Finding paths through narrow and wide trees. (English) Zbl 1161.03035

The authors introduce two statements which are restrictions of Weak König’s Lemma to subclasses of the \(0\)-\(1\) trees. A node \(\sigma\) in a tree \(T\) is called extendible if the set of its extensions is infinite. It is called a branching node if both \(\sigma 0\) and \(\sigma 1\) are extendible. The axiom DIM asserts that if \(T\) is an infinite \(0\)-\(1\) tree and there is no function \(f\) such that every extendible \(\sigma\) has a branching extension of length no more than \(f(|\sigma |)\), then \(T\) has an infinite path. Since branching nodes are rare in such trees, we can think of DIM as a restriction of WKL\(_0\) to narrow trees.
The statement VSMALL is a restriction of WKL\(_0\) to a smaller subclass of narrow trees. Working over RCA\(_0\), the base system for the program of reverse mathematics, the authors show that both DIM and VSMALL are independent of both WWKL (Weak Weak König’s Lemma) and DNR. More about the relationship between WWKL and DNR can be found in [K. Ambos-Spies, B. Kjos-Hanssen, S. Lempp and T. A. Slaman, “Comparing DNR and WWKL”, J. Symb. Log. 69, No. 4, 1089–1104 (2004; Zbl 1076.03039)], for example.


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


Zbl 1076.03039
Full Text: DOI arXiv


[1] DOI: 10.1007/s001530100100 · Zbl 1030.03044 · doi:10.1007/s001530100100
[2] Comparing DNR and WWKL 69 pp 1089– (2004) · Zbl 1076.03039
[3] Recursively Enumerable Sets and Degrees (1987)
[4] Subsystems of second order arithmetic (1999) · Zbl 0909.03048
[5] Simplicity of recursively enumerable sets 32 pp 162– (1967)
[6] Notre Dame Journal of Formal Logic V pp 10– (1964)
[7] Uniform almost everywhere domination 71 pp 1057– (2006)
[8] An introduction to Kolmogorov complexity and its applications (1997) · Zbl 0866.68051
[9] Measure, classes and complete extensions of PA pp 245– (1985)
[10] Kolmogorov complexity and the recursion theorem 3884 (2006) · Zbl 1137.03026
[11] DOI: 10.1090/S0002-9947-1968-0227009-1 · doi:10.1090/S0002-9947-1968-0227009-1
[12] Transactions of the American Mathematical Society 173 pp 35– (1972) · Zbl 0247.00014
[13] Recursion Theory Week 1141 (1985)
[14] Classical recursion theory 1 (1950)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.