On the indecomposability of \(\omega^n\). (English) Zbl 1260.03017

Corduan, Jared R.; Dorais, François G.

Notre Dame J. Formal Logic 53, No. 3, 373-395 (2012).

The authors consider several formulations of pigeonhole principles for finite powers of \(\omega\). The study leads to formalization of two versions of Ramsey’s theorem:
(1) Weak Ramsey’s theorem (WRT\(^2_k\)): For every finite coloring \(c: [\mathbb N ]^2 \to k\) we can find a color \(d\) and an infinite set \(H\) such that for each \(x \in H\) the set \(\{ y \mid c(x,y ) = d \}\) is infinite, and
(2) Hyperweak Ramsey’s theorem (HWRT\(^2_k\)): For every \(c : [\mathbb N ]^2 \to k\) we can find a color \(d\) and an increasing function \(h : \mathbb N \to \mathbb N\) such that, if \(0 < i < j\), there is an \((x,y) \in [h(i-1), h(i) -1 ] \times [h(j-1) , h(j) - 1 ]\) such that \(c(x,y) = d\).
The authors prove that HWRT\(^2_2\) is strictly weaker than WRT\(^2_2\) and that both are weaker than IPT\(^2_2\), as by D. D. Dzhafarov and J. L. Hirst [Arch. Math. Logic 48, No. 2, 141–157 (2009; Zbl 1172.03007)], and stronger than SADS, as in [D. R. Hirschfeldt and R. A. Shore, J. Symb. Log. 72, No. 1, 171–206 (2007; Zbl 1118.03055)]. Other principles introduced in the paper lie between B\(\Pi^0_n\) and I\(\Sigma^0_{n+1}\).

Reviewer: Jeffry L. Hirst (Boone)

MSC:

03B30	Foundations of classical theories (including reverse mathematics)
03F35	Second- and higher-order arithmetic and fragments

Keywords:

reverse mathematics; indecomposability; partition principle; pigeonhole principle; ordinal; Ramsey’s theorem

Citations:

Zbl 1172.03007; Zbl 1118.03055

References:

[1]	Cholak, P. A., C. G. Jockusch, and T. A. Slaman, “On the strength of Ramsey’s theorem for pairs,” Journal of Symbolic Logic , vol. 66 (2001), pp. 1-55. · Zbl 0977.03033
[2]	Chong, C. T., S. Lempp, and Y. Yang, “On the role of the collection principle for \(\Sigma^{0}_{2}\)-formulas in second-order reverse mathematics,” Proceedings of the American Mathematical Society , vol. 138 (2010), pp. 1093-1100. · Zbl 1195.03015
[3]	Dorais, F. G., “A variant of Mathias forcing that preserves \(\mathsf{\mbox{ACA}}_{0}\),” preprint, [math.LO] 1110.6559v2
[4]	Downey, R., D. R. Hirschfeldt, S. Lempp, and R. Solomon, “A \(\Delta_{2}^{0}\) set with no infinite low subset in either it or its complement,” Journal of Symbolic Logic , vol. 66 (2001), pp. 1371-1381. · Zbl 0990.03046
[5]	Dzhafarov, D. D., and J. L. Hirst, “The polarized Ramsey’s theorem,” Archive for Mathematical Logic , vol. 48 (2009), pp. 141-157. · Zbl 1172.03007
[6]	Dzhafarov, D. D., and C. G. Jockusch, “Ramsey’s theorem and cone avoidance,” Journal of Symbolic Logic , vol. 74 (2009), pp. 557-578. · Zbl 1166.03021
[7]	Fraïssé, R., Theory of Relations , revised edition, with an appendix by N. Sauer, vol. 145 of Studies in Logic and the Foundations of Mathematics , North-Holland Publishing Co., Amsterdam, 2000. · Zbl 0965.03059
[8]	Hájek, P., and P. Pudlák, Metamathematics of First-Order Arithmetic , Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1998. · Zbl 0903.01017
[9]	Hirschfeldt, D. R., and R. A. Shore, “Combinatorial principles weaker than Ramsey’s theorem for pairs,” Journal of Symbolic Logic , vol. 72 (2007), pp. 171-206. · Zbl 1118.03055
[10]	Hirst, J. L., “Reverse mathematics and ordinal exponentiation,” Annals of Pure and Applied Logic , vol. 66 (1994), pp. 1-18. · Zbl 0791.03034
[11]	Hirst, J. L., “Combinatorics in subsystems of second order arithmetic,” Ph.D. dissertation, The Pennsylvania State University, ProQuest LLC, Ann Arbor, 1987.
[12]	Jockusch, C., and F. Stephan, “A cohesive set which is not high,” Mathematical Logic Quarterly , vol. 39 (1993), pp. 515-530. · Zbl 0799.03048
[13]	Kohlenbach, U., “Higher order reverse mathematics,” pp. 281-295 in Reverse Mathematics 2001 , vol. 21 of Lecture Notes in Logic , Association for Symbolic Logic, La Jolla, California, 2005. · Zbl 1097.03053
[14]	Seetapun, D., and T. A. Slaman, “On the strength of Ramsey’s theorem,” Notre Dame Journal of Formal Logic , vol. 36 (1995), pp. 570-582. · Zbl 0843.03034
[15]	Simpson, S. G., Subsystems of Second Order Arithmetic , 2nd edition, Perspectives in Logic, Cambridge University Press, Cambridge, 2009. · Zbl 1181.03001
[16]	Švejdar, V., “The limit lemma in fragments of arithmetic,” Commentationes Mathematicae Universitatis Carolinae , vol. 44 (2003), pp. 565-568. · Zbl 1098.03067