Reverse mathematics and Ramsey properties of partial orderings (Q5963196)

This paper extends the study of reverse mathematics of Ramsey's theorem on partial orders. For a partial order \(\mathbb P\), write \(R^n (\mathbb P )\) if for every finite coloring of the length \(n\) chains of \(\mathbb P\), there is a homogeneous subset of \(\mathbb P\) order isomorphic to \(\mathbb P\). In [Electron. J. Comb. 20, No. 1, Research Paper P50, 27 p. (2013; Zbl 1266.05090)], the second author proved that for \(n\geq 3\) a bounded-level partial ordering \(\mathbb P\) with least element satisfies \(R^n (\mathbb P )\) if and only if it satisfies \(C(\mathbb P )\), where \(C(\mathbb P )\) is the conjunction of (1) \(\mathbb P\) is weakly proto-Ramsey, (2) \(\mathcal G (\mathbb P )\) is edge-Ramsey and has the joint embedding property, and (3) \(\mathbb P\) is biembeddable with a densely self-embeddable weakly proto-Ramsey partial ordering. These terms are defined in Section 2 of the paper. In this paper, the authors prove that for \(\mathbb P\) bounded-level with least element, ATR\(_0\) implies \(R^2 (\mathbb P ) \to C( \mathbb P )\), and \(C(P) \to R^3( \mathbb P )\) implies ACA\(_0\). They also construct a primitive recursive partial ordering such that RCA\(_0\) proves that \(R^2 ( \mathbb P )\) restricted to two colors is equivalent to ACA\(_0\). This equivalence between a Ramsey's theorem for pairs and ACA\(_0\) answers a question of \textit{J. Chubb} et al. [J. Symb. Log. 74, No. 1, 201--215 (2009; Zbl 1162.03009)]. For additional results on Ramsey's theorem for pairs in trees, see the forthcoming paper by \textit{D. Dzhafarov} and \textit{L. Patey} [``Coloring trees in reverse mathematics'', Preprint, \url{arXiv:1609.02627}].