# Finite Set of Models

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

-
I don't have the book. The assertion makes no sense for first-order logic if any of the $M_i$ is infinite, by Lowenheim-Skolem. –  André Nicolas Oct 10 '12 at 5:25
I apologise for the confusion. This is in sentential or predicate logic. –  user44069 Oct 10 '12 at 5:26
By first-order logic I meant the predicate calculus, what you call predicate logic. Remark about if one of the $M_i$ is infinite still stands. –  André Nicolas Oct 10 '12 at 5:35
@André: I have the first edition; it has a version of this as part (i) of a starred exercise (Ex. 1.2.9) in the section on model theory for sentential logic, not predicate logic. Here a model is simply a subset of the set $\mathscr{S}$ of simple statements. –  Brian M. Scott Oct 10 '12 at 6:19

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

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