Elementary embedding of $\mathbb{Z}$ in $\mathbb{Z}^2$

Question

Let $Z = (\mathbb{Z}, 0, S, P)$ where $S$ and $P$ are the usual sucessor and predecessor functions. Let $Z^2 = (\mathbb{Z}\times \mathbb{Z}, (0,0), S', P')$ where $S'(a,b) = (S(a),b)$ and $P'$ the same with $P.$ Consider: $$ \iota: \mathbb{Z}\to\mathbb{Z}\times \mathbb{Z} \\ \iota(n) = (n,0) $$

Show that $\iota$ is an elemeentary embedding.

My approach:

I have to show that $Z_1=(\mathbb{Z}\times\{0\}, (0,0), S', P' )$ is an elementary subestructure of $Z_2$. At first, I tried to use Tarski Criterion, particularly, I showed that it is enough to prove that $\mathbb{Z}^2 -(\mathbb{Z}\times\{0\})$ is not a definable set with parameters in $Z_1$, but I wasn't able to show that since every automorphism fixs $\mathbb{Z}\times\{0\}.$

Also, I discovered that every definable set in $Z_2$ with parameters in $Z_1$ is also a definable set from paramters in $\emptyset$ (This can be done applying $S'$ and $P'$ to $(0,0)$), then it's sufficient to show that $Z_1\equiv Z_2.$

Answer 1

One way you can prove $Z_1\equiv Z_2$ is to simply provide a list of axioms both satisfy and then prove those axioms generate a complete theory. In this case, you might use axioms that say that $S$ and $P$ are inverses of each other, and that $S^n(x)\neq x$ for any $x$ and any $n>0$ (this is a separate axiom for each $n$). Clearly both $Z_1$ and $Z_2$ satisfy these axioms. On the other hand, you can prove these axioms are complete by showing they are uncountably categorical.

A proof that these axioms are uncountably categorical is hidden below.

Suppose $M$ is an uncountable model. Define an equivalence relation $\sim$ on $M$ by $x\sim y$ if $x=S^n(y)$ for some $n\in\mathbb{Z}$. Let $A\subset M$ be a set of representatives for the equivalence classes, including $0_M$ as one of the representatives. We have $|A|=|M|$, since $M$ is uncountable and each equivalence class is countable. For any other uncountable model $M'$, we can similarly choose a set of representatives $A'\subset M'$. If $|M|=|M'|$, we have $|A|=|A'|$, so we can choose a bijection $f:A\to A'$ sending $0_M$ to $0_{M'}$. We can then extend $f$ to an isomorphism $M\to M'$ by defining $f(S^n(a))=S^n(f(a))$ whenever $a\in A$ and $n\in\mathbb{Z}$. This is well-defined since whenever $n>m$, $S^n(a)=S^{n-m}(S^m(a))\neq S^m(a)$ by our axioms (so each element of $M$ has the form $S^n(a)$ for a unique $n\in\mathbb{Z}$).