Abstract/Details

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

Weber, Frank Peter. 
 University of Connecticut ProQuest Dissertations Publishing,  1992. 9310256.

Abstract (summary)

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.

Indexing (details)


Subject
Mathematics
Classification
0405: Mathematics
Identifier / keyword
Pure sciences; @r.e. degrees
Title
Invariant constructions in the relative r.e. degrees and embeddings into initial segments of the lattice of ideals of r.e. degrees
Author
Weber, Frank Peter
Number of pages
171
Degree date
1992
School code
0056
Source
DAI-B 53/12, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
979-8-208-80493-3
Advisor
Lerman, Manuel
University/institution
University of Connecticut
University location
United States -- Connecticut
Degree
Ph.D.
Source type
Dissertation or Thesis
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
9310256
ProQuest document ID
303970647
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
https://www.proquest.com/docview/303970647/abstract