Partitions of trees and ACA^_0
\textit{J. Chubb, J. L. Hirst} and \textit{T. H. McNicholl} [``Reverse mathematics, computability, and partitions of trees, J. Symb. Log. 74, No. 1, 201--215 (2009; Zbl 1162.03009)] introduced a version of Ramsey's theorem for trees and proved that, for each standard exponent \(n\geq 3\), the usual Ramsey's theorem for \(n\)-tuples is equivalent to the tree version. Here, the authors show that the universally quantified versions are also equivalent, and hence equivalent to \(\text{ACA}'_0\), over \(\text{RCA}_0\). The tree version of Ramsey's theorem is formulated as follows. Given a set \(S\subseteq 2^{<\mathbb{N}}\), we let \([S]^n\) be the set of linearly ordered \(n\)-tuples of nodes from \(S\). The statement \(\text{TT}(n)\) says that for every \(k\), and every coloring of \([2^{<\mathbb{N}}]^n\) with \(k\) colors, there exists a subset \(S\subseteq 2^{<\mathbb{N}}\), isomorphic to \(2^{<\mathbb{N}}\), such that \([S]^n\) is monochromatic. The universally quantified version, \(\forall n\;\text{TT}(n)\), is the one that is shown to be equivalent to \(\text{ACA}'_0\), over \(\text{RCA}_0\).
- scientific article; zbMATH DE number 887757
- Ramsey's theorem for trees: the polarized tree theorem and notions of stability
- Abstract approach to Ramsey theory and Ramsey theorems for finite trees
- On the Ramsey numbers of trees with small diameter
- Reverse mathematics, computability, and partitions of trees
- Dual Ramsey theorem for trees
- Large Finite Sets
- The strength of the tree theorem for pairs in reverse mathematics
- Big Ramsey degrees of 3-uniform hypergraphs are finite
- The Ramsey numbers of trees versus \(W_{6}\) or \(W_{7}\)
This page was built for publication: Partitions of trees and \({{\text \textsf{ACA}}^\prime_{0}}\)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1016503)
