¿Son los números naturales estándar un modelo destacado de PA?

Ampliando el comentario de Qiaochu, el modelo estándar$\mathbb{N}$es el modelo mínimo único (hasta el isomorfismo) de PA en el sentido de incrustaciones. Es decir, lo siguiente es cierto:

• $\mathbb{N}$se integra de manera única en cada modelo de PA. Además, si$\mathcal{M}$es elementalmente equivalente a$\mathbb{N}$, entonces la incrustación de$\mathbb{N}$en$\mathcal{M}$es elemental

• Si$\mathcal{M}$es un modelo de PA no isomorfo a$\mathbb{N}$, entonces$\mathcal{M}$no se incrusta en$\mathbb{N}$.

Cada uno de estos hechos es un ejercicio sencillo de teoría de modelos; el punto clave es que$\mathbb{N}$se caracteriza únicamente entre los modelos de PA (hasta el isomorfismo) por el principio de inducción de segundo orden . Además de dar otra caracterización de$\mathbb{N}$(expresado de otra manera:$\mathbb{N}$es el único modelo bien ordenado de PA), la inducción de segundo orden nos permite razonar, bueno, inductivamente al comparar modelos arbitrarios de PA con$\mathbb{N}$. Por ejemplo, si$\mathcal{M}$es un modelo de PA, construimos una incrustación$f_\mathcal{M}: \mathbb{N}\rightarrow\mathcal{M}$por inducción como:

• $f_\mathcal{M}(0)=0^\mathcal{M}$, y

• haber definido$f_\mathcal{M}(n)$, dejamos$f_\mathcal{M}(n+1)=f_\mathcal{M}(n)+^\mathcal{M}1^\mathcal{M}$.

Por el principio de inducción de segundo orden para$\mathbb{N}$, esto de hecho define un mapa de$\mathbb{N}$a$\mathcal{M}$, y no es difícil mostrar que este mapa es una incrustación.

Tenga en cuenta, por cierto, que PA es exagerado aquí: podemos reemplazarlo por la teoría de los números naturales con sucesor. ¡Esta teoría, en contraste con PA, es completa y decidible!

Otra caracterización muy diferente de$\mathbb{N}$es vía computabilidad: el modelo estándar de PA es el único modelo contable de PA con una presentación computable , por el teorema de Tennenbaum . Este es un resultado más complicado. En particular, si bien la AP sigue siendo excesiva, existen teorías de la aritmética mucho más fuertes que la aritmética con sucesor que son demasiado débiles para que el fenómeno de Tennenbaum las sostenga.