×

Stable Ramsey’s theorem and measure. (English) Zbl 1217.03019

A finite coloring of pairs \(f: [{\mathbb N} ]^2 \to k\) is called stable if, for each \(s\), the limit \(\lim_{t \to \infty} f(s,t)\) exists. P. A. Cholak, C. G. Jockusch jun., and T. A. Slaman [J. Symb. Log. 66, No. 1, 1–55 (2001; Zbl 0977.03033); corrigendum ibid. 74, No. 4, 1438–1439 (2009; Zbl 1182.03107)] studied the reverse mathematics of SRT\(^2_2\), a formalization of Ramsey’s theorem restricted to stable colorings. This paper introduces the principle ASRT\(^2_2\), which asserts that, for every martingale approximation \(M\), there is a stable two-coloring that is not in the success set for \(M\) and that has an infinite homogeneous set. This formalizes the notion that the collection of colorings for which SRT\(^2_2\) holds is not small, that is, not \(\Delta^0_2\)-null. The author proves that over RCA\(_0\), ASRT\(^2_2\) implies DNR but neither implies nor is implied by WKL\(_0\), and also that ASRT\(^2_2\) does not imply SRT\(^2_2\) or COH. The paper also explores the principle ASRAM, a measure-theoretic adaptation of the assertion that for every \(X\) there is a \(Y\) such that every \(X\)-computable stable coloring has a \(Y\)-computable homogeneous set. Many of the proofs involve construction of \(\omega\)-models based on results concerning \(s\)-Ramsey and almost \(s\)-Ramsey degrees, relating the work to that of J. R. Mileti [Bull. Symb. Log. 11, No. 3, 411–427 (2005; Zbl 1097.03037)].

MSC:

03B30 Foundations of classical theories (including reverse mathematics)
03D32 Algorithmic randomness and dimension
03D80 Applications of computability and recursion theory
03F35 Second- and higher-order arithmetic and fragments
05D10 Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI arXiv