Abstract
We identify computability-theoretic properties enabling us to separate various statements about partial orders in reverse mathematics. We obtain simpler proofs of existing separations, and deduce new compound ones. This work is part of a larger program of unification of the separation proofs of various Ramsey-type theorems in reverse mathematics in order to obtain a better understanding of the combinatorics of Ramsey’s theorem and its consequences. We also answer a question of Murakami, Yamazaki and Yokoyama about pseudo Ramsey’s theorem for pairs.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bienvenu, L., Patey, L., Shafer, P.: On the logical strengths of partial solutions to mathematical problems (2015). http://arxiv.org/abs/1411.5874
Bovykin, A., Weiermann, A.: The strength of infinitary Ramseyan principles can be accessed by their densities. Ann. Pure Appl. Logic, 4 (2005 to appear)
Cholak, P.A., Giusto, M., Hirst, J.L., Jockusch, Jr., C.G.: Free sets and reverse mathematics. Reverse Math. 21, 104–119 (2001)
Cholak, P.A., Jockusch, C.G., Slaman, T.A.: On the strength of Ramsey’s theorem for pairs. J. Symbolic Logic 66(01), 1–55 (2001)
Csima, B.F., Mileti, J.R.: The strength of the rainbow Ramsey theorem. J. Symbolic Logic 74(04), 1310–1324 (2009)
Dzhafarov, D.D., Jockusch, C.G.: Ramsey’s theorem and cone avoidance. J. Symbolic Logic 74(2), 557–578 (2009)
Friedman, H.: Adjacent ramsey theory. preprint, 8 (2010). https://u.osu.edu/friedman.8/
Friedman, H., Pelupessy, F.: Independence of Ramsey theorem variants using \(\varepsilon _0\). Proc. Am. Math. Soc. 144(2), 853–860 (2016)
Hirschfeldt, D.R., Jockusch, C.G., Kjos-Hanssen, B., Lempp, S., Slaman, T.A.: The strength of some combinatorial principles related to Ramsey’s theorem for pairs. Comput. Prospects Infinity Part II: Presented Talks 15, 143–161 (2008). World Scientific Press, Singapore
Hirschfeldt, D.R., Shore, R.A.: Combinatorial principles weaker than Ramsey’s theorem for pairs. J. Symbolic Logic 72(1), 171–206 (2007)
Jockusch, C.G.: Ramsey’s theorem and recursion theory. J. Symbolic Logic 37(2), 268–280 (1972)
Kučera, A.: Measure, \(\Pi ^0_1\) classes, and complete extensions of PA. In: Ebbinghaus, H.-D., Müller, G.H., Sacks, G.E. (eds.) Recursion Theory Week. Lecture Notes in Mathematics, vol. 1141, pp. 245–259. Springer, Heidelberg (1985)
Lerman, M., Solomon, R., Towsner, H.: Separating principles below Ramsey’s theorem for pairs. J. Math. Logic 13(02), 1350007 (2013)
Liu, L.: Cone avoiding closed sets. Trans. Am. Math. Soc. 367(3), 1609–1630 (2015). http://dx.org/10.1090/S0002-9947-2014-06049-2
Murakami, S., Yamazaki, T., Yokoyama, K.: On the Ramseyan factorization theorem. In: Beckmann, A., Csuhaj-Varjú, E., Meer, K. (eds.) CiE 2014. LNCS, vol. 8493, pp. 324–332. Springer, Heidelberg (2014)
Patey, L.: Iterative forcing and hyperimmunity in reverse mathematics. In: Beckmann, A., Mitrana, V., Soskova, M. (eds.) CiE 2015. LNCS, vol. 9136, pp. 291–301. Springer, Heidelberg (2015)
Patey, L.: The reverse mathematics of Ramsey-type theorems. Ph.D. thesis. Université Paris Diderot (2016)
Patey, L.: The weakness of being cohesive, thin or free in reverse mathematics. Isr. J. Math. (2016 to appear). http://arxiv.org/abs/1502.03709
Seetapun, D., Slaman, T.A.: On the strength of Ramsey’s theorem. Notre Dame J. Formal Logic 36(4), 570–582 (1995)
Steila, S., Yokoyama, K.: Reverse mathematical bounds for the termination theorem, to appear
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Patey, L. (2016). Partial Orders and Immunity in Reverse Mathematics. In: Beckmann, A., Bienvenu, L., Jonoska, N. (eds) Pursuit of the Universal. CiE 2016. Lecture Notes in Computer Science(), vol 9709. Springer, Cham. https://doi.org/10.1007/978-3-319-40189-8_36
Download citation
DOI: https://doi.org/10.1007/978-3-319-40189-8_36
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-40188-1
Online ISBN: 978-3-319-40189-8
eBook Packages: Computer ScienceComputer Science (R0)