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

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$).
Hint: Find a set of sentences which is satisfied iff at most one of $s_0 , s_1 , \ldots$ is true. (Working first on finite initial segments of this enumeration of $\mathbb{S}$ may be helpful.)
Cool. $s_0 \lor \lnot s_0 \in \Sigma$ and $s_{n^+} \rightarrow (\lnot s_n \land \ldots) \in \Sigma$, $\mathbb M$ contains $\emptyset$ and singleton subsets of $\mathbb S$. Thanks for the hint! – Nate Oct 5 '13 at 7:33
Let the propositional symbols be $P_i$, $i=0,1,2,\dots$, and let the axioms be $P_i\longrightarrow P_{i+1}$.