I'm just starting Model Theory (Chang & Keisler) and I'm having trouble right off the bat with exercise 1.2.9 (ii):

Give an example of a set $\Sigma$ of sentences such that the set of all models of $\Sigma$ is countably infinite.

I am to assume that the sentences are built from the set $\mathbb S$ of simple statements, and that $\mathbb S$ is countable. We're working with models of propositional logic. (Aside: anyone recognize the character that the book uses for $\mathbb S$? I cannot identify it.)

My problem is that I've mathed myself into a corner. Here's what I've got so far. (I'll refer to the set of all models of $\Sigma$ as $\mathbb M$.)

  1. If $\Sigma$ is not satisfiable then $\mathbb M = \emptyset$, which is not countably infinite.

  2. If $\Sigma = \emptyset$ then every set of symbols in $\mathbb S$ constitutes a model for $\Sigma$, so $\mathbb M = \mathbb P(\mathbb S)$. The cardinality of the powerset of a countably infinite set is $\mathfrak{c}$, so $\mathbb M$ is not countably infinite.

  3. If $\Sigma$ is finite then we can construct a single sentence $\phi$ such that whenever $A \models \phi$, $A \models \Sigma$. $\phi$ is satisfiable, so it is finitely satisfiable, so it is satisfiable by a model containing a finite number of elements in $\mathbb S$. Therefore $\mathbb M$ includes some finite minimal model $M$ of $\phi$, and $\mathbb M$ also includes $M \cup R$ for all $R \subset \mathbb P(\mathbb S - M)$ (because $R$ has no impact on whether $M \cup R \models \phi$). Because $M$ is finite, $\mathbb S - M$ is countably infinite, so the cardinality of $\mathbb P(\mathbb S - M)$ is $\mathfrak{c}$, so $\mathbb M$ is not countably infinite.

  4. If $\Sigma$ is $\{\phi_0, \phi_1, ...\}$ for all $\phi_i \in \mathbb S$ (each simple symbol in $\mathbb S$ is a sentence in $\Sigma$), then $\mathbb M = \{\mathbb S\}$ and $\mathbb M$ is not countably infinite.

  5. If $\Sigma$ contains as sentences all symbols in $\mathbb S$ save for a finite set $F$ of them, then we must use all symbols in $\mathbb S$ in any model of $\Sigma$, save for a finite number of them which we can freely choose. In other words, $\mathbb M = \{\mathbb S - G : G \in \mathbb P(F)\}$. Because $\mathbb P(F)$ is finite, $\mathbb M$ is finite.

  6. If $\Sigma$ contains as sentences all symbols in $\mathbb S$ save for a countable set of $S$ of them, then to any model $M$ of $\Sigma$ we can adjoin a subset $R$ of $\mathbb P(S)$ without violating $M \cup R \models \Sigma$. The cardinality of $\mathbb P(S)$ is $\mathfrak c$, so $\mathbb M$ is not countably infinite.

So if $\mathbb M$ is to be countably infinite then $\Sigma$ cannot have (as sentences) zero elements of $\mathbb S$, nor can it have a finite subset of $\mathbb S$ as sentences, nor may it have a countably infinite (barring a finite set) set of elements of $\mathbb S$ as sentences, nor may it have a countably infinite (barring a countably infinite set) set of elements of $\mathbb S$ as sentences, nor may it have all elements of $\mathbb S$ as sentences.

Obviously I've taken a horribly wrong turn somewhere. I'm quite new to model theory, can you point out the flaw in my logic? I suspect it might be related to the fact that I'm considering only sets of simple sentences, but I'm not sure how.


Well, according to your observations $\Sigma$ is going to have to contain compound sentences (made up of connectives other than $\neg$).

Perhaps the conceptually easiest way to ensure that the set of models of $\Sigma$ is countably infinite is to ensure that $\Sigma$ is satisfied iff at most one of $s_0, s_1 , \ldots$ is true. (Then the models of $\Sigma$ are just the empty set, and all singleton sets, which is clearly countably infinite.)

Let $\Sigma$ be the set of all sentences of the form $\neg s_i \vee \neg s_j$ where $i < j$ are natural numbers.

  • Clearly $\varnothing \models \Sigma$, since $\neg s_i$ is true in $\varnothing$ for all $i$. If $M = \{ s_k \}$, then for any sentence $\neg s_i \vee \neg s_j$ in $\Sigma$, either $i \neq k$ (whence $M \models \neg s_i$) or $j \neq k$ (whence $M \models \neg s_j$), so in either case we have $M \models \neg s_i \vee \neg s_j$. Thus $M \models \Sigma$.
  • If $M \subseteq \mathbb{S}$ has size at least two, pick $i < j$ such that $s_i, s_j \in M$. Then clearly $M \not\models \neg s_i \vee \neg s_j$, and so $M$ is not a model of $\Sigma$.

Let the propositional symbols be $P_i$, $i=0,1,2,\dots$, and let the axioms be $P_i\longrightarrow P_{i+1}$.


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.