Remote Access Transactions of the American Mathematical Society
Green Open Access

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: https://doi.org/10.1090/S0002-9947-1980-0549153-7
Keywords: Recursively enumerable sets, decision procedure, maximal sets, r-maximal sets, hyperhypersimple sets
Article copyright: © Copyright 1980 American Mathematical Society