Recursively enumerable sets and van der Waerden's theorem on arithmetic progressions (Q1061736)

The following weak effective form of van der Waerden's theorem is proved: for every natural number k and every recursively enumerable (r.e.) set A, either A or some r.e. set \(B_ k\) disjoint from A contains infinitely many pairwise disjoint arithmetic progressions of length k. (The proof uses the classical finite form of van der Waerden's theorem.) One might hope to improve this by showing that \(B_ k\) could be chosen independently of k, but this is not possible. In fact it is shown that there is an r.e. set A such that A contains no arithmetic progression of length three, and yet no r.e. set disjoint from A contains arbitrarily long arithmetic progressions. The latter is proved by a priority argument.