Finding paths through narrow and wide trees

DOI10.2178/JSL/1231082316MaRDI QIDQ3616357zbMATH OpenOpenAlexFDO

Authors Stephen Binns, Bjørn Kjos-Hanssen

Publication date 25 March 2009

Published in Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

König's Lemmareverse mathematicstreeWKLWWKL

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35)

Abstract: We consider two axioms of second-order arithmetic. These axioms assert, in two different ways, that infinite but narrow binary trees always have infinite paths. We show that both axioms are strictly weaker than Weak K"onig's Lemma, and incomparable in strength to the dual statement (WWKL) that wide binary trees have paths.

Recommendations

• Comparing DNR and WWKL
• Another unique weak König's lemma WKL!!
• The cohesive principle and the Bolzano-Weierstraß principle
• On uniform weak König's lemma
• The strength of Ramsey's theorem for pairs over trees. I: Weak König's lemma
• Partial impredicativity in reverse mathematics
• Leaf management
• König's lemma, the ω-Rule and primitive recursive arithmetic
• Proof-theoretic investigations on Kruskal's theorem
• The strength of the tree theorem for pairs in reverse mathematics

Cites work

• Class groups of integral group rings
• Comparing DNR and WWKL
• scientific article; zbMATH DE number 1226875 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• Vitali's theorem and WWKL

Cited in

(7)

• Unified characterizations of lowness properties via Kolmogorov complexity
• On effectively closed sets of effective strong measure zero
• A Cappable Almost Everywhere Dominating Computably Enumerable Degree
• Leaf management
• Comparing DNR and WWKL
• Short Tours through Large Linear Forests
• Pathwise-randomness and models of second-order arithmetic

This page was built for publication: Finding paths through narrow and wide trees

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