0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I think not, it sounds a bit against the definition, but am unable to proof it , ps "An infinite set of sentences is consistent if each of its finite subsets is consistent." is not true (and rather impossible as well , there is no "each of its subsets", i guess you mean "if an infinite set of sentences is inconsistent then one of its finite subsets is inconsistent." which is true $\endgroup$ – Willemien Mar 12 '14 at 8:20
  • $\begingroup$ @Willemien: when I read "An infinite set of sentences is consistent if each of its finite subsets is consistent." it makes perfect sense as a mathematics sentence in English; it means the same as "An infinite set of sentences is consistent if all of its finite subsets are consistent." I don't think the original sentence is remarkable. $\endgroup$ – Carl Mummert Mar 12 '14 at 10:53
  • $\begingroup$ @Willemien - why "impossible" ? It is compactness. Moreover, let $\Sigma = \{ \sigma_i \}$ infinite; assume that "if $\lnot Cons(\Sigma)$, then $\exists \Gamma \subset \Sigma$, such that $\lnot Cons(\Gamma)$" is true, then, by contraposition : "if $\forall \Gamma$, $Cons(\Gamma)$, then $Cons(\Sigma)$" must also br true. $\endgroup$ – Mauro ALLEGRANZA Mar 12 '14 at 10:55
  • $\begingroup$ @CarlMummert in't there a problem that all finite subsets of an infinite set are not enumerable, so how can you even start checking their consistency? $\endgroup$ – Willemien Mar 12 '14 at 17:54
  • $\begingroup$ @Willemien: who said anything about enumerating the subsets? The compactness theorem in the form I know it simply says that a theory is consistent if and only if each of its finite subsets is consistent. This does not presume that we have a way to effectively determine the consistency of even one finite subset, much less of all of them. $\endgroup$ – Carl Mummert Mar 12 '14 at 19:24
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, that's right. After thinking about it some more I believe I found a similar example. Thanks. $\endgroup$ – MikeC Mar 12 '14 at 16:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.