Switch to: References

Add citations

You must login to add citations.
  1. Semi-honest subrecursive degrees and the collection rule in arithmetic.Andrés Cordón-Franco & F. Félix Lara-Martín - 2023 - Archive for Mathematical Logic 63 (1):163-180.
    By a result of L.D. Beklemishev, the hierarchy of nested applications of the $$\Sigma _1$$ -collection rule over any $$\Pi _2$$ -axiomatizable base theory extending Elementary Arithmetic collapses to its first level. We prove that this result cannot in general be extended to base theories of arbitrary quantifier complexity. In fact, given any recursively enumerable set of true $$\Pi _2$$ -sentences, S, we construct a sound $$(\Sigma _2 \! \vee \! \Pi _2)$$ -axiomatized theory T extending S such that the (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Computable irrational numbers with representations of surprising complexity.Ivan Georgiev, Lars Kristiansen & Frank Stephan - 2021 - Annals of Pure and Applied Logic 172 (2):102893.
    Download  
     
    Export citation  
     
    Bookmark  
  • Proof lengths for instances of the Paris–Harrington principle.Anton Freund - 2017 - Annals of Pure and Applied Logic 168 (7):1361-1382.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Honest elementary degrees and degrees of relative provability without the cupping property.Paul Shafer - 2017 - Annals of Pure and Applied Logic 168 (5):1017-1031.
    Download  
     
    Export citation  
     
    Bookmark  
  • Degrees of total algorithms versus degrees of honest functions.Lars Kristiansen - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 422--431.
    Download  
     
    Export citation  
     
    Bookmark  
  • Degrees of Relative Provability.Mingzhong Cai - 2012 - Notre Dame Journal of Formal Logic 53 (4):479-489.
    There are many classical connections between the proof-theoretic strength of systems of arithmetic and the provable totality of recursive functions. In this paper we study the provability strength of the totality of recursive functions by investigating the degree structure induced by the relative provability order of recursive algorithms. We prove several results about this proof-theoretic degree structure using recursion-theoretic techniques such as diagonalization and the Recursion Theorem.
    Download  
     
    Export citation  
     
    Bookmark   3 citations