Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

A decidable fragment of the elementary theory of the lattice of recursively enumerable sets


Authors: M. Lerman and R. I. Soare
Journal: Trans. Amer. Math. Soc. 257 (1980), 1-37
MSC: Primary 03D25; Secondary 03B25
MathSciNet review: 549153
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A natural class of sentences about the lattice of recursively enumerable sets modulo finite sets is shown to be decidable. This class properly contains the class of sentences previously shown to be decidable by Lachlan. New structure results about the lattice of recursively enumerable sets are proved which play an important role in the decision procedure.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 03D25, 03B25

Retrieve articles in all journals with MSC: 03D25, 03B25


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1980-0549153-7
PII: S 0002-9947(1980)0549153-7
Keywords: Recursively enumerable sets, decision procedure, maximal sets, r-maximal sets, hyperhypersimple sets
Article copyright: © Copyright 1980 American Mathematical Society