Ramsey's theorem for computably enumerable colorings

Citation
Tj. Hummel et Cg. Jockusch, Ramsey's theorem for computably enumerable colorings, J SYMB LOG, 66(2), 2001, pp. 873-880
Citations number
15
Categorie Soggetti
Mathematics
Journal title
JOURNAL OF SYMBOLIC LOGIC
ISSN journal
00224812 → ACNP
Volume
66
Issue
2
Year of publication
2001
Pages
873 - 880
Database
ISI
SICI code
0022-4812(200106)66:2<873:RTFCEC>2.0.ZU;2-W
Abstract
It is shown that for each computably enumerable set P of n-element subsets of m there is an infinite Pi (0)(n) set A subset of or equal to omega such that either all n-element subsets of ii are in P or no n-element subsets of A are in 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 fro m 0((n)). These results are best possible in various senses.