Finite Set of Models

Question

This is only directed towards logicians, model theorists etc.. I am reading "Model Theory" by Keisler and Chang and have encountered the following question.

Let $\Psi = \{M_1,...,M_n \}$ be a finite set of models (also known as interpretations) of a given language $L$. Let me also mention that $L$ is generated from a countably infinite alphabet $S$. Prove that $\exists$ a set $\Gamma$ of sentences (or well-formed formulas) such that $\Psi$ is the set of all models for $\Gamma$.

Answer 1

(Using the notation from Chang-Keisler.) Let the models be $M_1 , \ldots , M_n \subseteq \mathscr{S}$.

For each sentence symbol $S$ of $\mathscr{S}$ and each $i \leq n$, by $S_i$ denote $$ \begin{cases} S, &\text{if }S \in M_i \\ \neg S, &\text{if }S \notin M_i. \end{cases} $$ Let $\Gamma$ be the set of all sentences of the form $$ (S^1_1 \wedge \cdots \wedge S^m_1 ) \vee \cdots \vee (S^1_n \wedge \cdots \wedge S^m_n ) $$ where $S^1 , \ldots , S^m \in \mathscr{S}$.

Clearly each $M_i$ is a model of $\Gamma$.

Suppose now that $N \subseteq \mathscr{S}$ is some model distinct from each $M_i$. For each $i \leq n$ there is a sentence symbol, $S^i$ such that either $S^i \in M_i$ and $S^i \notin N$, or the opposite. It is easily seen that $N$ is not a model of the sentence $$ (S^1_1 \wedge \cdots \wedge S^n_1 ) \vee \cdots \vee (S^1_n \wedge \cdots \wedge S^n_n ) $$ ($N$ cannot model $(S^1_i \wedge \cdots \wedge S^n_i )$ since by construction it does not model $S^i_i$.)

Answer 2

Let $\Gamma$ be the set of sentences that are true for all of the $M_i$. If $M_i\ne M_j$, there is a sentence $\phi_{i,j}$ that is true in $M_i$ and false in $M_j$. Let $\phi_i=\phi_{i,1}\land\cdots\land\phi_{i,n}$ (with $\phi_{i,i}$ omitted). Then $\phi_i$ is true in $M_i$ and false in all $M_j$ with $j\ne i$. Let $\phi=\phi_1\lor\cdots\lor\phi_n$. Then $\phi$ holds in all $M_i$, hene $\phi\in\Gamma$.

Let $M$ be a model of $\Gamma$. Then $\phi$ is true in $M$, hence (at least) one $\phi_i$ is true in $M$. If $\psi$ is a sentence that is true in $M_i$ then $\phi_i\to \psi$ is in $\Gamma$ because $\phi_i$ is false in $M_j$ with $j\ne i$ and $\psi$ is true in $M_i$. It follows that $\phi_i\to \psi$ is true in $M$ and finally $\psi$ is true in $M$. If on the other hand, $\psi$ is false in $M_i$, then $\neg\psi$ is true in $M_i$, hence true in $M$, hence $\psi$ false in $M$. We conclude that $M=M_i$.