03843736

j

03843736 Stob, Michael Index sets and degrees of unsolvability. J. Symb. Log. 47, 241-248 (1982). 1982 Association for Symbolic Logic, Poughkeepsie, NY EN index sets degrees of unsolvability simple sets priority argument

doi:10.2307/2273139

The paper's first main theorem was announced by Kallibekov; it refines a result of Yates. Let \b{C} and \b{D} be nonrecursive r.e. sets, \b{C} not of degree ${\cal O}'$, \b{C} recursive in \b{D}. Let \b{S} be any set in $\Sigma\sb 3(\underline D)$ (i.e., what follows the initial quantifiers is recursive in \b{D}). Then there exists a uniformly r.e. sequence of r.e. sets $\{$ \b{A}${}\sb{\underline j}\}$ such that \b{A}${}\sb{\underline j}$ has the same (Turing) degree as \b{D} whenever \b{j}$\in \underline S$, but has degree incomparable with that of \b{C} otherwise. The proof uses an infinite injury priority argument, a method discussed at some length. The paper's second main theorem strengthens a result of Kinber. Let \b{S} be a $\Sigma\sb 3$ set of indices of r.e. sets, none of which is infinite, coinfinite and recursive. Then there exists a nonrecursive r.e. set in which no nonrecursive set with index in \b{S} is recursive. An interesting corollary is that an r.e. set has supersets of every r.e. degree iff it is not simple. J.S.Ullian