Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

After reading about the question, I've come to believe that it would suffice to exhibit and automorphism of that is not order preserving. However, I'm unsure of how to construct such an automorphism, and am a bit uncertain if my approach is sound. Any guidance would be appreciated.

The exact question reads: Let N = ⟨N,S,0⟩ where N = {0,1,2,...} and S is the successor function. Show that the binary relation {⟨a, b⟩ | a, b ∈ N and a < b} is not definable over N

share|cite|improve this question
$\mathbb{N}$ with successor has no non-trivial automorphisms, so this isn't going to work. – Chris Eagle Oct 23 '12 at 20:03
Do you mean in a manner similar to this MO question and this math.SE question? – arjafi Oct 23 '12 at 20:05
I would be inclined to try to use the Compactness Theorem with a nicely chosen set of extra statements. – Lord_Farin Oct 23 '12 at 20:06
I feel like I'm missing something; can anyone explain intuitively why this can't be done? Or perhaps a definition of constructible over N? – Eric Stucky Oct 23 '12 at 20:24
@spernerslemma: Read the question. Zero and successor. In fact this is one of the ways to show that addition and multiplication are not definable from only the successor: if they were then the order would be definable as well. – Asaf Karagila Oct 23 '12 at 20:32
up vote 9 down vote accepted

Suppose that $\varphi ( x , y )$ is a first-order formula defining the relation $<$ in $\mathcal{N} = ( \mathbb{N} , S , 0 )$; that is $$\mathcal{N} \models \varphi ( m,n ) \quad\Leftrightarrow\quad m < n.$$ Note that if $\mathcal{M}$ is any elementary extension of $\mathcal{N}$ it must be that $\varphi (x,y)$ defines a strict total (linear) order on the universe of $\mathcal{M}$. Consider the structure $\mathcal{M} = ( M , s , 0 )$ where

  • $M = \mathbb{N} \cup ( \mathbb{Z} \times \{ 0 , 1 \} )$;
  • $s(m) = m+1$; $s(m,i) = (m+1,i)$.

Then $\mathcal{M}$ is an elementary extension of $\mathcal{N}$. Let $a_0 = (0,0)$ and $a_1 = (0,1)$. As $\varphi$ defines a strict total order on $M$ we may assume without loss of generality that $$\mathcal{M} \models \varphi ( a_0 , a_1 ).$$

Consider the following function $\sigma : M \to M$:

  • $\sigma ( m ) = m$; and
  • $\sigma ( m , i ) = ( m , 1-i )$ (i.e., $\sigma$ switches the two disjoint copies of $\mathbb{Z}$).

It is quite easy to show that $\sigma$ is an automorphism of $\mathcal{M}$, and therefore $$\mathcal{M} \models \varphi ( \sigma(a_0) , \sigma(a_1) ).$$ But as $\sigma ( a_0 ) = a_1$ and $\sigma ( a_1 ) = a_0$ we have that $$\mathcal{M} \models \varphi ( a_1 , a_0 ),$$ contradicting the fact that $\varphi$ defines a strict total order on $M$!

share|cite|improve this answer
Why must it be that $\varphi$ defines a total order on $\mathcal{M}$ just because it defines one on $\mathcal{N}$? – mjqxxxx Oct 23 '12 at 22:08
Because the statement that "$\varphi$ defines a total order" is first order. – Andrés E. Caicedo Oct 23 '12 at 23:06

Your Answer


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.