Godel's Incompleteness Theorem and his subsequent work on computable functions exhibited undecidability in the most familiar mathematical settings, even in elementary number theory. Following Godel, 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 Godel'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 introduced the notion of a set of natural numbers A being computable relative to set B, written A \leT B. The equivalence class of $A$ under $\equivT$ is the ({\em Turing}) {\em degree} of $A$. %% Friedberg \cite{Friedberg:57*b} and independently Mu\v{c}nik \cite{Muchnik:56} 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 $\scrR$ = $(\boldR,<,\0,\0')$. Lower case boldface letters $\bolda, \boldb, \boldc, \dots \boldx, \boldy, \boldz$ denote c.e.\ degrees. The Friedberg-Mu\v{c}nik theorem may be regarded as the first and easiest extension of embeddings result for $\scrR$. It asserts that $(\exists\boldx)[\0<\boldx<\0'].$
Let $\bolda \lor \boldb $ denote the join of degrees $\bolda$ and $\boldb$ which always exists in $\boldR$. Sacks \cite{Sacks:63*b} introduced a stronger form of the finite injury method to prove his splitting theorem, $(\forall \bolda > \0) (\exists \boldx, \boldy) [\boldx \incomp \boldy \qand \boldx \lor \boldy = \bolda].$ Sacks \cite{Sacks:64} then developed a version of the infinite injury priority method to prove the density theorem, $(\forall \bolda, \boldb)[ \bolda < \boldb \to (\exists \boldx)[\bolda < \boldx < \boldb ]].$ %% Shoenfield \cite{Shoenfield:65} then conjectured that for all finite %% partial orderings upper semi-lattices $P\subseteq Q$ with least and greatest elements, any embedding of $P$ into the upper semi-lattice $(\boldR,<,\lor,\0,\0')$ can be extended to an embedding of $Q$ into the same. However, Lachlan \cite{Lachlan:66} and independently Yates \cite{Yates:66*b} refuted Shoenfield's conjecture by constructing a {\em minimal pair\/}, namely a pair of nonzero c.e.\ degrees $\pair{\bolda, \boldb}$ such that $\bolda \land \boldb = \0$.
The next significant advance was the Lachlan nonsplitting theorem which asserts that the Sacks splitting and density theorems cannot be combined simultaneously, Lachlan's result was significant first because it demonstrated a new kind of nonextension phenomenon, and second because its proof introduced a new and powerful technology (the $\0'''$-priority method) for constructing c.e.\ sets.
During the 1970's and 1980's this method was further developed and applied to prove a number of deep results about $\scrR$ such as the Harrington and Shelah theorem \cite{Harrington.Shelah:82} that the elementary theory of $\scrR$ is undecidable. It remained evident that $\scrR$ admits a considerable level of algebraic analysis. In this vein, attention was directed toward embedding and extension of embeddings problems for $\scrR$. Virtually all the major algebraic results about $\scrR$\ can be viewed as embedding, extension of embeddings results, or nonextension of embeddings results for $\scrR$ viewed as either a partial ordering or sometimes with partial lattice structure.
The extension of embeddings question was solved for certain related structures. For example, Fejer and Shore solved it for the c.e.\ tt-degrees and wtt-degrees. Shore and Slaman \cite{Shore.Slaman:91} calculated the extension of embeddings theory which is common to all principal ideals in $\scrR$ for which the top point is low$_2$ (i.e.\ $\bolda'' = \0''$). The method of proof in these results is to rule out certain extensions using the minimal pair method and then to realize those remaining extensions using the methods of the Sacks density theorem. %% However, the minimal pair method, with its associated theorems about meet and join, is not sufficient to capture all the nonextension properties of $\scrR$.
We solve the full extension of embeddings problem for the structure of the c.e.\ degrees $\scrR$. In {\S}\ref{sec:decision}, we state the extension criterion in terms of two relatively simple algebraic conditions on $P$ and $Q$. If Condition (1) holds, then in {\S}\ref{sec:ne1} we embed $P$ into $\scrR$ so that there is no extension to an embedding of $Q$; the proof uses a combination of elements from the proofs of the minimal pair and splitting theorems. If Condition (2) holds, then in {\S}\ref{sec:ne2} we construct a similar counterexample to extension of embedding; the proof uses a version of the Lachlan nonsplitting technology and the $\0'''$-method. If Conditions (1) and (2) both fail, then in {\S}\ref{sec:extension} we construct the required extension; the proof uses a strengthening of the Sacks density method generalizing \cite{Harrington.Soare:92}.