Hay este ejercicio en Modelos de Aritmética de Peano (Kaye 1991, p.157), que pide definir una relación binaria recursiva en $\mathbb{N}^2$, tal que $M \upharpoonright < $ sea isomorfo a $(\mathbb{N}, \prec)$, donde $\prec$ es la relación definida anteriormente, y $M \vDash PA$ es numerable y no estándar (lo que significa que $+^M$ y $\cdot^M$ no son recursivos para el teorema de Tennenbaum). Ahora, no puedo entender cómo debería definir esta relación. La relación estándar obviamente no funciona, porque no habría isomorfismo, pero no puedo encontrar una adecuada.
Respuesta
¿Demasiados anuncios?
Oli
Puntos
89
Sea $M$ un modelo no estándar contable. Desde un punto de vista ordenado, el modelo consiste en una copia de los números naturales, seguido por un conjunto ordenado que es isomorfo a $I\times \mathbb{Z}$. Aquí $I$ es un conjunto ordenado densamente sin primer o último elemento, $\mathbb{Z}$ tiene el orden natural, y $I\times Z$ está ordenado lexicográficamente.
Pero todos los conjuntos densamente ordenados contables sin primer o último elemento son orden-isomorfos a los números racionales.
Añadido: Damos más detalles sobre la existencia de un ordenamiento recursivo. Para cualquier número natural $n$ (estamos incluyendo $0$), sea el tipo de $n$ el más grande $k$ tal que $2^k$ divide a $n$. Mapeamos los números tipo $0$ biyectivamente a $\mathbb{N}$, los números tipo $1$ biyectivamente a una copia de $\mathbb{Z}$, los objetos tipo $2$ biyectivamente a una copia de $\mathbb{Z}$, y así sucesivamente.
Resta definir el orden. Enumera los racionales en el intervalo $(0,1)$ como $r_1,r_2, r_2,\dots$. Los tipos no nulos (párrafo anterior) pueden identificarse biyectivamente con los racionales. Ahora en los tipos, define el orden heredado de los racionales.
