First-order theory of the degrees of recursive unsolvability

DOI10.2307/1971028zbMath0349.02035OpenAlexW2016487828WikidataQ56430704 ScholiaQ56430704MaRDI QIDQ1234682

Stephen G. Simpson

Publication date: 1977

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

THE n-r.e. DEGREES: UNDECIDABILITY AND Σ₁ SUBSTRUCTURES ⋮ The ∀∃-theory of ℛ(≤,∨,∧) is undecidable ⋮ Degrees of unsolvability of continuous functions ⋮ The theory of the \(\alpha \) degrees is undecidable ⋮ The jump is definable in the structure of the degrees of unsolvability ⋮ The theory of ceers computes true arithmetic ⋮ The enumeration degrees: Local and global structural interactions ⋮ The existential theory of the poset of R.E. degrees with a predicate for single jump reducibility ⋮ Not every finite lattice is embeddable in the recursively enumerable degrees ⋮ ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS ⋮ Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes ⋮ The $\Delta ^0_2$ Turing degrees: Automorphisms and Definability ⋮ The relationship between local and global structure in the enumeration degrees ⋮ MASS PROBLEMS AND HYPERARITHMETICITY ⋮ DIRECT AND LOCAL DEFINITIONS OF THE TURING JUMP ⋮ Interpreting true arithmetic in the -enumeration degrees ⋮ The First Order Theories of the Medvedev and Muchnik Lattices ⋮ Local Definitions in Degree Structures: The Turing Jump, Hyperdegrees and Beyond ⋮ Embedding and coding below a 1-generic degree ⋮ Fragments of the theory of the enumeration degrees ⋮ Undecidability and initial segments of the (r.e.) tt-degrees ⋮ Coding true arithmetic in the Medvedev and Muchnik degrees ⋮ Definable degrees and automorphisms of 𝒟 ⋮ Initial segments of the degrees of size \(\aleph _ 1\) ⋮ Degree Structures: Local and Global Investigations ⋮ On homogeneity and definability in the first-order theory of the Turing degrees ⋮ Biinterpretability up to double jump in the degrees below $\mathbf {0}^{\prime }$ ⋮ Forcing and reductibilities. II. Forcing in fragments of analysis ⋮ Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers