Comparing the strength of diagonally nonrecursive functions in the absence of induction

Journal of Symbolic Logic 80 (4):1211-1235 (2015)
  Copy   BIBTEX

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$.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 89,560

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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
2016-06-30

Downloads
19 (#674,556)

6 months
1 (#1,011,292)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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