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

-
Isn't this what is meant by a "proper" extension? –  Mark Bennet Oct 16 '12 at 14:21
Could you elaborate on that? –  Pteromys Oct 16 '12 at 14:24
Well, in general. the word "proper" is used to mean the object you are considering is different from the one you started with (proper subgroups, ideals, extensions), rather than the trivial example (the original object itself), which satisfies the definition, but isn't what you really want to consider. I don't know the textbook you are using, so the definition there might be different, but I would check out how it uses the word "proper" in this context. –  Mark Bennet Oct 16 '12 at 14:30
Well, I know that, and I suppose 'proper' here means $\mathbb Z$ is properly contained in $|\mathcal M|$ in a set-theoretic sense. The notion of extension of models being proper is not defined in the book, though. –  Pteromys Oct 16 '12 at 14:34
Let $D'$ be the set defined by $\phi(Sx)$ in your $\mathcal M$. As $\mathcal M$ is a proper extension either $D'$ or $D$ must contain some non-integers. But if one does contains some $y$, the other must contain $Sy$ (which isn't an integer for non-integer $y$). –  martini Oct 16 '12 at 14:54

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

Why $S^{\mathcal M}(a) \in \mathbb Z \Rightarrow a \in \mathbb Z$? –  Pteromys Oct 17 '12 at 10:29
@Pteromys: Sorry; I severely misread your comment before. Note that $S^{\mathcal{M}}$ must be one-to-one. If $a \in M$ is such that $S^{\mathcal{M}} ( a ) = b \in \mathbb{Z}$, then $\mathcal{Z} \models ( \exists x ) ( S(x) = b )$, and therefore there is some $a^\prime \in \mathbb{Z}$ such that $S^{\mathcal{Z}} ( a^\prime ) = b$. But then $S^{\mathcal{M}} ( a^\prime ) = b$, and so by injectivity $a = a^\prime \in \mathbb{Z}$. –  Arthur Fischer Oct 17 '12 at 15:28