Ramsey’s theorem for pairs asserts that every 2-coloring of the pairs of integers has an infinite monochromatic subset. In this paper, we study a strengthening of Ramsey’s theorem for pairs due to Erdős and Rado, which states that every 2-coloring of the pairs of rationals has either an infinite 0-homogeneous set or a 1-homogeneous set of order type η, where η is the order type of the rationals. This theorem is a natural candidate to lie strictly between the arithmetic comprehension axiom and Ramsey’s theorem for pairs. This Erdős–Rado theorem, like the tree theorem for pairs, belongs to a family of Ramsey-type statements whose logical strength remains a challenge.
P.A.Cholak, C.G.Jockusch and T.A.Slaman, On the strength of Ramsey’s theorem for pairs, Journal of Symbolic Logic66(01) (2001), 1–55. doi:10.2307/2694910.
2.
J.Chubb, J.L.Hirst and T.H.McNicholl, Reverse mathematics, computability, and partitions of trees, The Journal of Symbolic Logic74(01) (2009), 201–215. doi:10.2178/jsl/1231082309.
3.
J.Corduan, M.J.Groszek and J.R.Mileti, Reverse mathematics and Ramsey’s property for trees, The Journal of Symbolic Logic75(03) (2010), 945–954. doi:10.2178/jsl/1278682209.
4.
D.D.Dzhafarov, J.L.Hirst and T.J.Lakins, Ramsey’s theorem for trees: The polarized tree theorem and notions of stability, Archive for Mathematical Logic49(3) (2010), 399–415. doi:10.1007/s00153-010-0179-6.
5.
D.R.Hirschfeldt, Slicing the Truth, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, Vol. 28, 2014.
6.
D.D.Dzhafarov, Strong reductions between combinatorial principles, Journal of Symbolic Logic, to appear.
7.
P.Erdős and R.Rado, Combinatorial theorems on classifications of subsets of a given set, Proceedings of the London Mathematical Society3(1) (1952), 417–439. doi:10.1112/plms/s3-2.1.417.
8.
E.Frittaion and A.Marcone, Linear extensions of partial orders and reverse mathematics, MLQ Math. Log. Q.58(6) (2012). doi:10.1002/malq.201200025.
9.
J.L.Hirst, Combinatorics in subsystems of second order arithmetic, PhD thesis, Pennsylvania State University, August 1987.
10.
C.G.Jockusch, Ramsey’s theorem and recursion theory, Journal of Symbolic Logic37(2) (1972), 268–280. doi:10.2307/2272972.
11.
C.G.Jockusch and R.I.Soare, classes and degrees of theories, Transactions of the American Mathematical Society173 (1972), 33–56.
12.
M.Lerman, R.Solomon and H.Towsner, Separating principles below Ramsey’s theorem for pairs, Journal of Mathematical Logic13(02) (2013), 1350007. doi:10.1142/S0219061313500074.
13.
A.Montalbán, Open questions in reverse mathematics, Bulletin of Symbolic Logic17(03) (2011), 431–454. doi:10.2178/bsl/1309952320.
14.
L.Patey, Iterative forcing and hyperimmunity in reverse mathematics, in: Evolving Computability, A.Beckmann, V.Mitrana and M.Soskova, eds, Lecture Notes in Computer Science, Vol. 9136, Springer International Publishing, 2015, pp. 291–301. doi:10.1007/978-3-319-20028-6_30.
15.
L.Patey, The strength of the tree theorem for pairs in reverse mathematics. Journal of Symbolic Logic, to appear.
16.
L.Patey, The weakness of being cohesive, thin or free in reverse mathematics, Israel Journal of Mathematics, to appear. Available at: http://arxiv.org/abs/1502.03709.
17.
J.G.Rosenstein, Linear Orderings, Pure and Applied Mathematics, Vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982.
18.
D.Scott, Algebras of sets binumerable in complete extensions of arithmetic, in: Proc. Sympos. Pure Math, Vol. 5, 1962, pp. 117–121.
19.
D.Seetapun and T.A.Slaman, On the strength of Ramsey’s theorem, Notre Dame Journal of Formal Logic36(4) (1995), 570–582. doi:10.1305/ndjfl/1040136917.
20.
J.R.Shoenfield, On degrees of unsolvability, Annals of Mathematics69(03) (1959), 644–653. doi:10.2307/1970028.
21.
S.G.Simpson, Subsystems of Second Order Arithmetic, Cambridge University Press, 2009.
