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

Question

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.

Answer 1

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

Answer 2

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