Abstract

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^{}$. These results are best possible in various senses.