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