On weak recursive degrees

Ishmukhametov S.


We introduce a concept of weak recursive degrees and show that
each weak recursive degree possess a weak recursive strong
minimal cover (s.m.c.). So any finite linear ordering can be
imbedded as initial segment into weak recursive degrees.
Besides, since the class of r.e. array nonrecursive (a.n.r.) degrees
defined by Downey, Jockusch and Stob [1990] is complementary to
the class of weak recursive degrees in the r.e. degrees {\bf R}
and no a.n.r.degree can possess a s.m.c. we obtain as a corollary
that a r.e. degree possess a s.m.c. iff it is weak recursive.
A degree {\bf m} is a strong minimal cover for a (Turing)
degree {\bf a}, if {\bf a$<$m} and for each degree
{\bf c,\, c$<$m$\rightarrow$ c$\le$a}.
Spector in [1956] raised the problem of a decription of
degrees possessing s.m.c. but there was a little progress
in this direction. On the other hand, more success was
achieved in the description of
degrees that cannot be s.m.c. Clearly, all r.e.degrees and all
degrees relatively enumerable in a less degree are splittable
so they cannot be s.m.c. For example, the class
of all degrees greater than or equal to {\bf 0}$'$ and the class of
1-generic degrees are such.
In [1990] and [1996] Downey, Jockusch and Stob defined a notion
of array nonrecursive degree as such a degree {\bf a} that for any
function $f\le_{tt}K$, where $K$ is a creative set, there is a function $g$
recursive in {\bf a} such that $g(n)\ge f(n)$ for infinitely many $n$.
They shown that any degree {\bf a} from $\overline{GL_2}$ (i.e.satisfying
{\bf a$''>($a$\cup$0}$')'$) is a.n.r. but there are also low and low$_2$
a.n.r. degrees.
The most important is that a.n.r.degrees are closed upwards, splittable and
cupped to all higher degrees (more generally, any recursively presented
lattice with distinct least and greatest elements can be embedded in the
lower cone {\bf D$(\le$a}) bounded by an a.n.r. degree {\bf a} preserving
least and greatest elements and lattice operations, Fejer [1989],
Downey, Jockusch and Stob [1996]).
So no a.n.r.degree {\bf a} can be a s.m.c. or possess a s.m.c.
Decreasing a gap between a.n.r.degrees and degrees possessing s.m.c
we introduce a notion of weak recursive degrees and show that
any weak recursive degree has a s.m.c.
\vspace{1mm}
{\bf Definition} A degree {\bf a} is weak recursive, if there is
a recursive function $p(x)$ such that for every function
$f$ recursive in {\bf a} there is a weak array $\{W_{h(n)}\}_{n=0}^{\infty}$
such that for every $n\in\omega$ :
1. $|W_{h(n)}|\le p(n)$,
2. $f(n)\in W_{h(n)}$,
3. $x\ne y\,\rightarrow W_{h(x)}\cap W_{h(y)}=\emptyset$.
It follows immediately from the definition that the class of weak
recursive degrees $WR$ is closed downwards, i.e. for any degrees
{\bf a,b}, if {\bf a$<$b} and {\bf b}$\in WR$, then {\bf a}$\in WR$.
If a weak recursive degree {\bf a} is located below {\bf 0}$'$,
then every function $f$ recursive in {\bf a} is $p$-r.e.
i.e. has a recursive
approximation $f(s,n)$ such that for every $n$
$|\{f(s,n):\,s\in\omega\}|\le p(n)$.
Since a r.e.degree {\bf a} is $p$-r.e. for some increasing recursive
function $p$ iff it is not array nonrecursive (Downey, Jockusch
and Stob [1990]), we obtain that the class of r.e. weak recursive degrees
is complementary to the class of array nonrecursive degrees
in {\bf R}. So the following proposition holds:
{\bf Proposition}. Let {\bf a} be a r.e.degree. Then the
following conditions are equivalent:
(1) {\bf a} is weak recursive,
(2) {\bf a} is not array nonrecursive,
(3) Any {\bf b,\,b$\le$ a} has a strong minimal cover,
(4) There is a degree {\bf b$\ge a$} which is not the sup of a minimal
pair (in all degrees) (Downey [1993],\,Theorem 1.1),
(5) There is a non-splittable degree {\bf b$\ge a$},
This gives a partial answer to the question of
Downey, Jockusch and Stob [1996] about definability of the class of
a.n.r.degrees by showing that the class of r.e. a.n.r.degrees is definable
(in all degrees) by any property listed in points (3)-(5) of the
Proposition using the fact that {\bf R} is definable
in all degrees (Cooper [ta]).
\hspace{3 cm} {\bf R e f e r e n c e s}
S.B. Cooper [1996] Strong minimal covers for recursively enumerable
degrees, Mathmatical Logic Quarterly, {\bf 42} (1996), pp.191-196
S.B. Cooper [ta] On a conjecture of Kleene and Post, to appear
R. Downey [1993] Array nonrecursive degrees and lattice embeddings of
the diamond, III. J. Math. {\bf 37} (1993), pp.349-374
R. Downey, C. Jockusch, and M. Stob [1990]. Array nonrecursive
sets and multiple permitting arguments, in Recursion Theory
Week, Proceedings, eds. K. Ambow-Spies, G.H. Muller, and
G. Sacks, Lect. Notes Math.,v. 1432, Springer-Verlag, Berlin, 1990,
pp.141-173
R. Downey, C. Jockusch, and M. Stob [1996]. Array nonrecursive sets and
genericity, in Computability, Enumerability, Unsolvability: Directions in
Recursion Theory, eds S.B. Cooper, T.A. Slaman, S.S. Wainer, London
Mathematical Society, Lect. Notes Swries N 224, Cambridge University Press,
pp.93-104
P. Fejer [1989] Embedding lattices with top preserved below non-$GL_2$
degrees, Zeitschr. f.math. Logik und Grundlagen d.Math. {\bf 35}
(1989), 527-539
Sh. Ishmukhametov [ta1] Minimal covers for recursively enumerable
degrees, J.Symb.Log. to appear
Sh.T. Ishmukhametov [ta2] On a new method for constructing minimal
Turing degrees, Izv. Vyssh. Ucheb. Zaved. (Russian), to appear
P. Odifreddi [1989] Classical Recursion Theory, Studies in Logic and
the Foundations of Mathematics, Vol. 125, North-Holland, Amsterdam.
C.Spector [1956] On degrees of recursive unsolvability, Ann. of Math.
(2) {\bf 64}, pp.581-592
C.E.M. Yates [1970] Initial segments of the degrees of unsolvability,
Part II: Minimal degrees, J.Symb.Log. 35 (1970) pp.243-266