Degree Structures: Local and Global Investigations

DOI10.2178/bsl/1154698739zbMath1119.03039OpenAlexW2112163936MaRDI QIDQ3412461

Richard A. Shore

Publication date: 6 December 2006

Published in: Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/6f34e083bc9196db3b27e0f8e8b0dd104f2d2768

zbMATH Keywords

halting problemrecursively enumerable degreesTuring degree structures

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Recursively (computably) enumerable sets and degrees (03D25) Other Turing degree structures (03D28)

Related Items

THE n-r.e. DEGREES: UNDECIDABILITY AND Σ₁ SUBSTRUCTURES ⋮ Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes ⋮ DIRECT AND LOCAL DEFINITIONS OF THE TURING JUMP ⋮ The First Order Theories of the Medvedev and Muchnik Lattices ⋮ Set-theoretic blockchains ⋮ Extensions of embeddings below computably enumerable degrees ⋮ Definability via Kalimullin pairs in the structure of the enumeration degrees

Cites Work

• Unnamed Item
• Undecidability and 1-types in the recursively enumerable degrees
• On degrees of recursive unsolvability
• The elementary theory of the recursively enumerable degrees is not \(\aleph _ 0\)-categorical
• Inspheres and inner products
• Not every finite lattice is embeddable in the recursively enumerable degrees
• First-order theory of the degrees of recursive unsolvability
• Recursion theory and complexity. Proceedings of the Kazan '97 workshop, Kazan, Russia, July 14--19, 1997
• A finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees
• Defining the Turing jump
• The recursively enumerable degrees have infinitely many one-types
• The decidability of the existential theory of the poset of recursively enumerable degrees with jump relations
• A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees
• The recursively enumerable degrees are dense
• Initial segments of the degrees of unsolvability
• On the degrees less than 0'
• The upper semi-lattice of degrees of recursive unsolvability
• On a Conjecture of Kleene and Post
• A splitting theorem for $n-REA$ degrees
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• A minimal degree less than 0’
• The jump is definable in the structure of the degrees of unsolvability
• The undecidability of the recursively enumerable degrees
• On homogeneity and definability in the first-order theory of the Turing degrees
• Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers
• Lattice embeddings into the recursively enumerable degrees
• Interpretability and Definability in the Recursively Enumerable Degrees
• Definable degrees and automorphisms of 𝒟
• Reducibility orderings: Theories, definability and automorphisms
• Jump embeddings in the Turing degrees
• The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility
• Minimal degrees and the jump operator
• The homogeneity conjecture
• Lattice embeddings into the recursively enumerable degrees. II
• The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
• Lattice Embeddings into the R.E. Degrees Preserving 0 and 1
• Algebraic aspects of the computably enumerable degrees.
• PARAMETER DEFINABILITY IN THE RECURSIVELY ENUMERABLE DEGREES
• Local Initial Segments of The Turing Degrees
• Embedding jump upper semilattices into the Turing degrees
• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
• A General Framework for Priority Arguments
• On the Σ₂-theory of the upper semilattice of Turing degrees
• Degrees of Unsolvability. (AM-55)
• A minimal pair of recursively enumerable degrees
• The impossibility of finding relative complements for recursively enumerable degrees
• Distributive Initial Segments of the Degrees of Unsolvability
• Extension of embeddings in the computably enumerable degrees