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

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)$$?

• Hints: 1) Either prove it by induction on formulas, or find elementary embeddings between the three models. 2) If Z is saturated, what is the type that is realized in Z but not realized in the other models? Think of the type of an element $x$ which says "$c_n \rightarrow x$" (roughly). – Athar Abdul-Quader Dec 13 '18 at 14:46

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.

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