La relación $<$ no es definible en la estructura de los números enteros con la función sucesor

Question

Tengo que probar la siguiente declaración:

Demostrar que no existe una fórmula $\psi=\psi(x_0,x_1)$ en el idioma $\operatorname{Th}((\mathbb{Z},S))$ tal de que la relación se $\{(m,n)\in\mathbb{Z}\times\mathbb{Z}: (\mathbb{Z},S)\models \psi[m,n]\}$ es lineal en el orden de $\mathbb{Z}$. A la conclusión de que la relación se $<$ $\mathbb{Z}$ no es definible en la estructura de la $(\mathbb{Z},S)$

Observe que $S$ es el sucesor de la función y $\psi(x_0,x_1)$ una fórmula con dos variables libres. Alguien me puede ayudar con esta pregunta porque no tengo idea de cómo resolver este problema. Pensé acerca de la eliminación de cuantificadores, pero se puede resolver esto también sin eliminación de cuantificadores, por ejemplo, con los automorfismos?

Answer 1

El uso de automorfismos de no mostrar fórmula $\psi ( x,y )$ sobre el lenguaje de $\{ S \}$ define un orden lineal sobre $\mathcal{Z} = ( \mathbb{Z} , S )$, ten en cuenta, en primer lugar, que dado que la única automorfismos de a $\mathcal{Z}$ son los cambios no vamos a ser capaces de trabajar con $\mathcal{Z}$ sí, sino que algunos primaria de extensión.

Vamos a considerar la estructura de $\mathcal{M} = ( \mathbb{Z} \cup \mathbb{Z}^* , s )$ donde

• $\mathbb{Z}^*$ es un "destacado" copia de $\mathbb{Z}$ (disjunta de a $\mathbb{Z}$);
• $s : \mathbb{Z} \cup \mathbb{Z}^* \to \mathbb{Z} \cup \mathbb{Z}^*$ es la forma natural definido sucesor del operador: $$\begin{align} s ( n ) &= n+1 \\ s ( n^* ) &= (n+1)^*.\end{align}$$

Es bastante sencillo para mostrar que $\mathcal{Z} \prec \mathcal{M}$, y así si $\psi (x,y)$ define un orden lineal en $\mathcal{Z}$ también define un orden lineal, $\sqsubset$,$\mathcal{M}$. Desde la asignación $\sigma : \mathbb{Z} \cup \mathbb{Z}^* \to \mathbb{Z} \cup \mathbb{Z}^*$ definido por $$\begin{align} \sigma( n ) &= n^*\\ \sigma( n^* ) &= n\end{align}$$ is an automorphism of $\mathcal{M}$, it follows that for all $a,b \in \mathbb{Z} \cup \mathbb{Z}^*$ we have $$\mathcal{M} \models a \sqsubset b \quad \Leftrightarrow \quad \mathcal{M} \models \sigma(a) \sqsubset \sigma (b).$$ A partir de esto es fácil mostrar que tanto la hipótesis de las $0 \sqsubset 0^*$ $0^* \sqsubset 0$ conducir a contradicciones.

(También se pueden ver algunas anteriores preguntas relacionadas con el aquí y aquí.)