Definability in the Recursively Enumerable Degrees

DOI10.2307/421171zbMATH Open0874.03052OpenAlexW2000784135MaRDI QIDQ3128481FDOQ3128481

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

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

zbMATH Keywords

automorphismdefinabilityTuring reducibilityrecursively enumerable degreesdouble jump

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (23)

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

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)