Definability in the Turing degrees

MaRDI QIDQ1075320zbMATH OpenFDO

Authors Theodore A. Slaman, W. Hugh Woodin

Publication date 1986

Published in Illinois Journal of Mathematics (Search for Journal in Brave)

zbMATH Keywords

automorphismforcingjumprecursively enumerable degreesrigidity

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Review text

Suppose that \({\mathcal R}\) is a countable relation on the Turing degrees. Then \({\mathcal R}\) can be defined in \({\mathcal D}\), the Turing degrees with \(\leq_ T\), by a first order formula with finitely many parameters. The parameters are built by means of a notion of forcing in which the conditions are essentially finite. The conditions in the forcing partial specify finite initial segments of the generic reals and impose an infinite constraint on further extensions. This result is applied to show that any elementary function from \({\mathcal D}\) to \({\mathcal D}\) is an automorphism. Other applications are given toward the rigidity question for: By observing that a single jump is all that is needed to meet the relevant dense sets, it is also shown that the recursively enumerable degrees can be defined from finitely many parameters in the structure consisting of the degrees below O' with \(\leq_ T\).

Recommendations

• PARAMETER DEFINABILITY IN THE RECURSIVELY ENUMERABLE DEGREES
• Interpretability and Definability in the Recursively Enumerable Degrees
• Definability in the Recursively Enumerable Degrees
• scientific article; zbMATH DE number 66485
• scientific article; zbMATH DE number 1531930

Cited in

(35)

• Coding in the partial order of enumerable sets
• An oracle builder's toolkit
• Turing computability: structural theory
• The theory of ceers computes true arithmetic
• The \(\omega\)-Turing degrees
• A non-splitting theorem for d.r.e. sets
• Biinterpretability up to double jump in the degrees below \(\mathbf{0}'\)
• The typical Turing degree
• The Turing degrees below generics and randoms
• Definability in the Recursively Enumerable Degrees
• scientific article; zbMATH DE number 3861135 (Why is no real title available?)
• The jump is definable in the structure of the degrees of unsolvability
• Definable Filters in the Structure of Bounded Turing Reductions
• The First Order Theories of the Medvedev and Muchnik Lattices
• PARAMETER DEFINABILITY IN THE RECURSIVELY ENUMERABLE DEGREES
• Local Initial Segments of The Turing Degrees
• scientific article; zbMATH DE number 1531930 (Why is no real title available?)
• The ^0_2 Turing degrees: automorphisms and definability
• Definable relations in Turing degree structures
• Some properties of an algebra of all sets of naturals e-reducible to a fixed set
• scientific article; zbMATH DE number 7360060 (Why is no real title available?)
• Computing sets from all infinite subsets
• scientific article; zbMATH DE number 2204762 (Why is no real title available?)
• The enumeration degrees: local and global structural interactions
• Embedding and coding below a 1-generic degree
• Definability by turing machines
• scientific article; zbMATH DE number 2226385 (Why is no real title available?)
• Defining totality in the enumeration degrees
• The theory of the degrees is undecidable
• Sets of real numbers closed under Turing equivalence: applications to fields, orders and automorphisms
• The relationship between local and global structure in the enumeration degrees
• The Turing degrees: an introduction
• Generic degrees are complemented
• Model-theoretic properties of Turing degrees in the Ershov difference hierarchy
• On the theory of the PTIME degrees of the recursive sets

This page was built for publication: Definability in the Turing degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1075320)