Recursively enumerable sets and van der Waerden’s theorem on arithmetic progressions

Carl Groos Jockusch, Jr. and Iraj Kalantari

Vol. 115 (1984), No. 1, 143–153

DOI: 10.2140/pjm.1984.115.143

Abstract

Subsets of the set ω of nonnegative integers which possess some algebraic structure are interesting since they are most likely to give number-theoretic information. Arithmetic progressions are one of the simplest structures to observe. Effectiveness of any kind of information is of course an important factor. It seems that a study of possible interrelationships between combinatoric and number-theoretic properties of recursively enumerable (r.e.) subsets of ω might be interesting. In this paper we study van der Waerden’s theorem on arithmetic progressions in this light.

Mathematical Subject Classification 2000

Primary: 03D80

Secondary: 03D25, 03F65, 11B25

Milestones

Received: 21 December 1982

Published: 1 November 1984