Loop-free construction of counter-models in intuitionistic propositional logic
Luís Pinto, Roy Dyckhoff · 1995
. We present a non-looping method to construct Kripke trees refuting the nontheorems of intuitionistic propositional logic, using a contraction-free sequent calculus. 1991 Mathematics Subject Classification: 03B20, 03B35, 03C25, 03F03, 68T15 1. Introduction It is well known that IPL (Intuitionistic Propositional Logic) has the finite model property; in fact, any non-theorem of IPL can be invalidated by means of a finite Kripke tree [2]. The standard method (see [9] for a formal treatment) for constructing such counter-models requires a loop-checker. Here, we present a method for constructing counter-models not requiring a loop-checker, based on the contractionfree sequent calculi LJT and LJT* [1]. LJT provides a very simple but reasonably effective decision procedure for IPL. The ideas were first presented in the work of Vorob'ev [10] and more recently also in [3] and [5]. LJT differs from traditional formulations of Gentzen sequent calculi for IPL only in the rule oe) for introduct...