Comparing DNR and WWKL

DOI10.2178/JSL/1102022212MaRDI QIDQ5311768zbMATH OpenOpenAlexWikidataFDO

Authors Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp, Theodore A. Slaman

Publication date 29 August 2005

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

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

zbMATH Keywords

diagonally nonrecursiveMartin-Löf randomnessreverse mathematicsweak weak König's lemma

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Other Turing degree structures (03D28) Second- and higher-order arithmetic and fragments (03F35)

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

Recommendations

• 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

Cited in

(30)

• 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)