Infinitos modelos no isomórficos para la función sucesora

Question

Estoy tratando de resolver el siguiente ejercicio:

Dejemos que $L=\{0,S\}$ , donde $0$ es un símbolo constante y $S$ es un símbolo de función unario. Sea $T$ sea el conjunto de $L-$ frases. \begin{align*} & \forall x \forall y (S(x)= S(y) \rightarrow x = y) \\ & \forall y (y \neq 0 \rightarrow \exists x (S(x)=y)) \\ & \forall x (S(x) \neq 0) \\ & \forall x (S^n(x)\neq x) \quad , n \in \omega \end{align*} Demostrar que $T$ tiene infinitos modelos contables no isomórficos por pares.

Obtenemos un modelo $M$ para $T$ al establecer $M := \{\mathbb{N};0_{\mathbb{N}},x+1\}$ . Ahora tenemos uno de los infinitos modelos contables. Lo utilizaré como punto de partida para todos los demás.

Quiero definir un modelo $M_n , n \in \omega$ sobre el universo $ \mathbb{N} \sqcup \mathbb{Z} \sqcup \dots \sqcup \mathbb{Z}$ con $n$ $\mathbb{Z}$ 's. Entonces cualquier $x \in M_n$ puede expresarse como $x = (i_x, a_x), i \in \{0,...,n\}$ con el $a_x$ siendo un número natural para $i_x=0$ y un número entero en caso contrario. La interpretación del cero será $(0,0)$ y $S(i_x,a_x)=(i_x,a_x+1)$ . Entonces $M_n$ modelos $T$ .

Queda por demostrar que el $M_n, n\in \omega$ no son isomorfas entre sí.

Mi enfoque es el siguiente: Si considero una ordenación $<$ en $\mathbb{N}$ respectivamente $\mathbb{Z}$ Puedo demostrar que el $M_n$ son pares no isomorfos. Introduzco una ordenación en cada $\mathbb{Z}$ por $0,1,-1,2,-2,...$ . Entonces el tipo de orden de $M_n$ es la suma de $n+1$ $\omega$ por lo que todos los $M_n$ son pares no isomorfos.

Sin embargo, me temo que esto no es realmente una solución.

Problema 1: $L$ no contiene el símbolo de una orden. Por lo tanto, ¿es siquiera legítimo crear una nueva estructura en forma de orden? E incluso si lo es, ¿hay alguna manera de demostrar la no isomorfia utilizando lo que se da con $L$ ¿solo?

Problema 2: Probablemente esté relacionado con el problema 1. Si todo lo que he hecho está realmente bien, ¿hay alguna forma de identificar el isomorfismo de modelos con el isomorfismo de tipos de orden? Porque lo que en realidad quiero es lo primero (es decir, un mapeo biyectivo entre los dos universos, es decir, que se conserve toda la estructura).

Problema 3: Si pedimos $\mathbb{Z}$ como se ha indicado, tenemos que asegurarnos de que todos los elementos menos el cero tienen un predecesor (resp. son sucesores), por lo que la función successur tendría que moverse a lo largo de $ \mathbb{N} \sqcup \mathbb{Z} \sqcup \dots \sqcup \mathbb{Z}$ por

$0 \rightarrow 1 \rightarrow ...\rightarrow -m \rightarrow -m+1 \rightarrow ...0 \rightarrow 1 \rightarrow ...\rightarrow m \rightarrow m+1 \rightarrow ...\rightarrow-m, ...$

A diferencia de la ordenación $0,1,2,...,0,1,-1,2,...0,1,-1,...$ . ¿Puede esto dar lugar a complicaciones?

Observación: Sé que hay preguntas similares sobre la función sucesora, sin embargo las respuestas no entran en detalle sobre la parte con la no isomorfa $M_n$ .

Se agradece cualquier ayuda. Gracias.

Answer 1

Dejemos que $M$ sea un modelo de $T$ con $f$ la interpretación del símbolo de la función $S$ .

Si $a$ y $b$ son miembros de (el conjunto subyacente de) $M$ Llama a $a$ y $b$ equivalente si existe un número entero no negativo $k$ tal que $b=f^{k}(a)$ o $a=f^{k}(b)$ . Se trata de una relación de equivalencia. En $M_n$ el número de clases de equivalencia es $1$ más que el número de copias de $\mathbb{Z}$ .

Dejemos que $M$ y $M'$ ser modelos de $T$ y que $\varphi$ sea un isomorfismo de $M$ a $M'$ . Entonces $a$ equivale a $b$ si y sólo si $\varphi(a)$ equivale a $\varphi(b)$ . Por lo tanto, la cardinalidad del número de clases de equivalencia es un invariante de isomorfismo, y por lo tanto el $M_n$ no son isomorfas entre sí.

Nota: : Es legítimo producir un pedido parcial en cualquier modelo de $T$ En la línea que has descrito. Y en sus modelos, uno puede describir un orden total, que aunque tiene un carácter algo arbitrario, se comporta razonablemente bien bajo isomorfismo.

Para modelos más generales de $T$ En la actualidad, hay muchas extensiones no isomorfas del orden parcial natural a un orden total, por lo que imponer dicho orden total no es útil para discutir el isomorfismo y el no isomorfismo.

No entiendo el tercer problema. En cualquier modelo de $T$ cualquier clase de equivalencia que no contenga la interpretación de $0$ tiene un orden natural isomorfo al orden habitual en $\mathbb{Z}$ . No hay ninguna razón para introducir un ordenamiento bueno, ni una forma natural de hacerlo.

Answer 2

Como indica la respuesta de André Nicolas, una forma más sencilla de resolver este problema es utilizar una relación de equivalencia, en lugar de una ordenación. Permítanme explicar lo que ocurre cuando se aborda este problema utilizando un ordenamiento.

Como se alude en el problema 1, si se introduce un ordenamiento, hay que asegurarse de que se respeta por isomorfismos. Es decir, puedes definir un orden $<$ en $M_n$ pero para poder utilizar estas órdenes para decirle al $M_n$ aparte, habría que saber que cualquier isomorfismo $f:(M_m,S)\to (M_n,S)$ es también un isomorfismo de conjuntos ordenados $f:(M_m,<)\to (M_n,<)$ . Normalmente, la forma de comprobar una condición como ésta es observando que $<$ se define mediante la operación $S$ y ninguna otra estructura de los conjuntos $M_n$ por lo que es rutinario verificar que una biyección que preserva la operación $S$ también debe conservar la relación $<$ . Sin embargo, esto no es obviamente cierto en su caso: su definición de $<$ utiliza su descripción explícita del conjunto $M_n$ como si se tratara de copias de $\mathbb{Z}$ (y $\mathbb{N}$ ), y no se indica en términos de la operación $S$ .

De hecho, resulta que su pedido $<$ hace no satisfacen la condición anterior. Es decir, existen isomorfismos entre las estructuras $(M_n,S)$ que no conservan el orden $<$ . Por ejemplo, consideremos el mapa $f:M_1\to M_1$ dado por $f(0,a)=(0,a)$ y $f(1,a)=(1,a+1)$ . Se trata de una biyección que preserva $S$ , pero no conserva su ordenación $<$ (por ejemplo, $(1,0)<(1,-1)$ pero $f(1,0)=(1,1)>(1,0)=f(1,-1)$ ).

Así que, lamentablemente, no hay forma aparente de utilizar su ordenamiento para mostrar el $M_n$ no son isomorfas. Sin embargo, se puede utilizar un ordenamiento diferente. Permítame definir un orden parcial $\prec$ en cualquier modelo $M$ de $T$ de la siguiente manera. Decimos que $x\prec y$ si existe un número entero positivo $n$ tal que $y=S^n(x)$ . En $M_n$ esto corresponde a la ordenación habitual de cada $\mathbb{Z}$ (sin embargo, $\prec$ no es una orden total si $n>0$ ya que los elementos de diferentes copias de $\mathbb{Z}$ o $\mathbb{N}$ son incomparables).

Desde $\prec$ se define para cualquier modelo de $T$ utilizando únicamente la operación $S$ es fácil ver que se preserva por isomorfismos. Explícitamente, si $f:(M,S)\to (N,S)$ es un isomorfismo de modelos de $T$ y $x,y\in M$ , entonces si $x\prec y$ en $M$ entonces $x=S^n(y)$ así que $f(x)=f(S^n(y))=S^n(f(y))$ así que $f(x)\prec f(y)$ (y de forma similar a la inversa).

Así que si $M_n$ y $M_m$ son isomorfos, entonces los conjuntos ordenados $(M_n,\prec)$ y $(M_m,\prec)$ sería isomorfo. Pero se puede verificar que $(M_n,\prec)$ es isomorfo a la unión disjunta de una copia de $\omega$ y $n$ copias de $\mathbb{Z}$ (con sus órdenes habituales). Como estos conjuntos parcialmente ordenados no son isomorfos para diferentes valores de $n$ El $M_n$ no son isomorfas para diferentes valores de $n$ . (Pero esto plantea la cuestión de cómo demostrarías realmente que estos conjuntos parcialmente ordenados no son isomorfos, y para hacerlo probablemente acabarías utilizando la relación de equivalencia de la respuesta de André Nicolas).