Ramsey’s theorem for trees: the polarized tree theorem and notions of stability. (English) Zbl 1215.03018

Dzhafarov, Damir D.; Hirst, Jeffry L.; Lakins, Tamara J.

Arch. Math. Logic 49, No. 3, 399-415 (2010).

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.

Reviewer: Antonio Montalbán (Chicago)

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

Keywords:

polarized version of Ramsey’s theorem for trees

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