Comparing the strength of diagonally non-recursive functions in the absence of Σ20Σ^0_2 induction

preprint2015arXivOpen access

Abstract

We prove that the statement "there is a kk such that for every ff there is a kk-bounded diagonally non-recursive function relative to ff" does not imply weak König's lemma over RCA0+BΣ20\mathrm{RCA}_0 + \mathrm{B}Σ^0_2. This answers a question posed by Simpson. A recursion-theoretic consequence is that the classic fact that every kk-bounded diagonally non-recursive function computes a 22-bounded diagonally non-recursive function may fail in the absence of IΣ20\mathrm{I}Σ^0_2.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.