A Decidable Fragment of the Elementary Theory of the Lattice of Recursively Enumerable Sets
M. Lerman, Robert Irving Soare · Transactions of the American Mathematical Society · 1980
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.