# $2\mathbb Z$ is not a definable set in the structure $(\mathbb Z, 0, S,<)$

This is (a translation of) an excerpt from a model theory textbook that shows that $2\mathbb Z$ is not a definable set in the structure $(\mathbb Z, 0, S, <)$, where $S$ is the successor function.

Suppose $2\mathbb Z$ is defined by a formula $\phi(x)$. Then let $\mathcal M \succ (\mathbb Z, 0, S, <)$ be a proper elementary extension and $D$ be the set defined by $\phi(x)$ in $\mathcal M$. In $\mathbb Z$, odd numbers and even numbers appears in turn. A similar property holds in $\mathcal M$, thus (1): $a\in D \Rightarrow S(a) \not \in D$. Let $\sigma : \mathcal M \rightarrow \mathcal M$ be a map defined by $a \mapsto a\ (a \in \mathbb Z)$ and $a \mapsto S(a)\ (a \not \in \mathbb Z)$. Then $\sigma$ is an isomorphism on $\mathcal M$. By (1), $\sigma$ does not preserve $D$. Thus $2\mathbb Z$ is not definable in $\mathbb Z$.

This uses the following proposition:

Suppose $A\subset |\mathcal M|^n$ is definable. Then for every isomorphism $\sigma$ on $\mathcal M$, $\sigma(A) = A$.

What I don’t understand is the argument that $\sigma$ does not preserve $D$. I suppose this argument assumes $D\setminus\mathbb Z\neq\emptyset$. This intuitively holds, because the language is not expressive enough to exclude non-integers from $D$ (I’m thinking of $\mathbb R$ as $\mathcal M$). But I am unable to show this.

How can you prove that $D\setminus\mathbb Z\neq\emptyset$?

#### Solutions Collecting From Web of "$2\mathbb Z$ is not a definable set in the structure $(\mathbb Z, 0, S,<)$"

Note that if $\phi (x)$ defines $2 \mathbb{Z}$ in $\mathcal{Z} = ( \mathbb{Z} , 0 , S , < )$ then as $\mathcal{Z} \models ( \forall x ) ( \phi (x) \vee \phi ( S(x) )$, every elementary extension of $\mathcal{Z}$ must also satisfy this sentence. From this it follows that $D \setminus \mathbb{Z}$ is nonempty.

If $\phi (x)$ defines $2 \mathbb{Z}$ in the model $\mathcal{Z}$, then it must be that $$\mathcal{Z} \models ( \forall x ) ( \phi (x) \leftrightarrow \neg \phi ( S(x) )$$ (and this is probably much better than my original). As an elementary extension, $\mathcal{M}$ must also satisfy this sentence. From here we may conclude that there is an $a \in M \setminus \mathbb{Z}$ (where $M$ denotes the universe of $\mathcal{M}$) such that $\mathcal{M} \models \phi ( a )$. (Taking any $a \in M \setminus \mathbb{Z}$ either it or $S^{\mathcal{M}} (a)$ will be as required.)
Using the automorphism $\sigma$ of $\mathcal{M}$ given in the question, and taking any $a \in M \setminus \mathbb{Z}$ such that $\mathcal{M} \models \phi (a)$, we then have the following:
• As $\mathcal{M} \models ( \forall x ) ( \phi (x) \leftrightarrow \neg \phi ( S(x) )$ it follows that $\mathcal{M} \models \neg \phi ( S(a) )$.
• As $\sigma$ is an automorphism it follows that $\mathcal{M} \models \phi ( \sigma(a) )$, but as $\sigma (a) = \mathcal{S}^\mathcal{M}$ we get $\mathcal{M} \models \phi ( S(a) )$.