Coloring the rationals in reverse mathematics

DOI10.3233/COM-160067zbMATH Open1420.03026arXiv1508.00752OpenAlexW2963961606WikidataQ61308012 ScholiaQ61308012MaRDI QIDQ4601029FDOQ4601029

Authors: Emanuele Frittaion, Ludovic Patey 

Publication date: 18 January 2018

Published in: Computability (Search for Journal in Brave)

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 Erdos 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 eta, where eta 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 Erdos-Rado theorem, like the tree theorem for pairs, belongs to a family of Ramsey-type statements whose logical strength remains a challenge.

Full work available at URL: https://arxiv.org/abs/1508.00752

Recommendations

• On the strength of Ramsey's theorem
• On the strength of Ramsey's theorem for pairs
• The strength of Ramsey's theorem for coloring relatively large sets
• The strength of the rainbow Ramsey Theorem
• Effective versions of Ramsey's Theorem: Avoiding the cone above 0′

zbMATH Keywords

Ramsey theoremreverse mathematicscomputable reduction

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Applications of computability and recursion theory (03D80)

Cited In (7)

• On the Weihrauch degree of the additive Ramsey theorem over the rationals
• The uniform content of partial and linear orders
• Coloring trees in reverse mathematics
• Erdős-Moser and \(I \Sigma_2\)
• Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective
• Representation of the positive real numbers as sums of colored rational numbers
• Coloring terms to control equational reasoning

This page was built for publication: Coloring the rationals in reverse mathematics

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601029)