Switch to: References

Add citations

You must login to add citations.
  1. On Shavrukov’s Non-Isomorphism Theorem for Diagonalizable Algebras.Evgeny A. Kolmakov - 2024 - Review of Symbolic Logic 17 (1):206-243.
    We prove a strengthened version of Shavrukov’s result on the non-isomorphism of diagonalizable algebras of two $\Sigma _1$ -sound theories, based on the improvements previously found by Adamsson. We then obtain several corollaries to the strengthened result by applying it to various pairs of theories and obtain new non-isomorphism examples. In particular, we show that there are no surjective homomorphisms from the algebra $(\mathfrak {L}_T, \Box _T\Box _T)$ onto the algebra $(\mathfrak {L}_T, \Box _T)$. The case of bimodal diagonalizable algebras (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • 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.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • The intrinsic difficulty of recursive functions.F. W. Kroon - 1996 - Studia Logica 56 (3):427 - 454.
    This paper deals with a philosophical question that arises within the theory of computational complexity: how to understand the notion of INTRINSIC complexity or difficulty, as opposed to notions of difficulty that depend on the particular computational model used. The paper uses ideas from Blum's abstract approach to complexity theory to develop an extensional approach to this question. Among other things, it shows how such an approach gives detailed confirmation of the view that subrecursive hierarchies tend to rank functions in (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • Streamlined subrecursive degree theory.Lars Kristiansen, Jan-Christoph Schlage-Puchta & Andreas Weiermann - 2012 - Annals of Pure and Applied Logic 163 (6):698-716.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • The structure of the honest polynomial m-degrees.Rod Downey, William Gasarch & Michael Moses - 1994 - Annals of Pure and Applied Logic 70 (2):113-139.
    We prove a number of structural theorems about the honest polynomial m-degrees contingent on the assumption P = NP . In particular, we show that if P = NP , then the topped finite initial segments of Hm are exactly the topped finite distributive lattices, the topped initial segments of Hm are exactly the direct limits of ascending sequences of finite distributive lattices, and all recursively presentable distributive lattices are initial segments of Hm ∩ RE. Additionally, assuming ¦∑¦ = 1, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • 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 (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
    		•