Journal of Symbolic Logic 80 (4):1211-1235 (2015)
Abstract |
We prove that the statement “there is aksuch that for everyfthere is ak-bounded diagonally nonrecursive function relative tof” does not imply weak König’s lemma over${\rm{RC}}{{\rm{A}}_0} + {\rm{B\Sigma }}_2^0$. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that everyk-bounded diagonally nonrecursive function computes a 2-bounded diagonally nonrecursive function may fail in the absence of${\rm{I\Sigma }}_2^0$.
|
Keywords | No keywords specified (fix it) |
Categories | (categorize this paper) |
DOI | 10.1017/jsl.2015.43 |
Options |
![]() ![]() ![]() ![]() |
Download options
References found in this work BETA
Measure Theory and Weak König's Lemma.Xiaokang Yu & Stephen G. Simpson - 1990 - Archive for Mathematical Logic 30 (3):171-180.
Metamathematics of First-Order Arithmetic.Petr Hajék & Pavel Pudlák - 1994 - Studia Logica 53 (3):465-466.
Nonstandard Models in Recursion Theory and Reverse Mathematics.C. T. Chong, Wei Li & Yue Yang - 2014 - Bulletin of Symbolic Logic 20 (2):170-200.
Reverse Mathematics and Recursive Graph Theory.William Gasarch & Jeffry L. Hirst - 1998 - Mathematical Logic Quarterly 44 (4):465-473.
∑2 Induction and Infinite Injury Priority Arguments, Part II Tame ∑2 Coding and the Jump Operator.C. T. Chong & Yue Yang - 1997 - Annals of Pure and Applied Logic 87 (2):103-116.
View all 6 references / Add more references
Citations of this work BETA
Reverse Mathematics and Colorings of Hypergraphs.Caleb Davis, Jeffry Hirst, Jake Pardo & Tim Ransom - 2019 - Archive for Mathematical Logic 58 (5-6):575-585.
Forcing with Bushy Trees.Mushfeq Khan & Joseph S. Miller - 2017 - Bulletin of Symbolic Logic 23 (2):160-180.
Similar books and articles
Comparing DNR and WWKL.Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp & Theodore A. Slaman - 2004 - Journal of Symbolic Logic 69 (4):1089-1104.
On a Theory for AC0 and the Strength of the Induction Scheme.Satoru Kuroda - 1998 - Mathematical Logic Quarterly 44 (3):417-426.
A Note on Bar Induction in Constructive Set Theory.Michael Rathjen - 2006 - Mathematical Logic Quarterly 52 (3):253-258.
Diagonally Non-Computable Functions and Bi-Immunity.Carl G. Jockusch & Andrew E. M. Lewis - 2013 - Journal of Symbolic Logic 78 (3):977-988.
Some Theories with Positive Induction of Ordinal Strength Φω.Gerhard Jäger & Thomas Strahm - 1996 - Journal of Symbolic Logic 61 (3):818-842.
On the Computability of Fractal Dimensions and Hausdorff Measure.Ker-I. Ko - 1998 - Annals of Pure and Applied Logic 93 (1-3):195-216.
Can There Be No Nonrecursive Functions?Joan Rand Moschovakis - 1971 - Journal of Symbolic Logic 36 (2):309-315.
Nonrecursive Combinatorial Functions.Erik Ellentuck - 1972 - Journal of Symbolic Logic 37 (1):90-95.
Degrees of Difficulty of Generalized R.E. Separating Classes.Douglas Cenzer & Peter G. Hinman - 2008 - Archive for Mathematical Logic 46 (7-8):629-647.
Some Theories with Positive Induction of Ordinal Strength $Varphiomega 0$.Gerhard Jager & Thomas Strahm - 1996 - Journal of Symbolic Logic 61 (3):818-842.
Induction and Inductive Definitions in Fragments of Second Order Arithmetic.Klaus Aehlig - 2005 - Journal of Symbolic Logic 70 (4):1087 - 1107.
The Role of Parameters in Bar Rule and Bar Induction.Michael Rathjen - 1991 - Journal of Symbolic Logic 56 (2):715-730.
Zwakheid En Kracht (2 Korinthiërs 12, 1-13)-Weakness and Strength (2 Corinthians 12: 1-13).Jan Lambrecht - 2005 - Bijdragen 66 (3):326-340.
Analytics
Added to PP index
2016-06-30
Total views
17 ( #639,019 of 2,519,575 )
Recent downloads (6 months)
1 ( #407,153 of 2,519,575 )
2016-06-30
Total views
17 ( #639,019 of 2,519,575 )
Recent downloads (6 months)
1 ( #407,153 of 2,519,575 )
How can I increase my downloads?
Downloads