Algunas dudas sobre los Teoremas de Incompletitud

Un punto importante a tener en cuenta sobre el primer teorema de incompletitud es que, si bien cierta fórmula es "verdadera" pero no demostrable, es "verdadera" sobre la base de mi comprensión (interpretación prevista) del "sistema formal" en cuestión. Eso es lo que creo que uno quiere decir cuando se dice que uno puede ver que es verdad. Wikipedia proporciona una explicación:

La oración de Gödel está diseñada para referirse, indirectamente, a sí misma. La oración establece que, cuando se usa una secuencia particular de pasos para construir otra oración, esa oración construida no será demostrable en F. Sin embargo, la secuencia de pasos es tal que la oración construida resulta ser GF misma. De esta manera, la oración de Gödel GF establece indirectamente su propia indemostrabilidad dentro de F (Smith 2007, p. 135).

... El primer teorema de incompletitud muestra que la oración de Gödel GF de una teoría formal apropiada F es indemostrable en F. Porque, cuando se interpreta como un enunciado sobre aritmética, esta indemostrabilidad es exactamente lo que afirma (indirectamente) la oración, la oración de Gödel es , de hecho, cierto (Smoryński 1977 p. 825; ver también Franzén 2005 pp. 28–33). Por esta razón, a menudo se dice que la oración GF es "verdadera pero indemostrable". (Raatikainen 2015).

Hasta ahora estoy bien. Luego viene la consistencia.

El sistema no puede demostrar su propia consistencia. Demostrar consistencia significa "No es posible derivar una contradicción, es decir, 1=0". Si se prueba esta afirmación, se establece la consistencia. Segundo Teorema: La consistencia no se puede probar dentro del sistema. Entonces, puedo agregar un axioma de que mi sistema S es consistente y llegar a un nuevo sistema S' donde S' = S + (S es consistente). Mi pregunta es:

  1. ¡Esto todavía no hace que S sea consistente! ¿O sí? Si entiendo las reglas del sistema S, ¿puedo ver nuevamente pero no probar la consistencia de S, o la consistencia de S sigue siendo una pregunta abierta?
  2. ¿Cómo se relaciona la consistencia de un sistema S con la Máquina Universal de Turing para la lógica de primer orden? Quiero decir, ¿cuál es el análogo técnico de la consistencia en las máquinas de Turing? ¿ Mi computadora realmente no es demostrablemente consistente ? ¿Y eso significa que algún día puede dar una contradicción reconocible?
1. La consistencia sigue siendo una pregunta abierta. Se puede probar dentro de la metateoría (ver prueba de consistencia de Gentzen).
2. El hecho de que la teoría en cuestión no pueda probar su propia consistencia no significa que sea inconsistente. Nadie ha encontrado inconsistencias en la aritmética hasta ahora...
También se pueden señalar fuertes intuiciones de que los axiomas básicos y las definiciones de funciones en la aritmética de Peano no serán inconsistentes porque se pueden entender semánticamente como que describen hechos verdaderos sobre contar, sumar y multiplicar elementos finitos... por ejemplo, un argumento para A B=B Siempre se mantiene que puedes pensar en "A*B" como una matriz rectangular con A filas y B puntos por fila (por lo que cada columna tiene A puntos, cada fila tiene B puntos), y luego, si simplemente rotas en 90 grados, tiene una matriz rectangular con filas B y puntos A por fila (cada columna tiene puntos B, cada fila tiene puntos A).
@MauroALLEGRANZA ¿Podemos entonces deducir que es imposible probar la consistencia de la mente (en el ámbito matemático)? Después de todo, la metateoría es mente (si no es inmediata, entonces después de muchas, muchas iteraciones de S,S',S'',..., S(aleph-null)... y así sucesivamente, quizás en el límite .
Considere 'ex falso quodlibet' Si su sistema es inconsistente, por supuesto, puede demostrar que es consistente. Simplemente deduce la consistencia de la contradicción que prueba que es inconsistente. Entonces, si agrega su axioma de consistencia, puede probar que no lo viola, incluso si lo viola. El problema es que tanto los sistemas consistentes como los inconsistentes pueden deducir que no violarían su axioma. Así que no significa nada.
Si el sistema es inconsistente, entonces S ya es un teorema, por lo que agregarlo como un axioma no cambiará nada. Si el sistema es consistente, entonces agregar S hará que el sistema sea inconsistente ya que ahora tendría una prueba de consistencia (de una línea), contradiciendo el teorema de Gödel.
Tradicionalmente, una teoría es lo que una máquina de Turing enumeraría recursivamente. Detenerse en la enumeración cuando coincide con el enunciado en cuestión es entonces el equivalente a una prueba. Los sistemas inconsistentes pueden probar cualquier cosa. Entonces, la consistencia significaría que hay declaraciones en las que la máquina no se detendrá. Desafortunadamente, no podemos saber si la máquina se detendrá hasta que hayamos esperado infinitamente para hacerlo. Por lo tanto, no podemos saber si el sistema es consistente, si simplemente elegimos accidentalmente una declaración verdadera pero no demostrable, o si simplemente no hemos esperado lo suficiente.
@Nick Basado en esta respuesta , aparentemente no contradice el teorema de Godel para crear un nuevo sistema axiomático S2 que se forma tomando los axiomas de S y agregando un axioma que afirma la consistencia de S; S2 todavía no puede probar su propia consistencia, por lo que se aplica el teorema de Gödel. Por otro lado, la respuesta dice que si tienes una proposición 𝜑 que afirma algo como "el sistema axiomático formado al tomar los axiomas de S y sumar 𝜑 como axioma es consistente", entonces sumar 𝜑 a los axiomas S sería inconsistente.
@Hypnosifl Gracias. Sí, estoy corregido. Afirmar la consistencia de "T" no dice nada sobre la consistencia de "T"+"CON(T)". Un punto bastante sutil, obviamente demasiado sutil para mí.
"¿Podemos entonces deducir que es imposible probar la consistencia de la mente..." NO; La Th de Godel se aplica al sistema formal con algunas características específicas. La mente humana no es un sistema formal. Además, si tratamos de considerar el lenguaje humano como un "sistema", es claramente inconsistente.
@MauroALLEGRANZA Gracias por comentar. Sin embargo, ¿no podemos considerar el razonamiento humano en su totalidad (es decir, no sólo lo que hacemos ahora, sino lo que podemos hacer en principio) como un sistema formal "razonable" y, por lo tanto, aplicar el Th de Gödel?
@Ajax: un sistema significa: lenguaje fijo, reglas fijas para formar expresiones, reglas fijas para derivar nuevas fórmulas a partir de axiomas y un conjunto recursivo de axiomas. Si es así, ¿dónde están los axiomas? Recuerde que desde un punto de vista intuitivo, el principio de comprensión ingenua puede asumirse como un buen ejemplo del axioma del "sentido común". Utilizándolo, derivamos la conocida Paradoja. Conclusión: la mente humana es inconsistente .
En lo que se refiere a la consistencia del sistema aritmético, permítanme recomendar el artículo TJ Stępień, Ł. T. Stępień, „Sobre la consistencia del sistema aritmético”, Journal of Mathematics and System Science , vol. 7, 43 (2017), arXiv:1803.11072. Se publicó una prueba de consistencia del Sistema Aritmético. Esta prueba se realizó dentro de este Sistema (el resumen relacionado con este artículo: TJ Stepien y LT Stepien, "On the consistencia del sistema aritmético de Peano", The Bulletin of Symbolic Logic, vol. 16, No. 1, 132 ( 2010 ) ).

Respuestas (2)

Entonces, puedo agregar un axioma de que mi sistema S es consistente y llegar a un nuevo sistema S 'donde S' = S + (S es consistente)

Sí, eso está bien. Si me permite cambiar a variables que son más fáciles de distinguir entre sí, puede tener:

B = A + (A es consistente)

O incluso

C = A + (A no es consistente)

Ninguno (!) de esos implicará una contradicción (pero C no será consistente con omega , que es una forma más fuerte de consistencia que surge cuando intenta reconciliar la teoría y la metateoría entre sí). Ni B ni C pueden probar que B/C es en sí mismo consistente, aunque B obviamente prueba que A es consistente.

La explicación completa de C está fuera del alcance aquí, pero en resumen, afirma que existe una prueba de alguna contradicción, como 0 = 1, y se puede codificar con algún número de Gödel, pero resulta que este número en realidad no existen en el modelo estándar de aritmética (no es ninguno de 0, 1, 2, etc.). La aritmética de Peano no es lo suficientemente fuerte como para refutar la existencia de tales números no estándar, por lo que no surge ninguna contradicción dentro del sistema C. Sin embargo, es intuitivamente obvio que C es "incorrecto" en algún sentido, y de eso se trata la consistencia omega.

Pero hay una gran excepción: si A ya es inconsistente, entonces prueba todo , incluyendo su propia consistencia y su propia inconsistencia, y esa inconsistencia es heredada por B y C. Siempre que hablamos de cualquiera de los teoremas de incompletitud, siempre tomamos el la consistencia de la teoría como suposición básica, porque es muy poco lo que se puede decir de manera útil sobre una teoría inconsistente de la aritmética.

Por otro lado, no podemos salirnos con algo como esto:

D = A + (D es consistente)

Porque resulta que, suponiendo que pueda encontrar una manera de expresar la autorreferencia (con un uso inteligente de la numeración de Gödel), el sistema resultante entraría en conflicto con el segundo teorema de incompletitud y, por lo tanto, sería inconsistente.

Ahora, volviendo a tus preguntas:

¡Esto todavía no hace que S sea consistente! ¿O sí? Si entiendo las reglas del sistema S, ¿puedo ver nuevamente pero no probar la consistencia de S, o la consistencia de S sigue siendo una pregunta abierta?

Si cree que S' no prueba ninguna contradicción (o, de manera equivalente, que S' es consistente), entonces necesariamente cree que S es consistente y, por lo tanto, no se requiere una demostración. Si S fuera inconsistente, entonces S' también sería inconsistente, y cualquier "prueba" que proporcionara sería inútil. Por lo tanto, no puede usar S' para probar que S es consistente, porque ya cree que S es consistente, o ya duda de que S' sea consistente, y entonces S' no logra nada para usted.

¿Cómo se relaciona la consistencia de un sistema S con la Máquina Universal de Turing para la lógica de primer orden? Quiero decir, ¿cuál es el análogo técnico de la consistencia en las máquinas de Turing? ¿Mi computadora realmente no es demostrablemente consistente? ¿Y eso significa que algún día puede dar una contradicción reconocible?

El hecho de que no puedas probarla consistencia no significa que un sistema sea necesariamente inconsistente. Los matemáticos han considerado cuidadosamente la consistencia de la aritmética de Peano y la teoría de conjuntos de Zermelo-Fraenkel durante mucho tiempo, y nadie ha demostrado nunca que ninguno de los sistemas sea inconsistente. Podríamos imaginar que algún día podría construirse alguna contradicción increíblemente sutil y elaborada, pero no sería una simple reafirmación de, por ejemplo, la paradoja de Russell, porque todos los problemas "simples" como la paradoja de Russell ya han sido explorados y "arreglados". Si alguna vez encontráramos tal contradicción, probablemente podría estar limitada por una ligera modificación de los axiomas para descartar cualquier línea de argumentación que conduzca a una contradicción, por lo que probablemente podríamos recuperar la mayoría de los teoremas matemáticos existentes con poca interrupción.

Francamente, estaría mucho más preocupado por la posibilidad de que el software de su computadora tenga fallas o esté diseñado incorrectamente, en lugar de que toda la correspondencia Curry-Howard se derrumbe en algún momento en el futuro cercano. Los errores de software ocurren todo el tiempo; Los errores matemáticos son (en los últimos años) mucho más raros.

Pero en cualquier caso, bajo la correspondencia CH antes mencionada, los combinadores de punto fijo ya pueden usarse para recuperar la paradoja de Curry (o más bien, podrían hacerlo, si la correspondencia CH no hubiera excluido explícitamente el cálculo lambda sin tipo en el que surgen los combinadores de puntos, precisamente para solucionar este problema). Efectivamente, los lenguajes de programación modernos (Turing-completo) ya han "optado" por la consistencia por completo (y esto se vuelve aún más obvio cuando considera la posibilidad de conversión de tipo arbitraria en la mayoría de los lenguajes de tipado estático).

Gracias por su respuesta. No estoy muy familiarizado con la correspondencia CH. ¿Puedes aclarar cuál es el punto de CH? ¿Se mantiene en general? ¿Es mi intuición que debido a que el algoritmo A "decide" el teorema T, debe ser el caso que A codifique la prueba de T de alguna manera... -correcto?
@Ajax: No, la correspondencia es mucho más sutil y general que eso. Tiene más que ver con la teoría de tipos que con la teoría de la computación. Los algoritmos que "deciden" las cosas, o de hecho los algoritmos en general, no son realmente el punto de la correspondencia CH.
Excelente respuesta Es posible que desee tener en cuenta que la consistencia ω se puede debilitar a la solidez Σ1. C no es un sonido Σ1. Por eso, si creemos que A tiene sentido, debemos creer que B tiene sentido y que C no tiene sentido.

Tome un sistema inconsistente S y cree otro sistema S' agregando el axioma "S' es consistente". Ahora tienes una prueba muy simple de que S' es consistente. Pero aún tiene alguna afirmación X con prueba s tanto para X como para no X, por lo que S' es tan inconsistente como S, ¡además tiene una contradicción directa con el axioma agregado!

En su lugar, agregue un axioma "S' es completo". Pero al igual que en S, puede expresar una declaración X que dice en términos sencillos "no hay prueba para la declaración X". No necesitamos probar o refutar X, solo el hecho de que podamos expresarlo hace que la ley de Gödel se cumpla. La existencia de X muestra que S' es incompleto o inconsistente. Por supuesto, el axioma agregado muestra que S' no es incompleto, por lo tanto, es inconsistente.

¿Y si le añadimos “S' está incompleta”? Todo sistema inconsistente es completo, por lo que nuevamente tenemos una demostración inmediata de que S' es consistente. Pero una prueba de que S' es consistente no impide que sea inconsistente, por lo que no se gana nada.

Depende exactamente de lo que quieras decir con "completo" aquí. Por ejemplo, T:=ZFC+"ZFC es inconsistente" es una teoría consistente asumiendo que ZFC en sí mismo es , pero por supuesto T prueba "Para cada oración p , T prueba p o T refuta p " (ya que de hecho T prueba su propia inconsistencia ). Sin embargo , ZFC + "ZFC es consistente y completo" es inconsistente.
Algunas dudas sobre los Teoremas de Incompletitud
RespuestasAquíPolítica de privacidad1y, 0v