Decidibilidad y "valor de verdad"

Question

Se puede leer en el Página de Wikipedia para "Teoremas de incompletitud de Gödel" :

La indecidibilidad de un enunciado en un sistema deductivo particular no no aborda, por sí misma, la cuestión de si el valor de verdad de la afirmación está bien definido, o si se puede determinar por otros medios. La indecidibilidad sólo implica que el sistema deductivo particular sistema deductivo particular que se considera no prueba la verdad o la falsedad de la del enunciado. Si existen los llamados enunciados "absolutamente indecidibles" cuyo valor de verdad no puede conocerse nunca o está mal especificado, es un punto controvertido en la filosofía de las matemáticas.

Nota: El mismo texto aparece en el Página de Wikipedia para "Problema indecidible" .

No entiendo esto. Me parece que hay un par de teoremas en lógica matemática que, por el contrario, explican muy claramente la relación entre la indecidibilidad de un enunciado y su "valor de verdad": dependiendo del significado de "valor de verdad", estoy pensando en el teorema de tautología de Post y el teorema de completitud de Gödel.

¿Me estoy perdiendo algo? ¿Y qué quiere decir Wikipedia con "absolutamente indecidible"?

Permítanme que me explaye un poco para que quede claro. Entiendo que, según el teorema de completitud, una afirmación es indecidible si y sólo si existen modelos en los que es verdadera y otros modelos en los que es falsa. Además (o alternativamente), por el teorema de tautología de Post, un enunciado es indecidible si y sólo si existen algunas valoraciones de verdad para las que es verdadero y otras para las que es falso. En cualquier caso, la conclusión, me parece, es simplemente que un enunciado es indecidible si y sólo si su valor de verdad no está definido (puede ser "elegido" verdadero o falso arbitrariamente).

---

EDITAR . Permítanme añadir un par de observaciones después de leer las respuestas de 6005, user21820 y spaceisdarkgreen, que no me satisfacen del todo. Estas respuestas defienden el texto de Wikipedia interpretando el significado de "valor de verdad" relativamente a algún tipo de modelo correcto o peor, el mundo físico . Ninguna de estas nociones tiene cabida en la lógica matemática, me parece. Cuando hablamos de números naturales, nos gusta pensar que hay un modelo correcto, pero sería una tontería suponer que hay un "universo preferido" para cada teoría.

Por ejemplo, toma los 5 axiomas de Euclides para la geometría, quita el axioma #5 (el "postulado de la paralela") para que te quedes sólo con los primeros 4 axiomas (obtienes " geometría absoluta "). Tanto el plano euclidiano como el plano hiperbólico son modelos para esta teoría. ¿Es uno de los dos el "modelo correcto"? Evidentemente no, ya que nos deshicimos del quinto axioma que discriminaría entre los dos.

Así que en este punto me sigue pareciendo que la afirmación de Wikipedia sobre el "valor de verdad" sigue siendo irrelevante.

Answer 1

Es cierto que si un enunciado es indecidible (es decir, no es demostrable de una manera u otra, en un sistema deductivo dado), entonces hay modelos en los que es verdadero y modelos en los que es falso. Sin embargo, ésta no es 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 falsos, o modelos no estándar. En este sentido, creemos lo siguiente: toda afirmación sobre los números naturales es verdadera o falsa. (Esto es cierto incluso en la lógica matemática, donde por ejemplo hablamos de propiedades de los modelos "estándar" y "no estándar" de $\mathbb{N}$ .)

Sin embargo, el teorema de Godel puede interpretarse como un cuestionamiento de esta misma afirmación. Después de todo, si nunca podemos describir con precisión el conjunto de los números naturales $\mathbb{N}$ -- no en PA, ni en ZFC, ni en ninguna otra teoría (recursivamente axiomatizable) -- entonces ¿existe realmente una sola $\mathbb{N}$ que existe? ¿Tiene realmente sentido decir que toda afirmación sobre los números naturales es verdadera o falsa?

Algunos dirían que sí y otros que no. Es una cuestión filosófica, porque la pregunta es si se cree que hay un universo matemático ideal más allá de lo que podemos formalizar. Esa es la controversia de la que habla Wikipedia en este párrafo.

Answer 2

Tomemos como ejemplo la sentencia G de Gödel para PA (de primer orden) que es indecidible en PA. También es verdadera, pues afirma que no existe una prueba (número de Gödel de una) de sí misma, y efectivamente ese número/prueba no existe.

Y sin embargo, el teorema de completitud dice que como 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, falso o ninguno de los dos? Es verdadera como una afirmación literal sobre los números, y sin embargo está claro que hay modelos de AP que van en cualquier dirección. Lo único que nos dice esta segunda parte es que hay modelos de AP en los que algunas afirmaciones falsas sobre los números son verdaderas. Los axiomas de la AP no son suficientes para especificar de forma única un modelo de aritmética. Estos otros modelos sí existen y se denominan modelos no estándar de AP . El modelo de AP que conocemos en el amor -- donde el universo es $\mathbb N$ y los símbolos $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 difíciles en, digamos, la teoría de conjuntos ZFC, donde no hay un modelo "correcto" acordado que defina la "verdad teórica de los conjuntos".

Answer 3

Creo que esa frase 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 se cree en las propiedades clásicas de las cadenas finitas de un alfabeto finito). Esto no tiene nada que ver con la verdad semántica de la frase, independientemente del sistema deductivo. En el caso de los números naturales, podemos creer que se pueden incrustar en el mundo físico a través de la codificación como cadenas finitas, en cuyo caso toda sentencia aritmética tiene un valor de verdad bien definido. En otros casos, como la teoría de conjuntos ZFC, no se conoce ninguna incrustación física y, por tanto, hay razones para no creer que toda sentencia sobre ZFC tenga un valor de verdad bien definido, por lo que es más controvertido.

Además, aunque cada frase sobre un sistema tenga un valor de verdad bien definido (no mal especificado), no implica que podamos conocer ese valor de verdad ni siquiera en principio. Por ejemplo, aunque los "números naturales verdaderos" tengan una incrustación física, puede que no nos sea posible determinar el valor de verdad de alguna sentencia aritmética.

Además, añadiría lo siguiente.

En primer lugar, si creemos que la noción de demostrabilidad está bien definida, debemos creer también que toda $Σ_1$ -sentencia tiene un valor de verdad bien definido. Pero entonces es natural creer que toda sentencia aritmética tiene también un valor de verdad bien definido, como sigue. A $Π_2$ -sentencia afirma la verdad de $P(n)$ para cada natural $n$ , donde $P$ es algo $Σ_1$ -sentencia. Ya que $P(n)$ tiene un valor de verdad bien definido para cada $n$ (al sustituir el término que representa $n$ para el parámetro en $P$ ), tenemos que o bien todas son verdaderas o al menos una es falsa, por lo que la $Π_2$ -sentencia tiene un valor de verdad bien definido también. Por supuesto, este es un argumento filosófico, por lo que se puede discutir, pero la suposición inicial de que cada $Σ_1$ -sentencia tiene un valor de verdad bien definido es un salto mucho más grande que de eso a todas las sentencias aritméticas. Véase este post sobre los bloques de construcción para obtener detalles relacionados.

En segundo lugar, no hay una forma puramente matemática de precisar los números naturales, como puede verse por la existencia de modelos no estándar de cualquier sistema deductivo recursivo para ellos. Tampoco es posible utilizar la AP de segundo orden para precisarlos, porque la categoricidad es relativa al metasistema. Como se explica más adelante en este puesto En cuanto a los números naturales, cualquier justificación matemática es necesariamente circular, y parece que ni siquiera existe una justificación física de que haya una incrustación exacta en el mundo real de un modelo de AP, a pesar de su increíble precisión a escala humana.

En tercer lugar, incluso si asumimos la existencia de "el verdadero modelo $N$ de PA, no nos ayuda ni siquiera a determinar "las verdaderas subcolecciones" de $N$ . Nótese que toda teoría de primer orden (incluida la 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 expresar de forma muy concreta mediante la codificación por 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 )$ ", donde $pair$ es cualquier función de codificación razonable en $N$ . Si tal $X$ existía, que $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, aunque supongamos la existencia de "el verdadero modelo" de ZFC, no puede ser él mismo un objeto (conjunto) en el propio modelo, a pesar de ser como un conjunto, debido al axioma de fundamentación. 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 tales modelos sólo tienen conjuntos como elementos. Esta es una de las posibles razones por las que es muy controvertido suponer que tiene sentido asumir la existencia de un 'modelo verdadero' de ZFC.

En quinto lugar, en lo que respecta a la determinación del valor de verdad de las oraciones aritméticas aunque exista 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$ -sentencias, porque eventualmente encontraremos un testigo. Pero no podemos verificar computacionalmente el valor de verdad de las falsas $Σ_1$ -sentencias, de lo contrario podemos resolver el problema de la detención. Peor aún, incluso si podemos determinar de alguna manera el valor de verdad de todas las $Σ_n$ -de las frases, no implica que podamos hacer lo mismo para $Σ_{n+1}$ -de las sentencias, ya que el problema de detención relativizado a la $n$ -el salto de Turing no puede ser resuelto teniendo un oráculo de verdad para todos $Σ_n$ -sentencias. Esto está brevemente esbozado en este post relacionado .

Answer 4

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

• un axioma
• un teorema ya demostrado (sé que esto suena un poco circular, sólo 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 las listas posibles. La pregunta es: ¿todo predicado posible será un teorema o su negación será un teorema? ¿O hay propiedades que se pueden enunciar pero no son teoremas y sus negaciones tampoco son teoremas? Eso es todo lo que significa la incompletitud, al menos desde un punto de vista puramente sintáctico.

En cuanto a tu observación, la redacción del párrafo que citas no diría que es errónea, pero sí que resulta 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 una proposición que es indecidible en el sentido anterior, pero que sin embargo es verdadera (y por 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 apartado puede y debe ser mejorado. Nunca se puede exagerar en el nivel de precisión del lenguaje cuando se escribe sobre estos temas.