Extension of embeddings in the computably enumerable degrees (Q5945541)
From MaRDI portal
scientific article; zbMATH DE number 1657115
Language | Label | Description | Also known as |
---|---|---|---|
English | Extension of embeddings in the computably enumerable degrees |
scientific article; zbMATH DE number 1657115 |
Statements
Extension of embeddings in the computably enumerable degrees (English)
0 references
14 February 2002
0 references
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.
0 references
computably enumerable degrees
0 references
embeddings
0 references
partial orderings property
0 references
extensions of embeddings
0 references