Coloring the rationals in reverse mathematics

DOI10.3233/COM-160067MaRDI QIDQ4601029zbMATH OpenOpenAlexWikidataFDO

Authors Emanuele Frittaion, Ludovic Patey

Publication date 18 January 2018

Published in Computability (Search for Journal in Brave)

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

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)

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.

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′

Cited in

(7)

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

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)