Switch to: References

Add citations

You must login to add citations.
  1. Comparing the strength of diagonally nonrecursive functions in the absence of induction.François G. Dorais, Jeffry L. Hirst & Paul Shafer - 2015 - Journal of Symbolic Logic 80 (4):1211-1235.
    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$.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Notes on Sacks’ Splitting Theorem.Klaus Ambos-Spies, Rod G. Downey, Martin Monath & N. G. Keng Meng - forthcoming - Journal of Symbolic Logic.
    We explore the complexity of Sacks’ Splitting Theorem in terms of the mind change functions associated with the members of the splits. We prove that, for any c.e. set A, there are low computably enumerable sets $A_0\sqcup A_1=A$ splitting A with $A_0$ and $A_1$ both totally $\omega ^2$ -c.a. in terms of the Downey–Greenberg hierarchy, and this result cannot be improved to totally $\omega $ -c.a. as shown in [9]. We also show that if cone avoidance is added then there (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
    		•