Propositional modal logic: infinite models required in systems with finite model property?

621 Views Asked by At

A system of propositional modal logic has the "finite model property" if any consistent sentence is satisfiable at a model with finitely many possible worlds. Some systems have this property and others do not.

An infinite set of sentences is consistent if each of its finite subsets is consistent.

For systems that do have the finite model property, are there infinite consistent sets of sentences which are not satisfiable by a finite model? What is an example of such a set, for some system?

1

There are 1 best solutions below

2
On BEST ANSWER

If we use the definitions in the question, the answer is yes. Take any common propositional modal logic (e.g. S5) that has the finite model property for sentences. Work in a language with infinitely many propositional variables $X_i$, and consider the set $T$ of sentences that contains, for every finite set $D$ of propositional variables and every function $s \colon D \to \{+,-\}$, the formula $$ \Box \left ( \bigwedge_{X_i \in D} s(X_i) X_i \right) $$ where $+X_i$ is $X_i$ and $-X_i$ is $\lnot X_i$. For example, when $D = \{A,B,C\}$, we get 8 sentences $$ \Box(A\land B \land C)\\ \Box(A\land B \land \lnot C)\\ \Box(A\land \lnot B \land C)\\ \Box(A\land \lnot B \land \lnot C)\\ \Box(\lnot A\land B \land C)\\ \Box(\lnot A\land B \land \lnot C)\\ \Box(\lnot A\land \lnot B \land C)\\ \Box(\lnot A\land \lnot B \land \lnot C) $$

The infinite set of sentences $T$ is consistent (certainly every finite subset is consistent). But there is no finite Kripke frame that satisfies the entire set, because if we just look at just the sentences involving some finite subset $D$ of the propositional variables, the model will have to contain at least $2^{|D|}$ worlds.