Completeness Proof by Semantic Diagrams for Transitive Closure of Accessibility Relation.
Ryo Kashima · Advances in Modal Logic · 2010
We treat the smallest normal modal propositional logic with two modal operators 2 and 2+. While 2 is interpreted in Kripke models by the accessibility relation R, 2+ is interpreted by the transitive closure of R. Intuitively the formula 2+φ means the infinite conjunction 2φ ∧ 22φ ∧ 222φ ∧ · · · . There is a Hilbert style axiomatization of this logic (a characteristic axiom is 2φ ∧ 2+(φ → 2φ) → 2+φ, called “induction axiom”), and its completeness with respect to finite models was shown by the canonical model method. This paper gives an alternative proof of this completeness. We use the method of “semantic diagram”, which is a variant of semantic tableaux, as follows. Given an unprovable formula φ, we first make a small model (consisting of one world that forces φ to be false); then we add worlds step by step using the Hilbert system as an oracle, and finally we get a finite countermodel for φ. The point is how to handle 2+ in this construction.