# Show that binary < “less than” relation is not definable on set of Natural Numbers with successor function

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

-
$\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? –  Arthur Fischer 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
show 5 more comments

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

-
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. –  Andres Caicedo Oct 23 '12 at 23:06