Coloring the rationals in reverse mathematics

Article type: Research Article

Authors: Frittaion, Emanuele^a | Patey, Ludovic^b

Affiliations: [a] Mathematical Institute, Tohoku University, Japan. frittaion@math.tohoku.ac.jp; http://www.math.tohoku.ac.jp/~frittaion/ | [b] Laboratoire PPS, Paris Diderot University, France. ludovic.patey@computability.fr; http://ludovicpatey.com/

Abstract: 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.

Keywords: Reverse mathematics, Ramsey, computable reduction

DOI: 10.3233/COM-160067

Journal: Computability, vol. 6, no. 4, pp. 319-331, 2017