Definability in the Recursively Enumerable Degrees

DOI10.2307/421171MaRDI QIDQ3128481zbMATH OpenOpenAlexFDO

Authors André Nies, Richard A. Shore, Theodore A. Slaman

Publication date 5 November 1997

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

Full work available at URL https://semanticscholar.org/paper/74423533fd75cc39f55afa659665d6eff419a90d, http://www.math.ucla.edu/~asl/bsl/0204-toc.htm

zbMATH Keywords

automorphismdefinabilitydouble jumprecursively enumerable degreesTuring reducibility

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Review text

Let \(\mathcal R\) be the r.e. degrees with the usual partial order of Turing reducibility. This paper's main theorem is that in \(\mathcal R\) there is a definable copy \({\mathcal N}_0\) of the structure \(({\mathcal N},+,\times)\) and a definable map \(f:{\mathcal R}\to{\mathcal N}_0\) such that \(f({\mathbf a})\) is the code for the least index of some r.e. set whose double jump belongs to the double jump of \({\mathbf a}\). This comes ``within two jumps of a conjecture of Harrington, Slaman, and Woodin, which was the natural variant of this theorem that lacks the double jumps. Cooper showed in 1996 that their conjecture fails, so that the present theorem is the best possible. A relation is invariant in \(\mathcal R\) if automorphisms preserve it, invariant under the double jump if preserved when its arguments are replaced by degrees with the same double jumps. Among corollaries of the theorem: a relation is invariant in \(\mathcal R\) if it is invariant under double jump; any arithmetically definable relation that is invariant under double jump is definable in \(\mathcal R\); for \(k\geq 3\), the relation of having the same \(k\)th jump is definable in \(\mathcal R\); the class of \(\text{high}_n\) degrees is definable in \(\mathcal R\) for \(n\geq 1\), and so is the class of \(\text{low}_n\) degrees for \(n\geq 2\). (By Cooper's result, the class of \(\text{low}=\text{low}_1\) degrees is not definable in \(\mathcal R\).) These corollaries (but not others) may all be relativized to \({\mathcal R}^{\mathbf z}\), the structure of degrees r.e. in and above \({\mathbf z}\). The paper offers open questions and conjectures regarding the number and definability of automorphisms of \(\mathcal R\) and the definability in \(\mathcal R\) of individual degrees.

Recommendations

• Interpretability and Definability in the Recursively Enumerable Degrees
• Definability in the Turing degrees
• Defining Jump Classes in the Degrees Below 0'
• The nonlow computably enumerable degrees are not invariant in \(\mathcal{E}\)
• PARAMETER DEFINABILITY IN THE RECURSIVELY ENUMERABLE DEGREES

Cites work

• A minimal pair of recursively enumerable degrees
• Interpolation and embedding in the recursively enumerable degrees
• Lattice nonembeddings and initial segments of the recursively enumerable degrees
• Not every finite lattice is embeddable in the recursively enumerable degrees
• On homogeneity and definability in the first-order theory of the Turing degrees
• On the degrees less than 0'
• Recursively enumerable sets of positive integers and their decision problems
• The homogeneity conjecture
• The impossibility of finding relative complements for recursively enumerable degrees
• The recursively enumerable degrees are dense
• The undecidability of the recursively enumerable degrees
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• Undecidability and 1-types in the recursively enumerable degrees
• Working below a \(low_ 2\) recursively enumerable degree

Cited in

(24)

• Definability in the Turing degrees
• Cappable recursively enumerable degrees and Post's program
• On the jumps of the degrees below a recursively enumerable degree
• Nonbounding and Slaman triples
• The definability of \(\mathbb{E}\) in self-iterable mice
• The existence of high nonbounding degrees in the difference hierarchy
• On a Conjecture of Kleene and Post
• Biinterpretability up to double jump in the degrees below \(\mathbf{0}'\)
• Low level nondefinability results: domination and recursive enumeration
• A Rigid Cone in the Truth-Table Degrees with Jump
• On the definable ideal generated by nonbounding c.e. degrees
• Defining Jump Classes in the Degrees Below 0'
• Interpretability and Definability in the Recursively Enumerable Degrees
• PARAMETER DEFINABILITY IN THE RECURSIVELY ENUMERABLE DEGREES
• scientific article; zbMATH DE number 1531930 (Why is no real title available?)
• scientific article; zbMATH DE number 1531934 (Why is no real title available?)
• Recognizability equals definability for partial k-paths
• The ^0_2 Turing degrees: automorphisms and definability
• ON THE DEFINABILITY OF THE DOUBLE JUMP IN THE COMPUTABLY ENUMERABLE SETS
• The nonlow computably enumerable degrees are not invariant in \(\mathcal{E}\)
• scientific article; zbMATH DE number 1390016 (Why is no real title available?)
• A fixed point for the jump operator on structures
• Local Definitions in Degree Structures: The Turing Jump, Hyperdegrees and Beyond
• The relationship between local and global structure in the enumeration degrees

This page was built for publication: Definability in the Recursively Enumerable Degrees

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