id: 03926897
dt: j
an: 03926897
au: Welch, Lawrence V.
ti: A hierarchy of families of recursively enumerable degrees.
so: J. Symb. Log. 49, 1160-1170 (1984).
py: 1984
pu: Association for Symbolic Logic, Poughkeepsie, NY
la: EN
cc: 
ut: 
ci: 
li: doi:10.2307/2274268
ab: Assume that e is a number, b is a r.e. degree, and A is a set. We say that
    e is a representative for b in A if $e\in A$ and $W\sb e\in b$. Let A
    be a set and let ${\frak A}$ be a family of r.e. degrees. We say that A
    is a basis for ${\frak A}$ if the following two conditions hold: (1)
    every e in A is a representative in A for some b in ${\frak A}$; (ii)
    every b in ${\frak A}$ has a representative in A. Given any number n,
    we say that ${\tilde Δ}\sb n$ is the class of all ${\frak A}$ which
    have a $Δ\sb n$ basis, ${\tilde Π}\sb n$ is the class of all ${\frak
    A}$ which have a $Π\sb n$ basis, and ${\tilde Σ}\sb n$ is the class
    of all ${\frak A}$ which have a $Σ\sb n$ basis. In this paper it is
    shown that for all n, ${\tilde Δ}\sb n=Σ\sb n$ and for any n,
    ${\tilde Σ}\sb n\cup {\tilde Π}\sb n={\tilde Π}\sb n$ and ${\tilde
    Σ}\sb n\cap {\tilde Π}\sb n={\tilde Δ}\sb n$. The main results of
    this paper are the following theorems: Theorem 6. For all n, if ${\frak
    A}$ is ${\tilde Δ}\sb{n+1}$ then ${\frak A}$ is ${\tilde Π}\sb n$.
    Theorem 10. If $n\ge 3$ then ${\tilde Π}\sb n-{\tilde Π}\sb{n-1}\ne
    \emptyset$ (${\tilde Π}\sb 0={\tilde Π}\sb 1={\tilde Π}\sb 2)$.
    Theorem 11. If a is a Turing degree such that $a\ge 0\sp{(3)}$ then
    there is a family ${\frak A}$ such that deg(ind(${\frak A}))=a$.
    Theorem 12. If ${\frak A}$ is a nonempty family of r.e. degrees such
    that 0’ is not in ${\frak A}$, then $Rec\le\sb 1ind({\frak A})$.
    Theorem 15. If ${\frak A}$ is a nonempty family of r.e. degrees such
    that 0 is not in ${\frak A}$, and if ${\frak A}$ is ${\tilde Π}\sb 0$,
    then $Rec\le\sb 1ind({\frak A})$.
rv: R.Sh.Omanadze (Tbilisi)