Xrfgtjtk

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 Xmodels phi$$

I must show $Ymodels phi$ and $Z models phi$.

Now, the languages of these structures are the language of Dense Linear Ordering together with the constants ${c_n}_{nin 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)$?

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_nmid 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 $Ymodels T$ and $Zmodels 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 $xin 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 $Mmodels T$ by $xmapsto c_x^M$.