×

Extension of embeddings in the computably enumerable degrees. (English) Zbl 0988.03063

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.

MSC:

03D25 Recursively (computably) enumerable sets and degrees
PDF BibTeX XML Cite
Full Text: DOI