Reverse mathematics and Ramsey properties of partial orderings (Q5963196)
From MaRDI portal
scientific article; zbMATH DE number 6550117
Language | Label | Description | Also known as |
---|---|---|---|
English | Reverse mathematics and Ramsey properties of partial orderings |
scientific article; zbMATH DE number 6550117 |
Statements
Reverse mathematics and Ramsey properties of partial orderings (English)
0 references
4 March 2016
0 references
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}].
0 references
reverse mathematics
0 references
Ramsey properties
0 references
partitions
0 references
partial ordering
0 references
homogeneous subordering
0 references
monochromatic subordering
0 references
ACA
0 references
ATR
0 references