A $\Delta^0_2$ Set with No Infinite Low Subset in Either It or Its Complement
Downey, Rod ; Hirschfeldt, Denis R. ; Lempp, Steffen ; Solomon, Reed
J. Symbolic Logic, Tome 66 (2001) no. 1, p. 1371-1381 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
We construct the set of the title, answering a question of Cholak, Jockusch, and Slaman [1], and discuss its connections with the study of the proof-theoretic strength and effective content of versions of Ramsey's Theorem. In particular, our result implies that every $\omega$-model of RCA$_0$+ SRT$^2_2$ must contain a nonlow set.
Publié le : 2001-09-14
Classification:  
@article{1183746566,
     author = {Downey, Rod and Hirschfeldt, Denis R. and Lempp, Steffen and Solomon, Reed},
     title = {A $\Delta^0\_2$ Set with No Infinite Low Subset in Either It or Its Complement},
     journal = {J. Symbolic Logic},
     volume = {66},
     number = {1},
     year = {2001},
     pages = { 1371-1381},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183746566}
}

Downey, Rod; Hirschfeldt, Denis R.; Lempp, Steffen; Solomon, Reed. A $\Delta^0_2$ Set with No Infinite Low Subset in Either It or Its Complement. J. Symbolic Logic, Tome 66 (2001) no. 1, pp.  1371-1381. http://gdmltest.u-ga.fr/item/1183746566/