×

Reverse mathematics and Ramsey’s property for trees. (English) Zbl 1203.03018

The authors explore the reverse mathematics of various formulations of Ramsey’s theorem on partial orderings. A partial ordering \(P\) satisfies Ramsey’s theorem for \(n\)-tuples, denoted by RT\(^n\)(\(P\)), if for every finite coloring of the \(n\)-element chains of \(P\) there is a monochromatic subordering which is order-isomorphic to \(P\). The restriction of RT\(^n\)(\(P\)) to \(k\)-colorings is denoted by RT\(^n_k\)(\(P\)). Working in RCA\(_0\), the authors show that when \(n \geq 3\) and \(k\geq 2\), ACA\(_0\) is equivalent to the statement “RT\(^n_k\)(\(P\)) holds if and only if the full binary tree \(2^{<\omega }\) can be embedded in \(P\).” They also describe a family of trees for which Ramsey’s theorem for pairs is equivalent to ACA\(_0\). In the last section, they consider RT\(^1\)(\(2^{<\omega}\)), which is a pigeonhole principle on \(2^\omega\), proving that if \(T\) is an extension of RCA\(_0\) by \(\Pi^1_1\) axioms, then \(T\) proves RT\(^1\)(\(2^{<\omega}\)) if and only if \(T\) proves the induction scheme for \(\Sigma^0_2\) formulas. In particular, RT\(^1\)(\(2^{<\omega}\)) is strictly stronger than the usual infinite pigeonhole principle. This work addresses questions posed by J. Chubb, J. L. Hirst, and T. H. McNicholl [J. Symb. Log. 74, No. 1, 201–215 (2009; Zbl 1162.03009)].

MSC:

03B30 Foundations of classical theories (including reverse mathematics)
03F35 Second- and higher-order arithmetic and fragments

Citations:

Zbl 1162.03009
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Subsystems of second order arithmetic (1999) · Zbl 0909.03048
[2] On the strength of Ramsey’s theorem for pairs 66 pp 1– (2001) · Zbl 0977.03033
[3] {\(\Sigma\)}2 induction and infinite injury priority argument, I. Maximal sets and the jump operator 63 pp 797– (1998)
[4] Reverse mathematics, computability, and partitions of trees 74 pp 201– (2009) · Zbl 1162.03009
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.