Coloring trees in reverse mathematics

DOI10.1016/J.AIM.2017.08.009zbMATH Open1423.03048arXiv1609.02627OpenAlexW2964019544MaRDI QIDQ2401697FDOQ2401697

Authors: Ludovic Patey, Damir D. Dzhafarov 

Publication date: 4 September 2017

Published in: Advances in Mathematics (Search for Journal in Brave)

Abstract: The tree theorem for pairs ($mathsf{TT}_2^2$), first introduced by Chubb, Hirst, and McNicholl, asserts that given a finite coloring of pairs of comparable nodes in the full binary tree $2^{<omega}$, there is a set of nodes isomorphic to $2^{<omega}$ which is homogeneous for the coloring. This is a generalization of the more familiar Ramsey's theorem for pairs ($mathsf{RT}_2^2$), which has been studied extensively in computability theory and reverse mathematics. We answer a longstanding open question about the strength of $mathsf{TT}_2^2$, by showing that this principle does not imply the arithmetic comprehension axiom ($mathsf{ACA}_0$) over the base system, recursive comprehension axiom ($mathsf{RCA}_0$), of second-order arithmetic. In addition, we give a new and self-contained proof of a recent result of Patey that $mathsf{TT}_2^2$ is strictly stronger than $mathsf{RT}_2^2$. Combined, these results establish $mathsf{TT}_2^2$ as the first known example of a natural combinatorial principle to occupy the interval strictly between $mathsf{ACA}_0$ and $mathsf{RT}_2^2$. The proof of this fact uses an extension of the bushy tree forcing method, and develops new techniques for dealing with combinatorial statements formulated on trees, rather than on $omega$.

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

Recommendations

• The strength of the tree theorem for pairs in reverse mathematics
• Reverse mathematics and Ramsey's property for trees
• The strength of Ramsey's theorem for pairs over trees. I: Weak König's lemma
• Partitions of trees and \({{\text \textsf{ACA}}^\prime_{0}}\)
• On the strength of Ramsey's theorem for trees

zbMATH Keywords

reverse mathematicsRamsey's theoremcomputable combinatorics

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35)

Cites Work

• Algorithmic randomness and complexity.
• Subsystems of second order arithmetic
• ∏ 0 1 Classes and Degrees of Theories
• On the strength of Ramsey's theorem for pairs
• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• Slicing the Truth
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Ramsey's theorem and recursion theory
• Open Questions in Reverse Mathematics
• On the strength of Ramsey's theorem
• Reverse mathematics and Ramsey's property for trees
• Turing Computability
• Generics for computable Mathias forcing
• Partition Theorems and Computability Theory
• Ramsey-type graph coloring and diagonal non-computability
• On uniform relationships between combinatorial problems
• Ramsey's theorem and cone avoidance
• FORCING WITH BUSHY TREES
• A fixed-point-free minimal degree
• Reverse mathematics, computability, and partitions of trees
• Ramsey's theorem for trees: the polarized tree theorem and notions of stability
• Coloring the rationals in reverse mathematics
• Cone avoiding closed sets
• Nonstandard models in recursion theory and reverse mathematics
• Minimal complementation below uniform upper bounds for the arithmetical degrees
• Reverse mathematics and Ramsey properties of partial orderings

Cited In (9)

• RAMSEY-LIKE THEOREMS AND MODULI OF COMPUTATION
• The strength of Ramsey’s theorem for pairs over trees: I. Weak König’s Lemma
• Reverse mathematics and parameter-free transfer
• Reverse mathematics and Ramsey properties of partial orderings
• Reverse mathematics, computability, and partitions of trees
• Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective
• The Ginsburg-Sands theorem and computability theory
• On the strength of Ramsey's theorem for trees
• Ramsey's theorem for pairs and provably recursive functions

This page was built for publication: Coloring trees in reverse mathematics

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