×

zbMATH — the first resource for mathematics

Ramsey’s theorem for trees: the polarized tree theorem and notions of stability. (English) Zbl 1215.03018
The authors study the reverse mathematics of a polarized version of Ramsey’s theorem for trees. Ramsey’s theorem for trees (studied by Chubb, Hirst and McNicholl) extends the usual infinite Ramsey’s theorem from \(\mathbb N\) to \(2^{<\mathbb N}\): It says that for every coloring of the increasing \(n\)-tuples of binary strings with \(k\) colors, there is a subset of \(2^{<\mathbb N}\), order-isomorphic to \(2^{<\mathbb N}\), which is homogeneous. The polarized Ramsey’s theorem (studied by Dzhafarov and Hirst) extends the usual infinite Ramsey’s theorem in a different way: It says that for every coloring of \([\mathbb N]^n\) with \(k\) colors, there exist sets \(H_1\),…, \(H_n\) of natural numbers such that \(H_1\times\cdots \times H_n \cap [\mathbb N]^n\) is monochromatic. In this paper, a version of Ramsey’s theorem which mixes both of these ideas is introduced.
For those exponents greater than 2, both the reverse mathematics and the computability theory associated with this theorem parallel that of its linear analog. For pairs the situation is more complex. In particular, there are many notions of stability in the tree setting, complicating the analysis of the related results.

MSC:
03B30 Foundations of classical theories (including reverse mathematics)
03D80 Applications of computability and recursion theory
03F35 Second- and higher-order arithmetic and fragments
05D10 Ramsey theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cholak P.A., Jockusch C.G., Slaman T.A.: On the strength of Ramsey’s theorem for pairs. J. Symbolic Logic 66, 1–55 (2001) · Zbl 0977.03033 · doi:10.2307/2694910
[2] Cholak P.A., Jockusch C.G., Slaman T.A.: Corrigendum to: on the strength of Ramsey’s theorem for pairs. J. Symbolic Logic 74, 1438–1439 (2009) · Zbl 1182.03107 · doi:10.2178/jsl/1254748700
[3] Chong C.T., Lempp S., Yang Y.: On the role of the collection principle for \({\Sigma^0_2}\) -formulas in second-order reverse mathematics. Proc. Amer. Math. Soc. 138, 1093–1100 (2010) · Zbl 1195.03015 · doi:10.1090/S0002-9939-09-10115-6
[4] Chubb J., Hirst J.L., McNicholl T.H.: Reverse mathematics, computability, and partitions of trees. J. Symbolic Logic 74, 201–215 (2009) · Zbl 1162.03009 · doi:10.2178/jsl/1231082309
[5] Computability, Reverse Mathematics, and Combinatorics: Open Problems, Banff International Research Station (BIRS), Alberta, Canada (2008) http://robson.birs.ca/\(\sim\)08w5019/problems.pdf . Accessed 7 October 2009
[6] Dzhafarov D.D., Hirst J.L.: The polarized Ramsey’s theorem. Arch. Math. Logic 48, 141–157 (2009) · Zbl 1172.03007 · doi:10.1007/s00153-008-0108-0
[7] Hirschfeldt D.R., Shore R.A.: Combinatorial principles weaker than Ramsey’s theorem for pairs. J. Symbolic Logic 72, 171–206 (2007) · Zbl 1118.03055 · doi:10.2178/jsl/1174668391
[8] Hummel T., Jockusch C.G. Jr: Generalized cohesiveness. J. Symbolic Logic 64, 489–516 (1999) · Zbl 0935.03050 · doi:10.2307/2586482
[9] Jockusch C.G. Jr: Ramsey’s theorem and recursion theory. J. Symbolic Logic 37, 268–280 (1972) · Zbl 0262.02042 · doi:10.2307/2272972
[10] Soare R.I.: Recursively Enumerable Sets and Degrees. Springer, Berlin (1987) · Zbl 0667.03030
[11] Simpson S.G.: Subsystems of Second Order Arithmetic. Springer, Berlin (1999) · Zbl 0909.03048
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.