Ramsey's Theorem for Computably Enumerable Colorings
Hummel, Tamara J. ; Jockusch, Carl G.
J. Symbolic Logic, Tome 66 (2001) no. 1, p. 873-880 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
It is shown that for each computably enumerable set $\mathscr{P}$ of n-element subsets of $\omega$ there is an infinite $\Pi^0_n$ set $A \subseteq \omega$ such that either all n-element subsets of A are in $\mathscr{P}$ or no n-element subsets of A are in $\mathscr{P}$. An analogous result is obtained with the requirement that A be $\Pi^0_n$ replaced by the requirement that the jump of A be computable from $0^{(n)}$. These results are best possible in various senses.
Publié le : 2001-06-14
Classification:  
@article{1183746479,
     author = {Hummel, Tamara J. and Jockusch, Carl G.},
     title = {Ramsey's Theorem for Computably Enumerable Colorings},
     journal = {J. Symbolic Logic},
     volume = {66},
     number = {1},
     year = {2001},
     pages = { 873-880},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183746479}
}

Hummel, Tamara J.; Jockusch, Carl G. Ramsey's Theorem for Computably Enumerable Colorings. J. Symbolic Logic, Tome 66 (2001) no. 1, pp.  873-880. http://gdmltest.u-ga.fr/item/1183746479/