How many models are there, for a particular propositional modal logic? - MathOverflow

How many models are there, for a particular propositional modal logic?

2010-12-22T21:41:10Z

Background/motivation: A model for the classical propositional calculus is a boolean function b(S) which assigns 1 or 0 to each (modal-free) sentence S according to the usual rules. I'm looking at models for propositional modal logic, where a modal model is simply a collection of classical models as points. These simplified models make no use of a relation R that holds between points, nor of any one point as designated. How many modal models are there? I have two answers:

1) There are continuously many (c) classical models. Since any subset of the collection of classical models is a modal model, there are (2^c) > c modal models.

2) Suppose that for any given collection B = {b1, b2, ...} of classical models, the product of the collection B is defined as a function f(S) such that for each sentence S:

f(S) = 1 iff bi(S) = 1 for all bi ∈ B;
f(S) = 0 iff bi(S) = 0 for all bi ∈ B;
f(S) = -1 otherwise.

Since the function f(S) has a countable infinity of inputs and only finitely many outputs, it appears there are continuously many such functions. (Perhaps this assumes AC?)

The two answers can be reconciled if two different collections B1 and B2 of classical models both define the same function f(S). But I don't see how that's possible. So there's something I'm missing.

Answer by Andreas Blass for How many models are there, for a particular propositional modal logic?

2010-12-23T15:11:26Z

You've shown that there are $2^c$ models $B$ but only $c$ corresponding functions $f$, so indeed many $B$'s must yield the same $f$. Since you say you don't see how it's possible for even two $B$'s to yield the same $f$, here's an example. Consider the countably many sentences $S$ such that neither $S$ nor its negation is a tautology. For each such $S$, choose one classical model $Y(S)$ in which $S$ is true and one classical model $N(S)$ in which $S$ is false. Let $B$ be the set of all these $Y(S)$'s and $N(S)$'s. The corresponding $f$ maps each of these $S$'s to $-1$ (and it maps tautologies to 1 and the rest of the sentences, those whose negations are tautologies, to 0). Note that $B$ is countable (as it has just two members $Y(S)$ and $N(S)$ for each of countably many sentences $S$), so there are plenty of classical models not in $B$. Now let $B'$ be the union of $B$ with any nonempty subcollection of these other classical models. Then the $f$ associated to $B'$ is the same as that associated to $B$.

Answer by Sam Alexander for How many models are there, for a particular propositional modal logic?

2011-06-04T19:23:23Z

Of course, this is all assuming the original language (before augmentation by modal operators) was countable. It could be that we have a language with 2^c, or 2^2^c, or whatever, propositional atoms, which would of course drastically change the answer.

By the way, the most general possible semantics is to simply treat the purely modal formulas as being atoms themselves. Rather than defining a model for a propositional language as a function which assigns truth values to all formulas, define it to be a function which assigns truth values to atoms. This seems like a silly distinction, but it's important for what follows. If $L$ is a propositional language and $\mathscr{K}$ is a set of modal operators, define the propositional language $L(\mathscr{K})$ recursively as follows:

all the atoms of $L$ are atoms of $L(\mathscr{K})$
for any $K\in\mathscr{K}$ and any sentence $\phi$ of $L(\mathscr{K})$, $K(\phi)$ is an atom of $L(\mathscr{K})$.

Now we can do modal logic just like we do propositional logic. A model for a modal language is just a truth assignment for the atoms (which atoms include purely modal sentences).