Reducibility orderings: Theories, definability and automorphisms

DOI10.1016/0003-4843(80)90004-2zbMath0494.03028OpenAlexW2060031586MaRDI QIDQ3956925

Richard A. Shore, Anil Nerode

Publication date: 1980

Published in: Annals of Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0003-4843(80)90004-2

zbMATH Keywords

Turing degreessecond order arithmeticcoding symmetric irreflexive binary relationsr-degrees of arithmetic and hyperarithmetic sets

Mathematics Subject Classification ID

Inner models, including constructibility, ordinal definability, and core models (03E45) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

Interpolating \(d\)-r.e. and REA degrees between r.e. degrees ⋮ PERMUTATIONS OF THE INTEGERS INDUCE ONLY THE TRIVIAL AUTOMORPHISM OF THE TURING DEGREES ⋮ The jump is definable in the structure of the degrees of unsolvability ⋮ Degree theoretic definitions of the low₂ recursively enumerable sets ⋮ Permutations of the Integers Induce only the Trivial Automorphism of the Turing Degrees ⋮ Automorphism bases for degrees of unsolvability ⋮ Forcing and reducibilities ⋮ Embedding and coding below a 1-generic degree ⋮ Fragments of the theory of the enumeration degrees ⋮ The uniform Martin’s conjecture for many-one degrees ⋮ Undecidability and initial segments of the (r.e.) tt-degrees ⋮ Precomplete numberings ⋮ Low upper bounds of ideals ⋮ Automorphisms of the truth-table degrees are fixed on a cone ⋮ Definable degrees and automorphisms of 𝒟 ⋮ On the theory of the PTIME degrees of the recursive sets ⋮ 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