Decidability and Invariant Classes for Degree Structures

DOI10.2307/2000985zbMath0707.03036OpenAlexW4233434551MaRDI QIDQ3487331

Richard A. Shore, Manuel Lerman

Publication date: 1988

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

zbMATH Keywords

decision procedureinitial segmentjump classesextension of embeddings\(\forall \exists \)-theoryTuring degrees below \(\underset\sim 0^{\prime }\)

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Hierarchies of computability and definability (03D55)

Related Items

The Σ 2 theory of D h ( ⩽ h O ) as an uppersemilattice with least and greatest element is decidable ⋮ The ∀∃-theory of ℛ(≤,∨,∧) is undecidable ⋮ A non-inversion theorem for the jump operator ⋮ Homomorphisms and quotients of degree structures ⋮ The p-T-degrees of the recursive sets: Lattice embeddings, extensions of embeddings and the two-quantifier theory ⋮ Fragments of the theory of the enumeration degrees ⋮ Turing computability: structural theory ⋮ Extensions of embeddings below computably enumerable degrees

Cites Work

• Degrees which do not bound minimal degrees
• Initial segments of the degrees of unsolvability
• Jump restricted interpolation in the recursively enumerable degrees
• The upper semi-lattice of degrees of recursive unsolvability
• Degrees joining to 0′
• Defining Jump Classes in the Degrees Below 0'
• The Theory of the Degrees below 0 ′
• Initial segments of degrees below 0′
• A minimal degree not realizing least possible jump
• Simple Proofs of Some Theorems on High Degrees of Unsolvability
• Double jumps of minimal degrees
• Distributive Initial Segments of the Degrees of Unsolvability
• Initial segments of the degrees of unsolvability Part II: minimal degrees
• Unnamed Item
• Unnamed Item
• Unnamed Item