MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
If your definitions for "classical model" and "modal model" are correct, then this isn't a research level question: (1) would obviously the correct answer (assuming you have countably many propositional variables) and (2) has no relevance. If your definitions aren't correct, then that's the first thing that needs to be fixed. – Amit Kumar Gupta Dec 23 '10 at 0:20
Amit: Yes, I think the question in the title is not really what I was asking. My bad (as young folks in the USA say these days); sorry. – MikeC Dec 23 '10 at 16:22
After reading Andreas' answer, now I see what the point of your question was. If f is the function associated to some modal model, f(S) = 1 if S is necessary, f(S) = 0 if S is necessarily not the case, and f(S) = -1 if S is possibly true and possibly false, i.e. true in some possible worlds (classical models in your modal model) and false in others. However, f(S) = -1 could occur when S is true in one classical model and false in infinitely many, or true in 5 and false in 2, or true and false in infinitely many, etc. – Amit Kumar Gupta Dec 23 '10 at 20:51
Amit: that's right. Actually I think of the third value as "undefined", and of f(S) as a partial function rather than a total one. Kleene's idea, not mine, borrowed from Ch. XII Section 64, "The 3-valued logic", of his "Introduction to Metamathematics". – MikeC Dec 24 '10 at 4:33
up vote 4 down vote accepted

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$.

share|cite|improve this answer
Thanks, Andreas. The concept I was groping for, I think, was just that of elementary equivalence. The 2^c models fall into c equivalence classes. Each equivalence class defines one function. Assuming the function can be used to provide an adequate definition of satisfaction, we then can then say two models are elementarily equivalent if they satisfy all & only the same sentences. I missed this partly because I couldn't come up with an example like yours (and partly because we don't usually need to talk about elementary equivalence in propostional logic). – MikeC Dec 23 '10 at 16:18

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:

  1. all the atoms of $L$ are atoms of $L(\mathscr{K})$

  2. 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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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