Comparing DNR and WWKL
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.
- Finding paths through narrow and wide trees
- scientific article; zbMATH DE number 2236635
- The strength of Ramsey's theorem for pairs over trees. I: Weak König's lemma
- Partial impredicativity in reverse mathematics
- scientific article; zbMATH DE number 2019844
- Reverse mathematics, countable and uncountable
- Vitali's theorem and WWKL
- Graph Coloring and Reverse Mathematics
- The cohesive principle and the Bolzano-Weierstraß principle
- scientific article; zbMATH DE number 2236636
- Refining the taming of the reverse mathematics zoo
- On the uniform computational content of computability theory
- Extracting randomness within a subset is hard
- Comparing the strength of diagonally nonrecursive functions in the absence of _2⁰ induction
- On uniform relationships between combinatorial problems
- DNR and incomparable Turing degrees
- Diagonally non-computable functions and bi-immunity
- Lowness notions, measure and domination
- Mass problems and initial segment complexity
- Separating principles below \(\mathsf{WKL}_0\)
- Effective bi-immunity and randomness
- Turing Degrees and Muchnik Degrees of Recursively Bounded DNR Functions
- 2010 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '10
- A strong law of computationally weak subsets
- Open questions in reverse mathematics
- Degrees of unsolvability: a tutorial
- Mass Problems and Randomness
- MASS PROBLEMS AND HYPERARITHMETICITY
- Finding paths through narrow and wide trees
- Propagation of partial randomness
- On the logical strengths of partial solutions to mathematical problems
- A DNC function that computes no effectively bi-immune set
- The computational content of nonstandard analysis
- Diagonally non-computable functions and fireworks
- Partial impredicativity in reverse mathematics
- Forcing with bushy trees
- Cone avoiding closed sets
- Mass problems associated with effectively closed sets
- Ramsey-type graph coloring and diagonal non-computability
- Subsystems of second-order arithmetic between \(\text{RCA}_{0}\) and \(\text{WKL}_{0}\)
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)