1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Athar Abdul-Quader Dec 13 '18 at 14:46
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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