00618229

j

00618229 Kumabe, Masahiro Minimal upper bounds for arithmetical degrees. J. Symb. Log. 59, No.2, 516-528 (1994). 1994 Association for Symbolic Logic, Poughkeepsie, NY EN arithmetical degrees arithmetical functions generic set minimal upper bound Zbl 0205.308

doi:10.2307/2275404

Minimal upper bounds for arithmetical degrees have been studied since the paper of {\it H. B. Enderton} and {\it H. Putnam} [J. Symb. Log. 35, 429- 430 (1970; Zbl 0205.308)]. They have strong connections with Cohen genericity, classical recursion theory, and models of true arithmetic. In this paper the author makes three contributions to the area. First he proves that if a function $f$ dominates all arithmetical functions, then $f$ computes a generic set. Next he solves two technical questions in the area. (1) He constructs a set $A$ with $\emptyset\sp{(\omega)} \geq\sb T A$ whose degree is a minimal upper bound for the arithmetical degrees such that any function recursive in $A$ is dominated by some arithmetical function. (2) He constructs a minimal upper bound $\bold a$ for the arithmetical degrees below $\text{{\bf 0}}\sp{(\omega)}$ such that (2i) for any ${\bold b} \leq {\bold a}$, if ${\bold b}$ is nonarithmetical, then ${\bold b} \cup \text{{\bf 0}}\sp{(n)} \geq {\bold a}$ for some $n$, and (2ii) there is a function $f \leq {\bold a}$ not dominated by any arithmetical function. R.Downey (Wellington)