Lower bounds for modal logics

摘要

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 psi(1), psi(2),... s.t. every K-proof of psi(i) must have a number of proof-lines exponential in terms of the size of psi(i). The result extends, for the same sequence of K-tautologies, to the systems K4, Godel-Lob's logic, S and S4. We also deter-mine some speed-up relations between different systems of modal logic on formulas of modal-depth one.