$\Sigma_2$-Collection and the Infinite Injury Priority Method
Mytilinaios, Michael E. ; Slaman, Theodore A.
J. Symbolic Logic, Tome 53 (1988) no. 1, p. 212-221 / Harvested from Project Euclid
We show that the existence of a recursively enumerable set whose Turing degree is neither low nor complete cannot be proven from the basic axioms of first order arithmetic $(P^-)$ together with $\Sigma_2$-collection $(B\Sigma_2)$. In contrast, a high (hence, not low) incomplete recursively enumerable set can be assembled by a standard application of the infinite injury priority method. Similarly, for each $n$, the existence of an incomplete recursively enumerable set that is neither low$_n$ nor high$_{n - 1}$, while true, cannot be established in $P^- + B\Sigma_{n + 1}$. Consequently, no bounded fragment of first order arithmetic establishes the facts that the high$_n$ and low$_n$ jump hierarchies are proper on the recursively enumerable degrees.
Publié le : 1988-03-14
Classification: 
@article{1183742576,
     author = {Mytilinaios, Michael E. and Slaman, Theodore A.},
     title = {$\Sigma\_2$-Collection and the Infinite Injury Priority Method},
     journal = {J. Symbolic Logic},
     volume = {53},
     number = {1},
     year = {1988},
     pages = { 212-221},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183742576}
}
Mytilinaios, Michael E.; Slaman, Theodore A. $\Sigma_2$-Collection and the Infinite Injury Priority Method. J. Symbolic Logic, Tome 53 (1988) no. 1, pp.  212-221. http://gdmltest.u-ga.fr/item/1183742576/