A Decidable Fragment of the Elementary Theory of the Lattice of Recursively Enumerable Sets

DOI10.2307/1998123zbMath0439.03023OpenAlexW4237804810MaRDI QIDQ3880826

Robert I. Soare, Manuel Lerman

Publication date: 1980

Full work available at URL: https://doi.org/10.2307/1998123

zbMATH Keywords

decision proceduremaximal setshyperhypersimple setsr-maximal setsd-latticesfragment of the elementary theory of the lattice of the recursively enumberable sets

Mathematics Subject Classification ID

Logical aspects of lattices and related structures (03G10) Structure and representation theory of distributive lattices (06D05) Decidability of theories and sets of sentences (03B25) Recursively (computably) enumerable sets and degrees (03D25) Quantifier elimination, model completeness, and related topics (03C10)

Related Items

Duality, non-standard elements, and dynamic properties of r.e. sets ⋮ Property of t-retraceability and automorphisms of the lattice of recursively enumerable sets ⋮ Atomless \(r\)-maximal sets ⋮ Computably enumerable sets and related issues ⋮ \(r\)-maximal major subsets ⋮ Recursively enumerable sets and degrees

Cites Work

• d-simple sets, small sets, and degree classes
• \(r\)-maximal major subsets
• On some games which are relevant to the theory of recursively enumerable sets
• The elementary theory of recursively enumerable sets
• Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
• Determining Automorphisms of the Recursively Enumerable Sets
• Degrees of classes of RE sets
• On elementary theories of some lattices or α-recursively enumerable sets
• Nowhere simple sets and the lattice of recursively enumerable sets
• On the Lattice of Recursively Enumerable Sets
• Two Theorems on Hyperhypersimple Sets
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Degrees of recursively enumerable sets which have no maximal supersets
• Recursion, metarecursion, and inclusion

This page was built for publication: A Decidable Fragment of the Elementary Theory of the Lattice of Recursively Enumerable Sets