The strength of Ramsey's theorem for pairs over trees. I: Weak König's lemma

DOI10.1090/TRAN/8339MaRDI QIDQ5004544zbMATH OpenOpenAlexWikidataFDO

Authors Wei Li, Lu Liu, Yue Yang, C. T. Chong

Publication date 2 August 2021

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

Ramsey's theorem for pairsreverse mathematicstree theorem for pairsweak König's lemmaweak weak König's lemmaWKLWWKL

Mathematics Subject Classification ID

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

Abstract: Let $mathsf{TT}_k^2$ denote the combinatorial principle stating that every $k$-coloring of pairs of compatible nodes in the full binary tree has a homogeneous solution, i.e. an isomorphic subtree in which all pairs of compatible nodes have the same color. Let $mathsf{WKL}_0$ be the subsystem of second order arithmetic consisting of the base system $mathsf{RCA}_0$ together with the principle (called Weak K"onig's Lemma) stating that every infinite subtree of the full binary tree has an infinite path. We show that over $mathsf{RCA}_0$, $mathsf{TT}_k^2$ doe not imply $mathsf{WKL}_0$. This solves the open problem on the relative strength between the two major subsystems of second order arithmetic.

Recommendations

• The strength of the tree theorem for pairs in reverse mathematics
• Reverse mathematics and Ramsey's property for trees
• On the strength of Ramsey's theorem for trees
• Coloring trees in reverse mathematics
• scientific article; zbMATH DE number 7377981

Cites work

• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• A survey on structural Ramsey theory and topological dynamics with the Kechris-Pestov-Todorcevic correspondence in mind
• Coloring subgraphs of the Rado graph
• Coloring trees in reverse mathematics
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Cone avoiding closed sets
• Controlling iterated jumps of solutions to combinatorial problems
• Edge partitions of the Rado graph
• scientific article; zbMATH DE number 3487493 (Why is no real title available?)
• Introduction to Ramsey space
• Iterative forcing and hyperimmunity in reverse mathematics
• Measure theory and weak König's lemma
• On the strength of Ramsey's theorem
• On the strength of Ramsey's theorem for pairs
• On the strength of Ramsey's theorem for trees
• Pigeons do not jump high
• Ramsey's theorem and recursion theory
• Ramsey's theorem for trees: the polarized tree theorem and notions of stability
• Reverse mathematics and Ramsey's property for trees
• Subsystems of second order arithmetic
• The inductive strength of Ramsey's theorem for pairs
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• The strength of the tree theorem for pairs in reverse mathematics

Cited in

(15)

• On the strength of Ramsey's theorem for trees
• Coloring trees in reverse mathematics
• Separating principles below \(\mathsf{WKL}_0\)
• The strength of the tree theorem for pairs in reverse mathematics
• Reverse mathematics, computability, and partitions of trees
• Finding paths through narrow and wide trees
• Graph Coloring and Reverse Mathematics
• Reverse mathematics and a Ramsey-type König's lemma
• Ramsey's theorem for pairs and \(k\) colors as a sub-classical principle of arithmetic
• The inductive strength of Ramsey's theorem for pairs
• Comparing DNR and WWKL
• Cone avoiding closed sets
• Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective
• The Ginsburg-Sands theorem and computability theory
• Ramsey's theorem and König's lemma

This page was built for publication: The strength of Ramsey's theorem for pairs over trees. I: Weak König's lemma

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