×

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

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)].

MSC:

03B30 Foundations of classical theories (including reverse mathematics)
03F35 Second- and higher-order arithmetic and fragments
03D80 Applications of computability and recursion theory
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.