Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
I have a question. Does this answer presuppose that $\mathscr{S}$ is finite? Because otherwise we could always have a model $N$ such that $M_i \subset N$, no? (I'm thinking specifically of your other answer to my question about the cardinality of the set of all models for $\phi$ when $\phi$ is satisfiable and $\mathscr{S}$ is countably infinite. –  Nagase Mar 24 at 0:46
    
@Nagase: No. What's going on above is that given sentence symbols $S^1 , \ldots , S^m \in \mathscr{S}$ I form a sentence, call it $\phi(S^1 , \ldots , S^m)$, and then my set $\Gamma$ of $\mathscr{S}$-sentences is the collection of all these $\phi(S^1,\ldots,S^m)$. Your previous question was to show that there are uncountably many models of one specific sentence provided $\mathscr{S}$ is infinite; here I am constructing an uncountable set of sentences with only finitely many (prescribed) models. –  Arthur Fischer Mar 24 at 4:13
    
I see. I think that I was wrongly focused on the (let us call it) expressive power of a sentence, and missing the fact that we're working with a set of sentences. Missing the forest for the trees, so to speak! –  Nagase Mar 24 at 13:12
    
Sorry to insist on this again, but I have a further question. If $\mathscr{S}$ is infinite, does your construction require infinite long formulas? I ask this because, if I understood your construction correctly, we need to negate every sentence symbol which does not appear in the model; since the models are finite, if $\mathscr{S}$ is infinite, there will be infinite many symbols which won't appear in the model. Is this correct? –  Nagase Apr 14 at 23:26
    
@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.) –  Arthur Fischer Apr 15 at 4:55

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.