Sobre "La vida en un mundo inconsistente" de Pudlak

Question

En su Fundamentos lógicos de las matemáticas y la complejidad computacional (2013), Pavel Pudlak invita a los lectores a reflexionar sobre personas ficticias cuyos números naturales no son estándar. Su exposición se incluye en la sección 6.1, en la subsección Interludio - La vida en un mundo inconsistente .

Primero asume (implícitamente) la Aritmética de Peano $\mathrm{PA}$ es consistente. La teoría $\mathrm{PA + \neg Con(PA)}$ es consistente por el Segundo Teorema de Incompletitud, teniendo así un modelo $M$ . Luego nos insta a pensar en un mundo $\mathcal W$ donde los números naturales son $M$ .

Explica qué tipo de fenómeno desconcertante se produce en $\mathcal W$ .

[...] Supongamos que estas personas descubren una de las pruebas de contradicción en $\mathrm{PA}$ . Entonces se sentirían muy frustrados al tratar de determinar la teoría de los números naturales. Por un lado verían que los axiomas de la Aritmética de Peano se satisfacen en sus números naturales, por otro lado sabrían que los axiomas son inconsistentes. Como los axiomas son verdaderos, pero aún se puede derivar una contradicción de ellos, concluirían que la lógica falla . [...]

El problema es que no entiendo bien el pasaje. En particular, no está claro qué sistema lógico utilizan las personas en $\mathcal W$ utilizar al escribir "las pruebas de contradicción $\mathrm{PA}$ ."

Le agradecería que explicara el pasaje de forma más técnica y detallada.

Answer 1

Para hablar de estas cosas semánticamente, es más fácil trabajar en el sistema $\mathsf{ACA}_0$ de la aritmética de segundo orden. Este sistema es una extensión conservadora de la aritmética de Peano para sentencias en el lenguaje de la aritmética de Peano, pero $\mathsf{ACA}_0$ es capaz de tratar directamente con predicados de satisfacción (verdad). Si no conoces los detalles, para el resto de este post puedes simplemente tratar $\mathsf{ACA}_0$ como una versión de segundo orden de la aritmética de Peano.

Un punto clave sobre $\mathsf{ACA}_0$ es que se puede axiomatizar con un finito conjunto de axiomas. Por lo tanto, no tenemos que preocuparnos por los axiomas "no estándar" cuando examinamos modelos no estándar: podemos suponer simplemente que se utiliza el conjunto finito de axiomas. Esto no es cierto en el caso de la aritmética de Peano, lo que complica el argumento de Pudlak: la aritmética de Peano no es finitamente axiomatizable. El hecho de que $\mathsf{ACA}_0$ es finitamente axiomatizable es una buena razón para mirarlo en su lugar.

Supongamos que $M$ es un modelo de $\mathsf{ACA}_0 + \lnot \text{Con}(\mathsf{ACA}_0)$ . Esto significa que, en $M$ hay un número natural $c$ que codifica una prueba de $\lnot \text{Con}(\mathsf{ACA}_0)$ . La prueba codificada por $c$ utiliza la lógica de primer orden normal, usando sólo los axiomas de $\mathsf{ACA}_0$ . Porque podemos utilizar un sistema deductivo para la lógica de primer orden que sólo tiene un número finito de reglas de deducción, y porque $\mathsf{ACA}_0$ es realmente consistente, $c$ debe codificar una prueba de no estándar longitud cuando se ve desde fuera $M$ .

Siguiendo a Pudlak, supongamos que alguien que vive en $M$ reconoce que todos los axiomas (de número finito) de $\mathsf{ACA}_0$ son verdaderos en $M$ pero también reconocen que $c$ codifica una prueba de $0=1$ de estos axiomas. ¿Por qué no es una contradicción?

Para la persona en $M$ para ver la contradicción, tendrían que demostrar por inducción que, para cada prueba codificada y cada $n$ si todas las declaraciones de las líneas $0, 1, \ldots, n$ de una prueba son verdaderas, entonces también lo es la afirmación de la línea $n+1$ (suponiendo que la prueba tenga $n+1$ o más líneas). Si pudieran demostrar eso, podrían demostrar que $0=1$ es cierto en $M$ Aunque sepan que $0=1$ no es cierto en $M$ porque $M$ satisface $\mathsf{ACA}_0$ .

El problema para la persona en $M$ es que el principio de inducción necesario en esa prueba forma parte del $\Sigma^1_1$ esquema de inducción, y ese esquema no es demostrable desde $\mathsf{ACA}_0$ . De hecho, $\mathsf{ACA}_0$ más el $\Sigma^1_1$ El esquema de inducción demuestra $\text{Con}(\mathsf{ACA}_0)$ . Así que la persona en $M$ verá que $\Sigma^1_1$ la inducción falla.

Eso podría interpretarse como que "la lógica falla" si la persona en $M$ cree que $\Sigma^1_1$ La inducción es parte de la lógica. Dicho más claramente, la persona en $M$ ciertamente pensaría que "la lógica de primer orden no es sólida" en el sentido de que una oración falsa puede ser derivada de oraciones verdaderas en una forma "finita" (en $M$ ) número de pasos. (Al mismo tiempo, sabemos que $\mathsf{ACA}_0$ demuestra el teorema de solidez de la lógica de primer orden - pero eso se refiere a otra cosa, en este contexto).

Answer 2

Una prueba (estilo Hilbert) de $\phi$ de una teoría (de primer orden) $T$ es una secuencia finita de frases $\phi_1,\dots,\phi_n$ , donde $\phi$ es $\phi_n$ y cada $\phi_i$ es una instancia de un axioma lógico, una frase en $T$ o viene de oraciones anteriores en la secuencia vía modus ponens o una de las reglas lógicas que tratan con cuantificadores.

Hay variantes de esta definición, pero todas son muy similares, y lo que sigue puede adaptarse directamente para aplicarse también a ellas.

Trabajar en $\mathsf{PA}$ Cuando tenemos números pero no frases, o secuencias, tenemos que arreglárnoslas mediante la codificación. Esto requiere cierto cuidado. La propiedad clave de $\mathsf{PA}$ es que podemos realizar construcciones recursivas, ya que podemos codificar secuencias finitas de números a través de números. Esto no es del todo evidente, véase aquí para un ejemplo. Lo utilizamos de la siguiente manera: Comenzamos seleccionando un conjunto recursivo de números para codificar los símbolos de nuestro lenguaje. Una vez hecho esto, podemos codificar cadenas de símbolos, fórmulas y secuencias de fórmulas. Podemos asociar a $\mathsf{PA}$ un conjunto recursivo de números que codifican las sentencias de $\mathsf{PA}$ y tenemos una fórmula $\psi(x,y)$ que se mantiene si $x$ es el código de una frase, y $y$ es el código de una prueba en $\mathsf{PA}$ de la frase codificada por $x$ . (La forma en que los conjuntos recursivos y las funciones recursivas se representan en $\mathsf{PA}$ también requiere algunos cuidados técnicos. Las referencias que menciono en el enlace anterior abordan todos estos detalles con detenimiento). Además, siempre que $\mathsf{PA}$ prueba $\phi$ podemos codificar la prueba por un número $m$ y $\phi$ por un número $n$ y podemos demostrar en $\mathsf{PA}$ que $\psi(n,m)$ se mantiene. (Más formalmente, la afirmación $\forall x\,\forall y\,(\tau_n(x)\land\tau_m(y)\to\psi(x,y))$ es demostrable. Aquí, $\tau_k(x)$ es "la" fórmula que establece que $x$ "es" $k$ .) Además, dado cualquier número $n,m$ , si $n$ no codifica una sentencia, o si lo hace pero $m$ no codifica una prueba de esa frase, entonces $\mathsf{PA}$ también demuestra $\lnot\psi(n,m)$ .

Ahora, el punto es este: En los modelos no estándar, habrá números no estándar $n$ y $m$ tal que $\psi(n,m)$ se satisface en el modelo. Esto es lo que se quiere decir cuando decimos que la gente del modelo ve una prueba de "la sentencia codificada por $n$ ". En el modelo $\mathcal M$ Pudlak está describiendo, si $n$ es el código para $0=1$ hay una "prueba" $m$ con $\psi(n,m)$ que se encuentra en $\mathcal M$ . Este $m$ es necesariamente no estándar. Tal vez tenga una longitud no estándar, por lo que no está codificando realmente una secuencia. O tal vez algunos de los "axiomas" utilizados en la "secuencia" codificada por $m$ no son estándar, por lo que no son realmente sentencias. O tal vez tanto la longitud de la secuencia como la longitud de algunas de las frases utilizadas allí no son estándar.

Answer 3

Es una figura retórica común para volver a presentar una proposición $P$ que es independiente de un sistema formal concreto $S$ y de una forma lógica que puede decidirse mediante ejemplos (por ejemplo, mostrar una solución demuestra que una ecuación es resoluble, y escribir una prueba de $0=1$ demuestra incoherencia) como que tiene ejemplos que son "no estándar" y existen en un "modelo no estándar".

Esta forma de hablar de los testigos no estándar es el replanteamiento semántico equivalente (por el teorema de completitud) del concepto sintáctico de que un enunciado es indecidible. El teorema de completitud es una correspondencia entre la sintaxis y la semántica de las teorías de primer orden.

Añadir una declaración independiente a un sistema preserva la coherencia. El teorema de completitud afirma que el sistema más el enunciado independiente (o su negación) tiene un modelo. Si la adición es un enunciado existencial indecidible $\exists x Q(x)$ ese modelo contendrá un elemento $x$ para lo cual $Q(x)$ es cierto (un testigo). Si la adición es la negación de un enunciado universal indecidible $\forall y Q(y)$ ese modelo contendrá un elemento $y$ para lo cual $Q(y)$ es falso (un contraejemplo). Para cuantificadores anidados más complicados, el modelo podría tener que contener estructuras más grandes, como conjuntos y funciones y otras colecciones de muchos $x$ con el fin de (in)validar $P$ Ya no tienen que ser elementos únicos y no hay necesariamente una palabra sencilla como "contraejemplo" para describir la relación del certificado de verdad/falsedad con la proposición.

Las palabras verdadero y estándar se refieren a una situación en la que un supersistema más poderoso de $S$ (como una teoría de conjuntos, cuando $S$ es una teoría de la aritmética) demuestra que $S$ tiene un tipo de modelo preferido (por lo tanto "estándar"), tal vez uno único, que satisface propiedades adicionales, y también puede demostrar que el $S$ -independiente es verdadera en ese modelo (y, tal vez, también verdadera en cada modelo del supersistema).

---

El vocabulario no estándar es más común cuando el sistema base es una teoría de la aritmética como $PA$ ya que en ese caso se puede aplicar el lenguaje desarrollado y las intuiciones de los modelos no estándar de la aritmética. No se trata de extensiones aleatorias en las que se "añaden más cosas" a un modelo estándar, sino que tienen tipos de orden muy restringidos y una noción suficientemente clara de que los enteros positivos adicionales son infinitamente grandes pero con propiedades bien definidas.

En esta metáfora, puede existir una prueba de inconsistencia no estándar para un sistema consistente, pero tiene longitud $L$ para $L$ un número entero positivo no estándar (por tanto, infinito).

Lo que se puede probar en el sistema $S$ sólo implica pruebas cuya longitud se mide con enteros finitos estándar. El hecho de que esto coexista con pruebas no estándar infinitamente largas se debe a que estas últimas reflejan lo que es verdadero en el modelo, y la verdad es una propiedad más débil que ser demostrable. Cualquier prueba no estándar $L$ que es la longitud (o código) de una prueba de inconsistencia también admitiría pruebas que $L >1$ , $L > 2$ , $L>3$ y $L > n$ para cualquier $n$ que puede escribirse en un número finito de símbolos.

---

Desde un punto de vista más escéptico, el pasaje del libro no es más que una referencia evocadora al concepto indefinido de que la gente "ve que sus números naturales son un modelo de la Aritmética de Peano" (lo que también supone que está bien definido hablar de "sus números naturales" por separado del sistema similar a la AP en su mundo hipotético).