Switch to: Citations

Add references

You must login to add references.
  1. Multifunction algebras and the provability of PH↓.Chris Pollett - 2000 - Annals of Pure and Applied Logic 104 (1-3):279-303.
    We introduce multifunction algebras B i τ where τ is a set of 0 or 1-ary terms used to bound recursion lengths. We show that if for all ℓ ∈ τ we have ℓ ∈ O then B i τ = FP Σ i−1 p , those multifunctions computable in polynomial time with at most O )) queries to a Σ i−1 p witness oracle for ℓ ∈ τ and p a polynomial. We use our algebras to obtain independence results (...)
    Download  
     
    Export citation  
     
    Bookmark   12 citations  
  • A Model‐Theoretic Property of Sharply Bounded Formulae, with some Applications.Jan Johannsen - 1998 - Mathematical Logic Quarterly 44 (2):205-215.
    We define a property of substructures of models of arithmetic, that of being length-initial, and show that sharply bounded formulae are absolute between a model and its length-initial submodels. We use this to prove independence results for some weak fragments of bounded arithmetic by constructing appropriate models as length-initial submodels of some given model.
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • A Non-Standard Model for a Free Variable Fragment of Number Theory.J. C. Shepherdson - 1965 - Journal of Symbolic Logic 30 (3):389-390.
    Download  
     
    Export citation  
     
    Bookmark   17 citations  
  • The strength of sharply bounded induction.Emil Jeřábek - 2006 - Mathematical Logic Quarterly 52 (6):613-624.
    We prove that the sharply bounded arithmetic T02 in a language containing the function symbol ⌊x /2y⌋ is equivalent to PV1.
    Download  
     
    Export citation  
     
    Bookmark   11 citations