Decidibilidad y "valor de verdad"

Es cierto que si un enunciado es indecidible (es decir, no demostrable de un modo u otro, en un sistema deductivo dado), entonces hay modelos en los que es verdadero y modelos en los que es falso. Esta no es, sin embargo, la única forma de interpretar "si el valor de verdad del enunciado está bien definido" . En el caso de$\mathbb{N}$, en particular, es común creer que existen los números naturales "reales"$0, 1, 2, 3, \ldots$, y todos los demás modelos de aritmética son modelos falsos o no estándar. En este sentido, creemos lo siguiente: todo enunciado sobre los números naturales es verdadero o falso. (Esto es cierto incluso en la lógica matemática, donde por ejemplo hablamos de las propiedades de los modelos "estándar" y "no estándar" de$\mathbb{N}$.)

El teorema de Gödel, sin embargo, puede interpretarse como que cuestiona esta misma afirmación. Después de todo, si nunca podemos describir con precisión el conjunto de números naturales$\mathbb{N}$-- ni en PA, ni en ZFC, ni en ninguna otra teoría (axiomatizable recursivamente) -- entonces realmente hay una sola$\mathbb{N}$¿eso existe? ¿Realmente tiene sentido decir que todo enunciado sobre los números naturales es verdadero o falso?

Algunos dirían que sí, y algunos dirían que no. Es una cuestión filosófica, porque la pregunta es si crees que existe un universo matemático ideal más allá de lo que podamos formalizar. Esa es la polémica de la que habla Wikipedia en este párrafo.

Tomemos como ejemplo la oración de Gödel G para (primer orden) PA que es indecidible en PA. También es cierto, porque afirma que no existe un (número de Gödel de a) prueba de sí mismo, y de hecho ese número/prueba no existe.

Y, sin embargo, el teorema de completitud dice que, dado que PA+$\lnot$G es consistente, tiene un modelo, es decir, alguna interpretación de la aritmética de primer orden tiene G falso.

Entonces, ¿G es verdadero o falso o ninguno de los dos? Es cierto como una declaración literal sobre números y, sin embargo, está claro que hay modelos de PA que van en cualquier dirección. Lo que realmente nos está diciendo esta segunda parte es que hay modelos de PA en los que algunas afirmaciones falsas sobre los números son verdaderas. Los axiomas de PA no son suficientes para especificar de manera única un modelo de aritmética. Estos otros modelos existen y se denominan modelos no estándar de PA . El modelo de PA que conocemos en el amor: donde está el universo$\mathbb N$y los simbolos$0,$ $S,$ $+$en el lenguaje de la aritmética tienen sus interpretaciones habituales - se llama el modelo estándar de PA.

La clave aquí es que tenemos un modelo particular al que nos referimos cuando decimos que algo es cierto. Las cosas se ponen un poco más complicadas, por ejemplo, en la teoría de conjuntos ZFC, donde no hay un modelo "correcto" acordado que defina la "verdad teórica establecida".

Creo que esa oración no es 100% precisa, pero pretendía significar:

La indecidibilidad de una oración sobre un sistema deductivo es simplemente si ese sistema prueba o refuta la oración, y es una cuestión puramente sintáctica (al menos si cree en las propiedades clásicas de cadenas finitas de un alfabeto finito). Esto no tiene nada que ver con la verdad semántica de la oración independiente del sistema deductivo. En el caso de los números naturales, podemos creer que pueden integrarse en el mundo físico mediante la codificación como cadenas finitas, en cuyo caso cada oración aritmética tiene un valor de verdad bien definido. En otros casos, como la teoría de conjuntos de ZFC, no se conoce una incrustación física y, por lo tanto, hay razones para no creer que cada oración sobre ZFC tiene un valor de verdad bien definido, por lo que es más controvertido.

Además, incluso si cada oración sobre un sistema tiene un valor de verdad bien definido (no mal especificado), eso no implica que podamos conocer ese valor de verdad, incluso en principio. Por ejemplo, incluso si los 'números naturales verdaderos' tienen una incrustación física, puede que no nos sea posible determinar el valor de verdad de alguna oración aritmética.

Además, agregaría lo siguiente.

En primer lugar, si creemos que la noción de demostrabilidad está bien definida, también debemos creer que todo$Σ_1$-La oración tiene un valor de verdad bien definido. Pero entonces es natural creer que cada oración aritmética también tiene un valor de verdad bien definido, como sigue. A$Π_2$-La oración afirma la verdad de$P(n)$para cada natural$n$, dónde$P$es algo$Σ_1$-oración. Desde$P(n)$tiene un valor de verdad bien definido para cada natural$n$(al sustituir el término que representa$n$para el parámetro en$P$), tenemos que o todas son verdaderas o al menos una es falsa, por lo que el original$Π_2$-la oración también tiene un valor de verdad bien definido. Por supuesto, este es un argumento filosófico, por lo que uno puede discutirlo, pero la suposición inicial de que cada$Σ_1$-la oración tiene un valor de verdad bien definido es un salto mucho mayor que de eso a todas las oraciones aritméticas. Consulte esta publicación sobre bloques de construcción para obtener detalles relacionados.

En segundo lugar, no existe una forma puramente matemática de precisar los números naturales, como se desprende de la existencia de modelos no estándar de cualquier sistema deductivo recursivo para ellos. También es imposible utilizar PA de segundo orden para precisarlos, porque la categorización es relativa al metasistema. Como se explica más detalladamente en esta publicación , cualquier justificación matemática para los números naturales es necesariamente circular, y parece que ni siquiera hay una justificación física de que haya una incrustación exacta en el mundo real de un modelo de PA, a pesar de su increíble precisión en humanos. escamas.

En tercer lugar, incluso si asumimos la existencia del 'modelo verdadero'$N$de PA, no nos ayuda ni siquiera a determinar 'las verdaderas subcolecciones' de$N$. Tenga en cuenta que cada teoría de primer orden (incluida ZFC) tendrá, si es consistente, un modelo contable. Así que cualquier teoría de primer orden$T$que axiomatiza las subcolecciones de$N$tendrá un modelo contable, pero suposiciones muy débiles nos obligan a aceptar también que dentro de cualquier modelo de$T$las subcolecciones de$N$son incontables. Esto se puede afirmar de manera muy concreta a través de la codificación de pares como "$\neg \exists X ⊆ N\ \forall Y ⊆ N\ \exists c \in N\ \forall k \in N\ ( k \in Y ⇔ pair(c,k) \in X )$", dónde$pair$hay alguna función de codificación razonable en$N$. Si tal$X$existió, deja$Z = \{ k : k \in N \land pair(k,k) \notin X \}$, cuya construcción está permitida en casi cualquier sistema fundacional, por lo que para cada$c \in N$tenemos$c \in Z ⇔ pair(c,c) \in X$por la propiedad definitoria de$X$pero$c \in Z ⇔ pair(c,c) \notin X$por definición de$Z$, y por lo tanto la contradicción.

En cuarto lugar, incluso si asumimos la existencia del 'modelo verdadero' de ZFC, no puede ser en sí mismo un objeto (conjunto) en el modelo mismo, a pesar de ser como un conjunto, debido al axioma de fundamento. Más precisamente, si definimos "modelo" dentro de ZFC, podemos mostrar que cualquier modelo (conjunto) de ZFC no se tiene a sí mismo como elemento. Este problema no desaparece si consideramos los modelos de 'clase' de ZFC, porque dichos modelos solo tienen conjuntos como elementos. Esta es una posible razón por la que es muy controvertido suponer que tiene sentido suponer la existencia de un "modelo verdadero" de ZFC.

En quinto lugar, con respecto a la determinación del valor de verdad de las oraciones aritméticas, incluso si existe una incrustación de naturales en el mundo real, se puede argumentar que, en principio, podemos determinar el valor de verdad de las oraciones verdaderas.$Σ_1$-frases, porque al final encontraremos un testigo. Pero no podemos verificar computablemente el valor de verdad de falso$Σ_1$-frases, de lo contrario podemos resolver el problema de la detención. Peor aún, incluso si de alguna manera podemos determinar el valor de verdad de todos$Σ_n$-frases, no implica que podamos hacer lo mismo para$Σ_{n+1}$-frases, ya que el problema de la detención relativizado al$n$-el salto de Turing no se puede resolver teniendo un oráculo de la verdad para todos$Σ_n$-oraciones. Esto se esboza brevemente en este post relacionado .

Indecidible es indecidible bajo cierto sistema deductivo. Decidible significa que es un teorema o su negación es un teorema, entendido en un sentido muy específico. Un teorema aquí es la línea final de una lista de enunciados tales que cada uno de ellos es

• un axioma
• un teorema ya probado (sé que esto suena un poco circular, solo intento dar una idea)
• el resultado de aplicar modus ponens o algunas otras reglas lógicas a las líneas anteriores de la lista.

Si el número de axiomas es finito o enumerable, es "fácil" pensar en todas esas listas posibles. La pregunta es: ¿todo predicado posible será un teorema o su negación será un teorema? ¿O hay propiedades que puedes enunciar pero que no son teoremas y sus negaciones tampoco son teoremas? Eso es todo lo que significa la incompletud, al menos desde un punto de vista puramente sintáctico.

Con respecto a su observación, la redacción del párrafo que cita no diría que es incorrecta, pero se vuelve un poco confusa, ya que hay resultados sobre la indecidibilidad (como el teorema de incompletitud de Gödel) que SÍ abordan la cuestión del valor de verdad: nos presenta con una proposición que es indecidible en el sentido anterior, pero sin embargo es verdadera (y por lo tanto tiene un valor de verdad bien definido).

La cita dice algo así como "la indecidibilidad no aborda la cuestión de si el valor de verdad está bien definido", y bueno... No: la "indecidibilidad" no lo hace; Gödel, tal vez. =S

Seguro que ese párrafo puede y debe mejorarse. Nunca puedes exagerar en el nivel de precisión de tu lenguaje cuando escribes sobre estos temas.