Switch to: References

Add citations

You must login to add citations.
  1. End-extensions of models of weak arithmetic from complexity-theoretic containments.Leszek Aleksander Kołodziejczyk - 2016 - Journal of Symbolic Logic 81 (3):901-916.
    We prove that if the linear-time and polynomial-time hierarchies coincide, then every model of Π1 + ¬Ω1has a proper end-extension to a model of Π1, and so Π1 + ¬Ω ⊢ BΣ1. Under an even stronger complexity-theoretic assumption which nevertheless seems hard to disprove using present-day methods, Π1 + ¬Exp ⊢ BΣ1. Both assumptions can be modified to versions which make it possible to replace Π1 by IΔ0as the base theory.We also show that any proof that IΔ0+ ¬Exp does not (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • 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