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 $\mathcal{N} = ⟨\Bbb{N},S,0⟩$ where $\Bbb{N} = \{0,1,2,\cdots\}$ and $S$ is the successor function. Show that the binary relation $\{⟨a, b⟩:a, b ∈ \Bbb{N} \land a < b\}$ is not definable over $\Bbb{N}$.

Solution 1:

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