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
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 56,949
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

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.
Reverse Mathematics and Recursive Graph Theory.William Gasarch & Jeffry L. Hirst - 1998 - Mathematical Logic Quarterly 44 (4):465-473.
Graph Coloring and Reverse Mathematics.James H. Schmerl - 2000 - Mathematical Logic Quarterly 46 (4):543-548.

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.

Add more citations

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.
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.
Realism and the Absence of Rivals.Finnur Dellsén - 2017 - Synthese 194 (7):2427-2446.
On Grzegorczyk Induction.Ch Cornaros - 1995 - Annals of Pure and Applied Logic 74 (1):1-21.
The Role of Parameters in Bar Rule and Bar Induction.Michael Rathjen - 1991 - Journal of Symbolic Logic 56 (2):715-730.

Analytics

Added to PP index
2016-06-30

Total views
17 ( #588,939 of 2,409,928 )

Recent downloads (6 months)
1 ( #541,494 of 2,409,928 )

How can I increase my downloads?

Downloads

My notes