Comparing DNR and WWKL

From MaRDI portal



Abstract: In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0 (weak weak K"onig's Lemma).


This paper employs computability-theoretic techniques to answer a question originally asked in the context of reverse mathematics (\textit{S.~G. Simpson}'s book [Subsystems of second order arithmetic. Springer, Berlin (1999; Zbl 0909.03048)] is the main reference in this area). \textit{X. Yu} and \textit{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 \textit{D. K. Brown, M. Giusto} and \textit{S.~G. Simpson} [Arch. Math. Logic 41, 191--206 (2002; Zbl 1030.03044)]. \textit{M. Giusto} and \textit{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.




Cited in
(30)








This page was built for publication: Comparing DNR and WWKL

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