5
$\begingroup$

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

  • 0
    Isn't this what is meant by a "proper" extension?2012-10-16
  • 0
    Could you elaborate on that?2012-10-16
  • 0
    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.2012-10-16
  • 0
    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.2012-10-16
  • 0
    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$).2012-10-16
  • 0
    Is that argument valid? Suppose $\mathcal M = (\mathbb R, 0, (\cdot + 1), <)$, which I supose is a proper elementary extension of $\mathcal M$, and $D \subset \mathbb Z$. Then $D^\prime \subset \mathbb Z$ (for $Sy \in \mathbb Z \Rightarrow y\in \mathbb Z$) and neither $D$ nor $D^\prime$ includes non-integers.2012-10-16
  • 0
    @Pteromys: $D'=\mathbb R\setminus D$ is not a subset of $\mathbb Z$.2012-10-16
  • 0
    @Pteromys: Your $\mathcal{M} = ( \mathbb{R} , 0 , +1 , < )$ is certainly _not_ an elementary extension of $( \mathbb{Z} , 0 , S , < )$. The latter satisfies the sentence $( \forall x ) ( \neg ( \exists y ) ( x < y \wedge y < S(x) ) )$, while the former does not.2012-10-16

1 Answers 1

5

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.

Added for clarity:

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

These conclusions are clearly contradictory!

  • 0
    @Pteromys: I hope my additions help.2012-10-17
  • 0
    Why $S^{\mathcal M}(a) \in \mathbb Z \Rightarrow a \in \mathbb Z$?2012-10-17
  • 0
    @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}$.2012-10-17
  • 0
    Thanks a lot. (Actually, you did *not* misread my comment before. I was so sleepy when I wrote what I didn't mean to write. I meant to write what is in my last comment then. That's why I deleted it.)2012-10-18