Franklin's Notes


Possible sets of all models

Question. Given a set of sentence symbols $\mathscr{S}$ and a set of models $K\subset 2^{2^\mathscr{S}}$, how can we determine whether there exists a set of sentences $\Sigma$ such that $K$ is the set of all models of $\mathscr{S}$? (In philosophical terms, what kinds of sets can the "set of all possible worlds" be?)

Chang and Kiesler have a couple of exercises that have implications on this question. In each of the following exercises, $\mathscr{S}$ is taken to be a countable set of sentence symbols. Here are my attempts to solve them:

Exercise 1. (Chang and Kiesler, 1.2.9i) Prove that, for every finite set of models $K$, there is a set of sentences $\Sigma$ such that $K$ is the set of all models of $\Sigma$.

Solution. For each $i\in\mathbb{N}$, define $\mathscr{S}^{(i)}={S_1,...,S_i}$, if $\mathscr{S}={S_1,S_2,...}$ is the countably infinite set of sentence symbols. Further, if $K={A_1,...,A_n}$, define $A_k^{(i)}=A_k\cap\mathscr{S}^{(i)}$, which can be thought of as the "restriciton" of $A_k$ to the finite set of sentence symbols $\mathscr{S}^{(i)}$. Since each $\mathscr{S}^{(i)}$ is finite, we may construct a sentence $\varphi_i$ (unique, up to equivalence) such that ${A_1^{(i)},...,A_n^{(i)}}$ are precisely the models of $\varphi_i$ using the sentence symbols $\mathscr{S}^{(i)}$. Explicitly, $\varphi_i$ might be given by Then, we may claim that the set $\Sigma={\varphi_1,\varphi_2,...}$ has $K$ as its set of models. For each of the models $A_k$ is clearly a model of $\Sigma$ since it is a model of each $\varphi_i\in\Sigma$, and if $A\ne A_k$ for each $k=1,...,n$ for some model $A$, then there must be some $i$ for which $A\cup \mathscr{S}^{(i)}$ is distinct from each of the $A_1^{(i)},...,A_n^{(i)}$, which means that $A$ does not satisfy $\varphi_i$ and hence does not satisfy $\Sigma$. $\blacksquare$

So we have that a finite set of models is always the set of all models for some set of sentences.

Exercise 2. (Chang and Kiesler 1.2.9ii) Give an example of a set of sentences $\Sigma$ whose set of all models $K$ is countably infinite.

Solution. Consider the set $\Sigma$ consisting of the sentences where $\mathscr{S}={S_1,S_2,...}$. Clearly any model $A$ of $\Sigma$ containing $S_N$ for some $N\in\mathbb N$ must also contain $S_n$ for all $n < N$, meaning that unless $A=\varnothing$ or $A=\mathscr{S}$, $A$ is uniquely determined by the largest natural number $N$ for which $S_N\in A$. Hence, the set of all possible models of $\Sigma$ consists of
- The empty set $\varnothing$
- The set $\mathscr{S}$
- All sets of the form ${S_1,...,S_N}$ for $N\in\mathbb N$

which is countably many possible models. $\blacksquare$

So we have that it is possible for the set of all possible worlds to be only countably large.

Exercise 3. (Chang and Kiesler 1.2.9iii) Give an example of a countable set of models which cannot be represented as the set of all models of some set of sentences.

Solution. Let $K$ be the set of finite subsets of $\mathscr{S}$. Since $\mathscr{S}$ is countable, $K$ is also countable, and we claim that it is not the set of all possible models for any set of sentences $\Sigma$. First of all, note that a model $A$ satisfies $\Sigma$ if and only if it satisfies every finite subset of $\Sigma$. If any finite subset of $\Sigma$ is equivalent to the negation of a tautology, then $\Sigma$ is unsatisfiable and its set of possible models is $\varnothing$, so we may ignore this case. If all finite subsets of $\Sigma$ are equivalent to tautologies, then the set of all possible models of $\Sigma$ is $2^{\mathscr{S}}\ne K$, so we may ignore this case as well. Hence, we may assume that $\Sigma$ has some finite subset $\Sigma'\subset\Sigma$ which is not equivalent to a tautology or the negation of a tautology.

Since $\Sigma'$ is a finite set of sentences, it only uses finitely many sentence symbols, so we may choose $n$ sufficiently large that ${S_1,...,S_n}$ contains all of the sentence symbols used in $\Sigma'$. Further, since $\Sigma'$ is not a tautology, there exists a subset of ${S_1,...,S_n}$ which is not a model of $\Sigma'$. However, since $K$ consists of all finite subsets of $\mathscr{S}$, it contains this subset, meaning that some model in $K$ does not satisfy $\Sigma'$ nor $\Sigma$. Hence, $K$ is not the set of all models of $\Sigma$, and since $\Sigma$ was arbitrary, $K$ is not the set of all models of any set of sentences. $\blacksquare$

And we have that not all (countable) sets of models constitute the set of all possible models for some set of sentences.

One interesting way of characterizing these sets of models is by defining a topology on the set of models of $\mathscr{S}$. In a particular topology , these sets are precisely the closed sets.

model-theory

sentential-logic

back to home page