Extension of Embeddings in the Computably Enumerable Degrees
Theodore A. Slaman, Robert Irving Soare · Annals of Mathematics · 2001
Introduction G#del's incompleteness theorem [1931] and his subsequent work on computable functions [1934] exhibited undecidability in the most familiar mathematical settings, even in elementary number theory. Following G#del, there has been an intensive study of noncomputable sets arising in ordinary mathematics. Among these, the computably enumerable (c.e.) sets (those which can be listed by a computable method) are particularly interesting. For example, they play a key role in the unsolvability of the word problem for nitely presented groups and in the unsolvability of Hilbert's tenth problem on diophantine equations. Turing [1939] introduced the notion of relative computability of a set A from another B, written A T B. The equivalence class of A under j T is the (Turing) degree of A. Friedberg [1957] and