×

Comparing DNR and WWKL. (English) Zbl 1076.03039

This paper employs computability-theoretic techniques to answer a question originally asked in the context of reverse mathematics (S. G. Simpson’s book [Subsystems of second order arithmetic. Springer, Berlin (1999; Zbl 0909.03048)] is the main reference in this area).
X. Yu and S. G. Simpson [Arch. Math. Logic 30, 171–180 (1990; Zbl 0718.03043)] defined the system \(\mathbf{WWKL}_0\) and showed that it is equivalent to some statements about Lebesgue measure. The main axiom of \(\mathbf{WWKL}_0\) states that if a tree \(T \subseteq 2^{<\omega}\) has no path then \(\lim_{n \to \infty} | T \cap 2^n| \cdot 2^{-n} = 0\). The importance of \(\mathbf{WWKL}_0\) for the reverse mathematics of measure theory is further supported by results of D. K. Brown, M. Giusto and S. G. Simpson [Arch. Math. Logic 41, 191–206 (2002; Zbl 1030.03044)].
M. Giusto and S. G. Simpson [J. Symb. Log. 65, 1451–1480 (2000; Zbl 0967.03051)] studied different versions of the Tietze Extension Theorem and showed that one of them implies what they called the axiom \(\mathbf{DNR}\): for every \(A \subseteq \omega\) there exists a function \(f: \omega \to \omega\) which is diagonally nonrecursive in \(A\), i.e.such that \(f(n) \neq \varphi_n^A (n)\) for every \(n\). They noticed that \(\mathbf{WWKL}_0\) implies \(\mathbf{DNR}\) and that the latter is not provable in the base system \(\mathbf{RCA}_0\). Giusto and Simpson asked whether \(\mathbf{DNR}\) implies \(\mathbf{WWKL}_0\).
The paper under review answers this question in the negative by defining an \(\omega\)-model of \(\mathbf{RCA}_0 + \mathbf{DNR}\) where \(\mathbf{WWKL}_0\) fails (this implies that the result does not depend on the use of restricted induction). The problem is translated into the realm of computability theory by using the notion of Martin-Löf randomness: an \(\omega\)-model \(M\) satisfies \(\mathbf{WWKL}_0\) if and only if for every \(A \in M\) there exists \(B \in M\) which is Martin-Löf random relative to \(A\).
The proof is based on some notions generalizing the ideas used in M. Kumabe’s unpublished proof of the existence of a fixed-point free minimal degree. The authors state a few corollaries of the proof about diagonally nonrecursive functions which are of independent interest.

MSC:

03F35 Second- and higher-order arithmetic and fragments
03D28 Other Turing degree structures
03B30 Foundations of classical theories (including reverse mathematics)
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Located sets and reverse mathematics 65 pp 1451–1480– (2000)
[2] Proceedings of the International Congress of Mathematicians (Vancouver, B. C, 1974), Vol. 1 pp 235–242– (1975)
[3] Archive for Mathematical Logic 41 pp 191–206– (2002)
[4] Computability theory and its applications (Boulder, CO, 1999) 257 pp 1–14– (2000)
[5] Logic, methodology and philosophy of science, VIII (Moscow, 1987) 126 pp 191–201– (1989)
[6] Archive for Mathematical Logic 30 pp 171–180– (1990)
[7] Notes on constructive mathematics (1970)
[8] Recursion theory week (Oberwolfach, 1984) 1141 pp 245–259– (1985)
[9] Subsystems of second order arithmetic (1999) · Zbl 0909.03048
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.