COMPARING THE STRENGTH OF DIAGONALLY NONRECURSIVE FUNCTIONS IN THE ABSENCE OF INDUCTION

DOI10.1017/jsl.2015.43zbMath1373.03016arXiv1401.3823OpenAlexW2964177411WikidataQ59895724 ScholiaQ59895724MaRDI QIDQ2795915

François G. Dorais, Paul Shafer, Jeffry L. Hirst

Publication date: 22 March 2016

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

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

zbMATH Keywords

graph colouringreverse mathematicsnonstandard models of arithmeticWKLDNRdiagonally nonrecursive functions

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

Ramsey-type graph coloring and diagonal non-computability, On the uniform computational content of computability theory, FORCING WITH BUSHY TREES, Diagonally non-computable functions and fireworks, Reverse mathematics and colorings of hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• \(\varPi^1_1\)-conservation of combinatorial principles weaker than Ramsey's theorem for pairs
• \(\Sigma_ 2\) induction and infinite injury priority arguments. II. Tame \(\Sigma_ 2\) coding and the jump operator
• Measure theory and weak König's lemma
• NONSTANDARD MODELS IN RECURSION THEORY AND REVERSE MATHEMATICS
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• Reverse Mathematics and Recursive Graph Theory
• Graph Coloring and Reverse Mathematics
• Σ_{𝑛}-bounding and Δ_{𝑛}-induction
• Class groups of integral group rings
• \(\Sigma_2\) induction and infinite injury priority arguments. III: Prompt sets, minimal pairs and Shoenfield's conjecture