Definability in the Recursively Enumerable Degrees

DOI10.2307/421171zbMATH Open0874.03052OpenAlexW2000784135MaRDI QIDQ3128481FDOQ3128481

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

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

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 (14)

• 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
• Cappable recursively enumerable degrees and Post's program
• The nonlow computably enumerable degrees are not invariant in $\mathcal {E}$
• A Rigid Cone in the Truth-Table Degrees with Jump
• The existence of high nonbounding degrees in the difference hierarchy
• Low level nondefinability results: domination and recursive enumeration
• The $\Delta ^0_2$ Turing degrees: Automorphisms and Definability
• 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)