Some properties of recursively enumerable sets uniform for equivalence relations
Abstract (summary)
In Jockush, Lerman, Soare and Solovay's joint paper, the following equivalence reactions over (r.e.) sets A and B were introduced: (1) A $\sim\sb0$ B means that A = B. (2) A $\sim\sb1$ B means that A = *B. (where a = * B means A and B differ finitely.) (3) A $\sim\sb2$ B means that A $\equiv\sb{T}$ B. (4) A $\sim\sb{n}$ B where n $>$ 2 means that $A\sp{\rm (n-2)}\equiv\sb{T}B\sp{\rm (n-2)}$. (5) A $\sim\sb{\omega}$ B means that A $\sim\sb{n}$ B for some n $<$ $\omega$.<p> Many elementary properties of the degrees of r.e. sets, such as the existence of intermediate degrees between 0 and 0$\sp\prime$ and the Sacks splitting theorem have been studied. What we are trying to answer are the questions like: is there a version of those theorems which is uniform for the above equivalence relations? We are able to prove some uniform versions and reject some others. We are interested in the following questions: (1) Is there an e such that for every set $B\sb{T}\geq\emptyset\sp\prime$, if $C\sb{B}$ = $\varphi\sbsp{e}{B}$ then $C\sb{B}\sp\prime$ $\equiv\sb{T}C\sb{B}\oplus\emptyset\sp\prime$, and if B $\sim\sb{m}$ A, then $C\sb{B}\sim\sb{n}C\sb{A}$ where m, n $\in$ $\omega$? (2) For m, n $\in$ $\omega$, is there an e such that if X $\sim\sb{m}$ Y then $W\sbsp{e}{X}$ $\sim\sb{n}W\sbsp{e}{Y}$? where for all set X, X $<$ $W\sbsp{e}{X}<$ X$\sp\prime$. (3) Are there any recursive functions f and g such that for any $X\subset\omega$, $e \in \omega$, $W\sbsp{f(e)}{X}$, $W\sbsp{g(e)}{X}$ split $W\sbsp{e}{X}$ and for t, m, n $\in$ $\omega$, X, Y $\subset\omega$, if $X \sim\sb{t}Y$ and $W\sbsp{e}{X}\oplus X\sim\sb{m}W\sbsp{t}{Y}\oplus Y > X(or Y)$, then $W\sbsp{f(e)}{X}\oplus X\sim\sb{n}W\sbsp{f(i)}{Y}\oplus Y$, $W\sbsp{g(e)}{X}$ $\oplus$ X $\sim\sb{n}W\sbsp{g(i)}{Y}\oplus Y$?
Since the cases for t = m are the most interesting, we concentrate on dealing with the t = m cases.
Usually, when m, n are large enough (say $\geq$ 3), it's easy to find the answers. Most of the work has been done for m, n = 0, 1, or 2 (sometimes 3). Generally, we present counterexamples when m $>$ n and prove uniform versions otherwise. The open cases are when m = n = 2 and sometimes, when n = 1 and m = 2.