Invariant constructions in the relative r.e. degrees and embeddings into initial segments of the lattice of ideals of r.e. degrees

Two types of problems in the r.e. degrees are investigated. First, when is the construction of relative r.e. sets with certain prescribed properties, uniform in the oracles? Second, which lattices can be embedded into all initial segments of the lattice of ideals of r.e. degrees?

(1) For each $n\in\omega$, define an equivalence relation $\sim\sb{n}$ on the subsets of $\omega$ as follows:

(UNFORMATTED TABLE OR EQUATION FOLLOWS)$$\eqalign{A\sim\sb0\ B\quad&{\rm if}\ A = B,\cr A\sim\sb1\ B\quad&{\rm if}\ A = \sp*B\ {\rm i.e.}\ (A-B)\cup(B-A)\ {\rm is\ finite,}\cr A\sim\sb2\ B\quad&{\rm if}\ A\equiv\sb{T}\ B,\cr A\sim\sb{n+2}\ B\quad&{\rm if}\ A\sp{(n)}\equiv\sb{T}\ B\sp{(n)},\ n\ge 1.\cr}$$(TABLE/EQUATION ENDS) $A\sp{(n)}$ denotes the nth iteration of the jump operation of A. Call a property P of r.e. sets m,n-invariant, if there exist an algorithm $\Phi\sb{e}$, such that for all oracles $A,B\subseteq\omega$ $W\sbsp{e}{A}$ has P relative to A, and $A\sim\sb{m}\ B\to W\sbsp{e}{A}\sim\sb{n}\ W\sbsp{e}{B}$. Sacks (20) asks whether there is a 2,2-invariant algorithm for incompleteness. We show:

Theorem 1. $(\exists e)(\forall A,\ B)\lbrack W\sbsp{e}{A}$ is simple in A and $A\sim\sb1\ B\to W\sbsp{e}{A}\sim\sb1\ W\sbsp{e}{A}\rbrack$.

Theorem 2. $\neg(\exists e)(\forall A,\ B)\lbrack W\sbsp{e}{A}$ is simple in A and $A\sim\sb3\ B\to W\sbsp{e}{A}\sim\sb1\ W\sbsp{e}{B}\rbrack$.

Theorem 3. $(\exists e)(\forall A,\ B)\lbrack W\sbsp{e}{A}$ is incomplete maximal in A and $A\sim\sb1\ B\to W\sbsp{e}{A}\sim\sb2\ W\sbsp{e}{B}\rbrack$.

(2) The investigation of the lattice ${\cal I}$ of ideals of r.e. degrees here derives from an attempt to settle the decidability of the $\forall\exists$ theory of the r.e. degree via reduction to the $\exists$ theory with enforcement of infima. By Lachlan, Soare (11) the $S\sb8$ does not embed into the r.e. degrees R, but recently Calhoun (3) showed the $S\sb8$ does embed in ${\cal I}$. Also recently Downey (5) showed the $M\sb3$ does not embed into every initial segment of R. We use a combination of the Lachlan-Lerman embedding technique together with a meet-preservation strategy of Fejer to show that the lattices mentioned embed into every initial segment of ${\cal I}$. We derive a general condition for embeddability into initial segments of ${\cal I}$ (apparently also valid for embeddability in ${\cal I}$ with 'preservation of the bottom'). As a corollary, we derive an embedding condition based on a decomposition of a lattice L into subsets $L\sb{j}$ determined by the set of join-relations $\{t\sb{j}=t\sbsp{j}{0}\vee t\sbsp{j}{1}\}\sb{j}$ and elements $f\sbsp{m}{0}$, $f\sbsp{m}{1}$ deriving from meet-relations $\{f\sb{m}=f\sbsp{m}{0}\wedge f\sbsp{m}{1}\}\sb{m}$ in L.

Corollary to Theorem 5 and Lemma 50. A lattice L embeds into all initial segments ${\cal I}\lbrack {\bf 0,a}\rbrack,\ {\bf a}>{\bf 0}$, if for each $j,m$ and each $i\in 2$, the set $L\sb{j}-\langle\le f\sbsp{m}{i}\rangle$ is non-empty. We show that the general condition is 'closed under forming 'stacks' of lattices.' We formulate still more inclusive embedding-strategies.