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.