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.

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.

share|improve this question
    
Take propositional symbols $P_i$, $i=0,1,2,\dots$. Have axioms $P_i\longrightarrow P_{i+1}$. –  André Nicolas Oct 5 '13 at 6:41

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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}$.

share|improve this answer

Your Answer

 
discard

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

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