Extension of Embeddings in the Computably Enumerable Degrees

Gödel’s Incompleteness Theorem [Göd31] and his subsequent work on computable functions [Göd34] 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. The computably enumerable (c.e.) sets (those which can be listed by a computable method) are of particular interest because they appear naturally in most branches of mathematics and there is a noncomputable c.e. set. Thus, they play a key role in well-known results such as Gödel’s incompleteness theorem, the unsolvability of the word problem for finitely presented groups, and the unsolvability of Hilbert’s tenth problem on Diophantine equations. Turing [Tur39] introduced the notion of a set of natural numbers A being computable relative to set B, written A ≤T B. The equivalence class of A under ≡T is the (Turing) degree of A. Friedberg [Fri57] and independently Mučnik [Muc56] solved Post’s problem by producing a noncomputable incomplete c.e. set, and in doing so introduced the finite injury priority method. Let 0 denote the degree of the computable sets and 0′ denote the degree of K, the complete c.e. set, and let R = (R, <,0,0′). Lower case boldface letters a,b, c, . . .x,y, z denote c.e. degrees. The Friedberg-Mučnik theorem may be regarded as the first and easiest extension of embeddings result for R. It asserts that (∃x)[0 < x < 0′].