Rainbow Ramsey theorem for triples is strictly weaker than the arithmetical comprehension axiom. (English) Zbl 1300.03013

Wang, Wei

J. Symb. Log. 78, No. 3, 824-836 (2013).

The rainbow Ramsey theorem addresses colorings of \(n\)-tuples. A coloring \(f: [\mathbb N ]^n \to \mathbb N\) is \(k\)-bounded if \(|f^{-1}(c)|\leq k\) for every \(c \in \mathbb N\). A set \(R \subseteq \mathbb N\) is a rainbow for \(f\) if \(f\) is injective on \([R]^n\). For natural numbers \(n\) and \(k\), the rainbow Ramsey theorem states: (RRT\(^n_k\)) If \(f: [\mathbb N ]^n \to \mathbb N\) is \(k\)-bounded, then there is an infinite rainbow for \(f\). Working in the framework of reverse mathematics, the author shows that RCA\(_0\)+RRT\(^3_2\not\vdash\)ACA\(_0\) via an adaptation of cone-avoidance arguments like those used to analyze the strength of Ramsey’s theorem for pairs. This result is sharpened in the author’s article [Ann. Pure Appl. Logic 165, No. 2, 389–408 (2014; Zbl 1300.03012)]. For other results on the strength of the rainbow Ramsey theorem, see the work of B. F. Csima and J. R. Mileti [J. Symb. Log. 74, No. 4, 1310–1324 (2009; Zbl 1188.03044)].

Reviewer: Jeffry L. Hirst (Boone)

MSC:

03B30	Foundations of classical theories (including reverse mathematics)
03F35	Second- and higher-order arithmetic and fragments
03D80	Applications of computability and recursion theory

Keywords:

ACA; arithmetical comprehension; cone avoidance; cohesive set; rainbow Ramsey theorem; reverse mathematics

Citations:

Zbl 1188.03044; Zbl 1300.03012

References:

[1]	Combinatorial principles weaker than Ramsey’s theorem for pairs 72 pp 171– (2007) · Zbl 1118.03055
[2]	Ramsey’s theorem and cone avoidance 74 pp 557– (2009)
[3]	The strength of the rainbow Ramsey theorem 74 pp 1310– (2009)
[4]	On the strength of Ramsey’s theorem for pairs 66 pp 1– (2001) · Zbl 0977.03033
[5]	Ramsey’s Theorem does not hold in recursive set theory, Logic Colloquium (Manchester, 1969) pp 439– (1971)
[6]	Ramsey’s theorem and recursion theory 37 pp 268– (1972)
[7]	DOI: 10.1305/ndjfl/1040136917 · Zbl 0843.03034
[8]	Subsystems of second order arithmetic (1999) · Zbl 0909.03048
[9]	DOI: 10.1007/BFb0076224
[10]	Transactions of the American Mathematical Society 173 pp 33– (1972) · Zbl 0247.00014
[11]	Recursively enumerable sets and degrees (1987)