Find non-isomorphic models of $(Q,<,c_{n \in N})$

Question

This is a problem in Basic Model Theory by Kees Doets:

Let

$X=(Q,<,n)_{n \in N}$

$Y=(Q,<,\frac{-1}{n+1})_{n \in N}$

$Z=(Q,<,q_n)_{n \in N}$ where $\{q_n\}_{n \in N}$ is an ascending sequence of rationals converging to some irrational.

(a) Show that $Y$ and $Z$ are countable models of $Th(X)$.

(b) Show that they are the only other models of $Th(X)$ up to isomorphism.

(c) Show which one is saturated and which one is prime.

---

Attempt:

(Sketch)

By Vaught's Theorem, no complete theory has exactly two countable models.

If I show that either $Y$ or $Z$ are saturated, then I know there will be another equivalent prime model (Proposition 4.33 Kees Doets), and by Vaught's test it can't be only these two models of $Th(X)$, so there needs to be at least a third one. This way I get at least three models, and all I have to show is that any fourth model would be isomorphic to one of these three.

My guess is that $Z$ will turn up to be saturated, $X$ will be prime, and all other models will be isomorphic to $Y$.

---

But first I need to show $Y$ and $Z$ are actually models of $Th(X)$.

Let $$\phi \in Th(X) \Rightarrow X\models \phi$$

I must show $Y\models \phi$ and $Z \models \phi$.

Now, the languages of these structures are the language of Dense Linear Ordering together with the constants $\{c_n\}_{n\in N}$, where the constants are interpreted as indicated in each structure. If $\phi$ is a sentence not involving any of the additional constants, then $\phi$ belongs to the theory of Dense Linear Ordering and therefore satisfied in all models.

However, if $\phi$ contains constant symbols, how do I know that being satisfied in $X$ implies it is satisfied in $Y$ and $Z$?

Also, am I correct that $Z$ should be saturated, and $X$ prime? If so, can you make any suggestions as to why or how to show it? Is it the case that $X$ is always a prime model of $Th(X)$?

Answer 1

For (a) and (b), you need to understand $\text{Th}(X)$, e.g. by axiomatizing it or coming up with some other necessary and sufficient condition to be elementarily equivalent to $X$.

There are some obvious axioms for $\text{Th}(X)$:

• The axioms of dense linear orders without endpoints (DLO).
• The axioms $\{c_m < c_n\mid m<n\}$.

Here I'm using $c_n$ for the constant symbol which names the elements $n$ in $X$, $\frac{-1}{n+1}$ in $Y$, and $q_n$ in $Z$.

Let $T$ be the set of axioms above. It turns out that $T$ suffices to axiomatize $\text{Th}(X)$, i.e. $T$ is complete. You need to prove this.

Now I don't know what tools do you have available to prove that a theory is complete, but here are some possibilities:

1. You could prove $T$ has quantifier elimination and decides the truth of every quantifier-free sentence (this is probably the easiest way to go if you already know that DLO has quantifier elimination).
2. You could use an Ehrenfeucht-Fraïssé game argument to prove that any model of $T$ is elementarily equivalent to $X$.
3. Or here's a clever (but more ad hoc) trick: If $T$ has a model which is not elementarily equivalent to $X$, then it has a countable such model $X'$. Then $X$ and $X'$ disagree about some sentence, which only mentions finitely many constant symbols. Show that in the reduct to just the order and these finitely many constant symbols, $X$ and $X'$ are isomorphic, contradiction.

Once you've axiomatized $\text{Th}(X)$ by $T$, (a) is easy (just check that $Y\models T$ and $Z\models T$). For (b), let $M$ be an arbitrary countable model of $T$, decide which of $X$, $Y$, and $Z$ it should be isomorphic to, and prove it.

Also, am I correct that Z should be saturated, and X prime?

Yes.

If so, can you make any suggestions as to why or how to show it?

Well, the usual way to prove that a model is saturated is to understand all the types (e.g. by proving quantifier elimination), and check that they're all realized in $Z$. But in this case, you're guaranteed that $T$ has a countable saturated model (since it only has finitely many countable models, this is a theorem), so all you have to do is check that $X$ and $Y$ are not saturated, which is much easier.

Similarly, to show that $X$ is prime, you could show that $X$ embeds elementarily into both $Y$ and $Z$ (and hence into every model of $T$, since every model of $T$ has a countable elementary substructure, which is isomorphic to $X$, $Y$, or $Z$). But in this case, you're guaranteed that $T$ has a countable prime model (since it has a countable saturated model, this is a theorem), so all you have to do is check that $Y$ and $Z$ are not prime, e.g. by showing that they both realize types which are not realized in $X$.

Is it the case that X is always a prime model of Th(X)?

You mean for a general structure $X$? Of course not. Let $T$ be any complete theory, and let $X$ be any model of $T$ which is not prime. Then $T = \text{Th}(X)$, but $X$ is not a prime model of this theory.

On the other hand, if you expand the language to $L(X)$ by adding a new constant symbol $c_x$ for each element $x\in X$, and take $T = \text{Th}_{L(X)}(X)$ (which is also called the elementary diagram of $X$), then $X$ is a prime model of $T$. Indeed, $X$ has a canonical elementary embedding into any model $M\models T$ by $x\mapsto c_x^M$.