6 found
Sort by:
  1. Pavel Hrubeš (2009). Kreisel's Conjecture with Minimality Principle. Journal of Symbolic Logic 74 (3):976-988.
    We prove that Kreisel's Conjecture is true, if Peano arithmetic is axiomatised using minimality principle and axioms of identity (theory $PA_M $ )-The result is independent on the choice of language of $PA_M $ . We also show that if infinitely many instances of A(x) are provable in a bounded number of steps in $PA_M $ then there existe k ∈ ω s. t. $PA_M $ ┤ ∀x > k̄ A(x). The results imply that $PA_M $ does not prove scheme (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  2. Pavel Hrubeš (2009). On Lengths of Proofs in Non-Classical Logics. Annals of Pure and Applied Logic 157 (2):194-205.
    We give proofs of the effective monotone interpolation property for the system of modal logic K, and others, and the system IL of intuitionistic propositional logic. Hence we obtain exponential lower bounds on the number of proof-lines in those systems. The main results have been given in [P. Hrubeš, Lower bounds for modal logics, Journal of Symbolic Logic 72 941–958; P. Hrubeš, A lower bound for intuitionistic logic, Annals of Pure and Applied Logic 146 72–90]; here, we give considerably simplified (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  3. Gregory L. Cherlin, Ilijas Farah, Pavel Hrubes, Victor Marek, Jan Riemann, Simon Thomas & Jeffrey Remmel (2008). San Diego Convention Center, San Diego, CA January 8–9, 2008. Bulletin of Symbolic Logic 14 (3).
    Direct download  
     
    My bibliography  
     
    Export citation  
  4. Pavel Hrubeš (2007). A Lower Bound for Intuitionistic Logic. Annals of Pure and Applied Logic 146 (1):72-90.
    We give an exponential lower bound on the number of proof-lines in intuitionistic propositional logic, IL, axiomatised in the usual Frege-style fashion; i.e., we give an example of IL-tautologies A1,A2,… s.t. every IL-proof of Ai must have a number of proof-lines exponential in terms of the size of Ai. We show that the results do not apply to the system of classical logic and we obtain an exponential speed-up between classical and intuitionistic logic.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5. Pavel Hrubeš (2007). Lower Bounds for Modal Logics. Journal of Symbolic Logic 72 (3):941 - 958.
    We give an exponential lower bound on number of proof-lines in the proof system K of modal logic, i.e., we give an example of K-tautologies ψ₁, ψ₂,... s.t. every K-proof of ψi must have a number of proof-lines exponential in terms of the size of ψi. The result extends, for the same sequence of K-tautologies, to the systems K4, Gödel—Löb's logic, S and S4. We also determine some speed-up relations between different systems of modal logic on formulas of modal-depth one.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. Pavel Hrubeš (2007). Theories Very Close to PA Where Kreisel's Conjecture Is False. Journal of Symbolic Logic 72 (1):123 - 137.
    We give four examples of theories in which Kreisel's Conjecture is false: (1) the theory PA(-) obtained by adding a function symbol minus, '−', to the language of PA, and the axiom ∀x∀y∀z (x − y = z) ≡ (x = y + z ⋁ (x < y ⋀ z = 0)); (2) the theory T of integers; (3) the theory PA(q) obtained by adding a function symbol q (of arity ≥ 1) to PA, assuming nothing about q; (4) the (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation