Follow up on the existence of prime model;

Question

I'm asking some follow up question on the following;

Existence of a prime model for a theory

Because I'm doing a practice exercise for an exam that is extremely similar to this. Like what the OP asked; I wish to know how to find a prime model for the Theory $T$ in question, and the comeplete 1-type of it.

In the comments, the OP said " it is not hard to see that every model of $T$ contains (up to isomorphism) $\{…,−2,−1,0,1,2,…\}×ω."$ (I would assume $\omega$ refers to set of natural number). So my first difficulty is seeing this fact; I must have missed something obvious.

Next the OP said "Here we consider $\{k\}×ω$ as the elements $x$ such that $Pf^kx$ is true but $Pf^{k−1}x$ is false". I dont really understand what he meant by that.

Lastly; is there a way to show the existence abstractly instead of constructing one? And how does one describe the 1-types of the theory ?

Answer 1

As to the question of showing that a prime model exists, there are various relevant theorems. For example, Vaught showed that for a countable theory the existence of a prime model is equivalent to the set of principal types being dense in the type space. This paper of Knight and its bibliography might be of interest.

---

Now as to the specific problem, we begin with a general analysis of $T$. So fix $M\models T$ and let's see what we can say about it.

The key is to shift to a "geometric" description of $M$: specifically, axioms $(1)$ and $(2)$ say that we can think of $M$ as a bunch of copies of $\mathbb{Z}$ - basically, $f$ represents the successor operation on each copy. In more detail, for $x\in M$ let $$[x]=\{f^z(x): z\in\mathbb{Z}\}$$ be the set of elements of $M$ "connected" to $x$ by $f$; then for each $x$, the set $[x]$ looks like $\mathbb{Z}$.

Now all that's left to describe in $M$ is:

• How many "$\mathbb{Z}$-copies" there are.

• How $P$ behaves on each of the $\mathbb{Z}$-copies.

The axiom $P(x)\rightarrow P(f(x))$ tells us that there are three possibilities for how $P$ can behave on a given $\mathbb{Z}$-chain $[x]$: maybe $P$ holds everywhere, or $P$ holds nowhere, or $P$ holds "half the time:" there is some $z\in\mathbb{Z}$ such that $P(f^w(x))$ for all $w\ge z$ but $\neg P(f^w(x))$ for all $w<z$. Call these "type $1$," "type $2$," and "type $3$" $\mathbb{Z}$-chains respectively.

Now we see that $M$ is determined up to isomorphism by three numbers, $c_1, c_2, c_3$, where $c_i$ is the number of $\mathbb{Z}$-chains of type $i$ in $M$.

Our next step is to determine what possibilities we can have. Axiom $4$ says that we $c_3$ is always infinite; right away this gives us an idea for the prime model of $T$, namely countably infinitely many chains of type $3$ and no other chains. With a little work we can prove, based on this, the following:

• Any collection of $\mathbb{Z}$-chains, infinitely many of which are of type $3$, yields a model of $T$.

• $\aleph_0$-many chains of type $3$ and no other chains gives the prime model of $T$.

The above is a bit informal but it's not hard to make precise. In particular, we have an intuitive description of the prime model; the discussion at the linked question gives a detailed construction.

As to the $1$-types, the point is that in each chain of type $3$ every element looks different from every other. Specifically, each element is determined by its "distance from the switching point" (and which side its on); e.g. the last element on which $P$ fails, the second element on which $P$ holds, the seventeenth element on which $P$ holds, etc. This gives us a bunch of complete $1$-types, which we can think of as corresponding to integers if we want.