The Journal of Symbolic Logic

Research Article

Lower bounds for modal logics

Pavel Hrubeš

Mathematical Institute, Zitna 25, 11000 Praha 1, Czech Republic, E-mail: pahrubes@centrum.cz

Abstract

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 ψ1, ψ2, … 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 andS4. We also determine some speed-up relations between different systems of modal logic on formulas of modal-depth one.

(Received May 24 2006)

Key words and phrases

  • Proof complexity;
  • modal logic;
  • lower bound;
  • monotone interpolation