×

zbMATH — the first resource for mathematics

On the indecomposability of \(\omega^n\). (English) Zbl 1260.03017
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}\).
MSC:
03B30 Foundations of classical theories (including reverse mathematics)
03F35 Second- and higher-order arithmetic and fragments
PDF BibTeX XML Cite
Full Text: DOI Euclid arXiv
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 · doi:10.2307/2694910
[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 · doi:10.1090/S0002-9939-09-10115-6
[3] Dorais, F. G., “A variant of Mathias forcing that preserves \(\mathsf{\mbox{ACA}}_{0}\),” preprint, [math.LO] 1110.6559v2 · arxiv.org
[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 · doi:10.2307/2695113
[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 · doi:10.1007/s00153-008-0108-0
[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 · doi:10.2178/jsl/1243948327
[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 · doi:10.2178/jsl/1174668391
[10] Hirst, J. L., “Reverse mathematics and ordinal exponentiation,” Annals of Pure and Applied Logic , vol. 66 (1994), pp. 1-18. · Zbl 0791.03034 · doi:10.1016/0168-0072(94)90076-0
[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 · doi:10.1002/malq.19930390153
[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 · doi:10.1305/ndjfl/1040136917
[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 · emis:journals/CMUC/cmuc0303/cmuc0303.htm · eudml:22714
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.