Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
show 3 more comments

1 Answer 1

up vote 5 down vote accepted

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!

share|improve this answer
    
@Pteromys: I hope my additions help. –  Arthur Fischer Oct 17 '12 at 5:36
    
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
    
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.) –  Pteromys Oct 18 '12 at 8:21
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.