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  
  • The minimal e-degree problem in fragments of Peano arithmetic.M. M. Arslanov, C. T. Chong, S. B. Cooper & Y. Yang - 2005 - Annals of Pure and Applied Logic 131 (1-3):159-175.
    We study the minimal enumeration degree problem in models of fragments of Peano arithmetic () and prove the following results: in any model M of Σ2 induction, there is a minimal enumeration degree if and only if M is a nonstandard model. Furthermore, any cut in such a model has minimal e-degree. By contrast, this phenomenon fails in the absence of Σ2 induction. In fact, whether every Σ2 cut has minimal e-degree is independent of the Σ2 bounding principle.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
    		•