Verdadero vs. Probable

Question

Primer teorema de incompletitud de Gödel afirma que "...Para cualquier sistema de este tipo, siempre habrá afirmaciones sobre los números naturales que sean verdaderas, pero que sean indemostrables dentro del sistema".

¿Qué significa que una afirmación es verdadera si no es demostrable?

¿Cuál es la diferencia entre verdadero y demostrable?

Answer 1

Considere esta afirmación: John Smith nunca podrá demostrar que esta afirmación es cierta.

Si la afirmación es falsa, John Smith podrá demostrar que es verdadera. Pero está claro que eso no puede ser, ya que es imposible demostrar que un enunciado falso es verdadero. (Suponiendo que John Smith sea sensato).

Si es verdad, no hay contradicción. Sólo significa que John Smith no podrá demostrar que es verdad. Así que es cierto, y John Smith no será capaz de demostrar que es cierto. Esto es un límite a lo que Juan Pérez puede hacer. (Así que si John Smith es sensato, hay verdades que no puede probar).

Lo que Goedel demostró es que para cualquier sistema de axiomas formales sensato, habrá versiones formales de "este sistema de axiomas no puede demostrar que esta afirmación es verdadera". Será una afirmación expresable en ese sistema formal pero, obviamente, no demostrable dentro de ese sistema de axiomas.

Answer 2

Probable significa que existe una prueba formal utilizando los axiomas que se quieren utilizar. El conjunto de axiomas (en este caso los axiomas para la aritmética, es decir, los números naturales) es el "sistema" que menciona tu cita. Los enunciados verdaderos son los que se mantienen para los números naturales (en esta situación particular).

El objetivo de los teoremas de incompletitud es que para cualquier sistema razonable de axiomas para los números naturales siempre habrá enunciados verdaderos que sean indemostrables. Por supuesto, puedes hacer trampa y decir que tus axiomas son simplemente todas las afirmaciones verdaderas sobre los números naturales, pero esto no es un sistema razonable, ya que no hay ningún algoritmo que decida si una afirmación dada es o no uno de tus axiomas.

Como nota al margen, tu cita es esencialmente el primer teorema de incompletitud, en la forma en que se deduce fácilmente del segundo.

En general (no hablando sólo de números naturales) dada una estructura, es decir, un conjunto junto con relaciones sobre el conjunto, constantes en el conjunto y operaciones sobre el conjunto, hay una forma natural de definir cuándo una sentencia (de primer orden) que utiliza los símbolos correspondientes para sus relaciones, constantes y operaciones es válida en la estructura. ( $\forall x\exists y(x\cdot y=e)$ es una frase que utiliza símbolos correspondientes a las constantes y operaciones que se encuentran en un grupo, y la frase dice que todo elemento tiene un inverso).

Así que esto define lo que es cierto en una estructura. Para demostrar un enunciado (frase), se necesita un conjunto de axiomas (como los axiomas de la teoría de grupos) y una noción de prueba formal a partir de estos axiomas. No voy a eleborar aquí, pero la conexión importante entre los enunciados verdaderos y los enunciados demostrables es el teorema de completitud:

Una sentencia es demostrable a partir de un conjunto de axiomas si toda estructura que satisface los axiomas también satisface la sentencia.

Este teorema te dice cuál es el problema de los teoremas de incompletitud: Consideramos afirmaciones verdaderas sobre los números naturales, pero una afirmación es demostrable a partir de un conjunto de axiomas sólo si es válida para todas las estructuras que satisfacen los axiomas. Y habrá estructuras que no sean isomorfas a los números naturales.

Answer 3

Observe que no está parafraseando el 2º Teorema de Incompletitud (que dice que un sistema axiomático que satisface ciertas condiciones técnicas no puede demostrar su propia consistencia a menos que sea inconsistente), sino el En primer lugar Teorema de Incompletitud.

Recuerda que un "modelo" de un sistema axiomático significa una interpretación particular de las nociones primitivas que hace que los axiomas sean verdaderos en esa interpretación.

"Verdadero" y "Falso" en este contexto se refieren a modelos . "Verdadero" debería ser realmente "verdadero en el modelo $M$ "; es decir, hay una interpretación particular de los axiomas que hace que el enunciado sea verdadero. Cuando hablamos de que los enunciados aritméticos son "verdaderos", nos referimos a "verdaderos en la modelo estándar "(el "modelo estándar" es una interpretación particular de las nociones primitivas de la aritmética). Véase, por ejemplo La página de Wikipedia sobre no estándar modelos de airthmetic .

"Probable" significa que existe una derivación formal del enunciado a partir de los axiomas. Si un enunciado es demostrable, entonces es verdadero en todos los modelos; a la inversa, el Teorema de Completitud de Gödel muestra que si un enunciado (de primer orden) es verdadero en todos los modelos, entonces es demostrable.

En particular, un enunciado es "formalmente indecidible" en un sistema axiomático si hay algunos modelos en los que es verdadero y otros en los que es falso. Cuando se tiene un "modelo preferido" (como ocurre con la aritmética), a menudo se habla simplemente de "verdadero" en lugar de "verdadero en un modelo particular".

Answer 4

Los dinosaurios fueron asesinados por un cerebro gigantesco, en lugar de un asteroide. (cf. Futurama, El porqué de Fry )

Aunque parezca falso, no se puede probar esta afirmación es verdadera o falsa. Sólo puedes encontrar pruebas que apoyen su refutación.

En la vida real tendemos a etiquetar las cosas como verdaderas o falsas independientemente de su comprobabilidad. Las matemáticas, sin embargo, nos ofrecen la distinción entre la existencia de una prueba y el valor de verdad de una afirmación.

Es decir, nosotros definir qué es una estructura en algún lenguaje, y qué tipo de afirmaciones son verdadero en esa estructura.

Podemos tomar un conjunto de oraciones de las que no podemos derivar una contradicción (estos conjuntos se llaman teorías por ejemplo, axiomas de un grupo), y podemos considerar estructuras del lenguaje apropiado en las que este conjunto de oraciones es verdadero (decimos que se trata de un modelo de la teoría).

El teorema de incompletitud dice que dada tal teoría que es "suficientemente bonita" y que puede utilizarse para desarrollar parte de la teoría verdadera en los números naturales, entonces en un modelo de esta teoría habrá afirmaciones que son verdaderas pero que no pueden demostrarse.

Por supuesto, podemos demostrar tal afirmación utilizando diferentes teorías, o podemos proporcionar contraejemplos con teorías diferentes. Quizá podamos demostrar más (o menos) si incluso sustituimos la forma de deducir las cosas, o las sentencias que permitimos (podemos permitir la lógica de segundo orden, o la cuantificación infinita, por ejemplo).

Sin embargo, dentro de los confines de la lógica de primer orden, y de la teoría dada, hay oraciones que podemos probar son indemostrables a partir de esta teoría dada, pero pueden ser ciertas en algún modelo. Además, en cada modelo hay alguna afirmación que es verdadera (en ese modelo específico) pero que no tiene ninguna prueba.

Answer 5

Supongamos que hago algún tipo de afirmación como "Para todos los números naturales $n$ , $P(n)$ se mantiene".

Para que mi afirmación sea cierta, debe ser que no haya ningún contraejemplo. Es decir, no hay ningún número entero $n_0$ tal que $P(n_0)$ falla. Incluso si este es el caso, puede que no sea capaz de probar que es así. Por lo tanto, mi afirmación podría ser cierta, pero no demostrable.