# 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
Full Text:
##### References:
  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  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  Dorais, F. G., “A variant of Mathias forcing that preserves $$\mathsf{\mbox{ACA}}_{0}$$,” preprint, [math.LO] 1110.6559v2 · arxiv.org  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  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  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  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  Hájek, P., and P. Pudlák, Metamathematics of First-Order Arithmetic , Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1998. · Zbl 0903.01017  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  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  Hirst, J. L., “Combinatorics in subsystems of second order arithmetic,” Ph.D. dissertation, The Pennsylvania State University, ProQuest LLC, Ann Arbor, 1987.  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  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  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  Simpson, S. G., Subsystems of Second Order Arithmetic , 2nd edition, Perspectives in Logic, Cambridge University Press, Cambridge, 2009. · Zbl 1181.03001  Š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.