I have just started reading Chang and Keisler and I'm already stuck in an exercise. Let $\mathscr{S}$ be a countable set of sentence letters (i.e. $\mathscr{S} = \{S_0, S_1, S_2, \dots\}$ or some such). Let $\phi$ be a wff built in the usual way (using negation and/or conjunction). Suppose $\phi$ is satisfiable, i.e. it has at least one model. On p. 17, exercise 1.2.7, they ask us to prove that the set of all models of $\phi$ has the cardinality of the continuum. Now, I'm a little bit confused by this. It seems obvious that, if $\phi$ is valid, then, indeed, the set of all models of $\phi$ is the cardinality of the continuum (there are two possible valuations for each sentence letter, thus the set of all models has cardinality $2^{|\mathscr{S}|}$). But if $\phi$ is only satisfiable, I don't see how the result follows. What am I missing?


Hint: Sentence symbols/letters which do not occur in $\phi$ play no role in determining the truth or falsity of $\phi$ in a model.

  • $\begingroup$ So the idea is: $\phi$ is necessarily composed of a finite number of sentence letters. Let $S_i$ be a sentence letter which does not occur in $\phi$. We know that $\phi$ is satisfiable, i.e. true in at least one model. Call such a model $A$. Now, given each $S_i$, we can extend $A$ to $A'$ such that it either values $S_i$ as true or false. Since there are countably many $S_i$s, this means that $A$ can be extended to $2^{|\mathscr{S}|}$ models. $\endgroup$ – Nagase Mar 23 '14 at 1:33
  • 1
    $\begingroup$ @Nagase: Yup! (Or, as I might put it, let $\mathscr{S}^\prime$ denote all of the sentence symbols from $\mathscr{S}$ which do not appear in $\phi$, and let $A_0$ be a subset of the sentence symbols from $\mathscr{S}$ which do appear in $\phi$ such that $A_0 \models \phi$. Then $A_0 \cup A \models \phi$ for all $A \subseteq \mathscr{S}^\prime$.) $\endgroup$ – user642796 Mar 23 '14 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.