Extension of embeddings in the computably enumerable degrees

DOI10.2307/3062109MaRDI QIDQ5945541zbMATH OpenOpenAlexFDO

Authors Theodore A. Slaman, Robert I. Soare

Publication date 14 February 2002

Published in Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/3062109

zbMATH Keywords

computably enumerable degreesembeddingsextensions of embeddingspartial orderings property

Mathematics Subject Classification ID

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

Review text

The paper presents a solution to an important, long-standing problem in the Turing degrees, the problem of extensions of given embeddings. More precisely, let \(P\), \(Q\) be partial orderings with \(P\) a sub-order of \(Q\) and such that there is an embedding \(\nu\) of \(P\) into the computably enumerable Turing degrees. The main result of the paper gives a necessary and sufficient condition when the embedding \(\nu\) can be extended to an embedding of \(Q\) into the c.e. degrees. This problem has already been solved for many related structures, such as c.e. tt-degrees and c.e. wtt-degrees, but nowhere it was so hard and complicated. It was preceded by a number of partial results and ends a long period of development in Computability Theory. It can be viewed also as a significant step in the theory of the priority method and a great advancement into its practice.

Recommendations

• Extensions of Embeddings in the Computably Enumerable Degrees
• Algebraic aspects of the computably enumerable degrees.
• Embedding finite lattices into the Σ₂⁰ enumeration degrees
• Extensions of embeddings below computably enumerable degrees
• A necessary and sufficient condition for embedding ranked finite partial lattices into the computably enumerable degrees

Cited in

(16)

• Fragments of the theory of the enumeration degrees
• Turing computability: structural theory
• The \(\forall \exists \)-theory of the effectively closed Medvedev degrees is decidable
• Extensions of embeddings below computably enumerable degrees
• Embedding countable partial orderings in the enumeration degrees and the -enumeration degrees
• Degree Structures: Local and Global Investigations
• Extensions of Embeddings in the Computably Enumerable Degrees
• Almost universal cupping and diamond embeddings
• The $\Pi _3$-theory of the computably enumerable Turing degrees is undecidable
• Embedding finite lattices into the ideals of computably enumerable turing degrees
• scientific article; zbMATH DE number 1531929 (Why is no real title available?)
• A GAP Package for Braid Orbit Computation and Applications
• The ∀∃-theory of ℛ(≤,∨,∧) is undecidable
• On the existence of a strong minimal pair
• Model-theoretic properties of Turing degrees in the Ershov difference hierarchy
• Structural theory of degrees of unsolvability: advances and open problems

This page was built for publication: Extension of embeddings in the computably enumerable degrees

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