1
$\begingroup$

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

  • 0
    @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.2012-10-10

2 Answers 2

5

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

  • 0
    @Nagase: No, it doesn't require infinitely long formulas. I just pick some finite number of sentences from $\mathscr{S}$, and then form a sentence (of finite length) from these finitely many sentences determined by the true-false patterns in the given models. But I do this for all choices of finitely many sentences from $\mathscr{S}$, so I will end up with an infinite collection $\Gamma$ of sentences. (Also, the models themselves could be infinite, I just have finitely many of them.)2014-04-15
1

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