How many models are there, for a particular propositional modal logic? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T06:39:01Z http://mathoverflow.net/feeds/question/50196 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/50196/how-many-models-are-there-for-a-particular-propositional-modal-logic How many models are there, for a particular propositional modal logic? Michael Carroll 2010-12-22T21:41:10Z 2011-06-04T19:23:23Z <p><strong>Background/motivation:</strong> A model for the <strong>classical</strong> propositional calculus is a boolean function <em>b(S)</em> which assigns 1 or 0 to each (modal-free) sentence <em>S</em> according to the usual rules. I'm looking at models for propositional <strong>modal</strong> 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:</p> <p>1) There are continuously many (<em>c</em>) classical models. Since any subset of the collection of classical models is a modal model, there are <em>(2^c) > c</em> modal models.</p> <p>2) Suppose that for any given collection <em>B</em> = {<em>b1</em>, <em>b2</em>, ...} of classical models, the product of the collection <em>B</em> is defined as a function <em>f(S)</em> such that for each sentence <em>S</em>:</p> <ul> <li><em>f(S)</em> = 1 iff <em>bi(S)</em> = 1 for all <em>bi</em> ∈ B;</li> <li><em>f(S)</em> = 0 iff <em>bi(S)</em> = 0 for all <em>bi</em> ∈ B;</li> <li><em>f(S)</em> = -1 otherwise.</li> </ul> <p>Since the function <em>f(S)</em> has a countable infinity of inputs and only finitely many outputs, it appears there are continuously many such functions. (Perhaps this assumes AC?)</p> <p>The two answers can be reconciled if two different collections <em>B1</em> and <em>B2</em> of classical models both define the same function <em>f(S)</em>. But I don't see how that's possible. So there's something I'm missing.</p> http://mathoverflow.net/questions/50196/how-many-models-are-there-for-a-particular-propositional-modal-logic/50244#50244 Answer by Andreas Blass for How many models are there, for a particular propositional modal logic? Andreas Blass 2010-12-23T15:11:26Z 2010-12-23T15:11:26Z <p>You've shown that there are <code>$2^c$</code> 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$.</p> http://mathoverflow.net/questions/50196/how-many-models-are-there-for-a-particular-propositional-modal-logic/66912#66912 Answer by Sam Alexander for How many models are there, for a particular propositional modal logic? Sam Alexander 2011-06-04T19:23:23Z 2011-06-04T19:23:23Z <p>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.</p> <p>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 <em>atoms</em>. 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:</p> <ol> <li><p>all the atoms of $L$ are atoms of $L(\mathscr{K})$</p></li> <li><p>for any $K\in\mathscr{K}$ and any sentence $\phi$ of $L(\mathscr{K})$, $K(\phi)$ is an atom of $L(\mathscr{K})$.</p></li> </ol> <p>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).</p>