Mostrar ese binario < relación "menor que" no es definible en el conjunto de números naturales con la función del sucesor

Question

Después de leer sobre el tema, he llegado a creer que es suficiente para exhibir y automorphism de que no se conserva el orden. Sin embargo, estoy seguro de cómo construir una automorphism, y estoy un poco incierto si mi planteamiento es el sonido. Cualquier orientación se agradece.

La pregunta exacta que se lee: Vamos N = ⟨N,S,0⟩, donde N = {0,1,2,...} y S es la función sucesor. Mostrar que la relación binaria {⟨a, b⟩ | a, b ∈ N y un < b} no es definible más de N

Answer 1

Supongamos que $\varphi ( x , y )$ es de primer orden la fórmula de la definición de la relación $<$$\mathcal{N} = ( \mathbb{N} , S , 0 )$; que es $$\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 )$ donde

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

A continuación, $\mathcal{M}$ es una primaria de la extensión de $\mathcal{N}$. Deje $a_0 = (0,0)$$a_1 = (0,1)$. Como $\varphi$ define un estricto orden total en $M$ podemos suponer sin pérdida de generalidad que $$\mathcal{M} \models \varphi ( a_0 , a_1 ).$$

Considere la siguiente función de $\sigma : M \to M$:

• $\sigma ( m ) = m$; y
• $\sigma ( m , i ) = ( m , 1-i )$ (es decir, $\sigma$ interruptores de las dos copias disjuntas de $\mathbb{Z}$).

Es muy fácil demostrar que $\sigma$ es un automorphism de $\mathcal{M}$, y por lo tanto $$\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$!