¿Se puede demostrar que no hay pruebas de cierto problema?

Answer 1

Es todo lo contrario, se espera que haya una prueba de cualquier enunciado computacionalmente significativo no trivial (como P! = NP) en un sistema axiomático suficientemente fuerte. La demostración es de la tesis de Turing en 1938, con respecto a las iteraciones ordinales del teorema de Godel.

Para demostrar que una declaración no es demostrable en un sistema de axiomas dado, generalmente demuestra que la declaración implica la consistencia de este sistema de axiomas. Esto es suficiente, pero no es necesario, hay muchas declaraciones mucho más débiles que la consistencia de una teoría que aún no se pueden probar. Para ver esto, considere los programas “TWEEDLEDUM” y “TWEEDLEDEE” de esta publicación de mathoverflow: ¿Cuáles son algunas pruebas del Teorema de Godel que son * esencialmente diferentes * de la prueba original? O “TWEEDLE_N”. Todos estos son más débiles que la consistencia, pero aún no demostrables. Seguramente hay resultados combinatorios equivalentes a estas declaraciones para PA, como el teorema de Paris Harrington o Goodstein es equivalente a la consistencia de PA.

Estos resultados locales de no demostrabilidad no se aplican a las matemáticas como un sistema, porque las matemáticas se pueden extender arbitrariamente en el extremo superior, nombrando ordinales computables más grandes. Este proceso no puede ser computable y, sin embargo, parece que lo estamos haciendo. Esta contradicción llevó a muchas personas a decir “el cerebro no debe ser computable”, un conjunto de personas que incluye a Kurt Godel y Roger Penrose.

Pero esta es una conclusión errónea. Hay una cosa indiscutible en el cerebro, al menos en el estricto sentido de Turing, hay un generador de números aleatorios de jitter térmico. Los números aleatorios no son computables en Turing, y deberían ser suficientes para desarrollar descripciones de ordinales computables más grandes con límite en Church Kleene. Nadie ha demostrado esto, ni siquiera está claro cómo decirlo, pero es algo que uno cree al conciliar el teorema de Godel con la capacidad obvia de los matemáticos para crear sistemas más fuertes que resuelvan más problemas.

Con P! = NP, habrá una prueba. Es una afirmación relativamente simple, y tenemos una fuerte intuición de que debería ser cierto, lo cual no es realmente probabilístico. La prueba probablemente será relativamente simple. Pero por el momento, las técnicas de pruebas de algoritmos son relativamente primitivas, porque los matemáticos han descubierto la ciencia de la computación durante 60 años.

Answer 2

Sí, se puede demostrar que no hay pruebas. En realidad es bastante común incluso en casos triviales. Si le dicen que p y q son verdaderas, hay un número infinito de cosas que son verdaderas (p y q, p o q, p or r, etc.) pero no puede probar ni r ni no-r.

Este no es un caso muy interesante, pero establece la noción. Más personas están interesadas en probar cosas que comienzan con los axiomas de la aritmética, ya que esos son axiomas que nos interesan. Los teoremas de incompletitud de Godel son pruebas de que existen afirmaciones que son verdaderas pero que no se pueden probar en sistemas aritméticos. Los ejemplos que se generan no son necesariamente teoremas que te interesan mucho, pero la existencia de ellos te dice cosas sobre la estructura de la aritmética.

También hay ejemplos prácticos de problemas no demostrables. Los matemáticos trabajaron durante miles de años para tratar de responder a la pregunta de si “si tiene una línea, existe exactamente otra línea paralela a ella que pasa a través de un punto externo particular” puede probarse a partir de los otros axiomas de la geometría. La respuesta es que no, puedes probar que no puedes probarlo de una forma u otra a partir de esos axiomas. De hecho, si asumes lo contrario, obtienes una geometría válida diferente, una que resulta tener aplicaciones muy importantes.

Uno de los ejemplos más famosos es el primero de los problemas de Hilbert. Querían demostrar, utilizando los axiomas de una determinada teoría de conjuntos ampliamente utilizada, que no existe un conjunto que sea mayor que el número de enteros y menor que el número de números reales. Paul Cohen demostró en 1963 que no se puede hacer. Puedes asumirlo como un axioma o asumir lo contrario. De cualquier manera, nunca tendrás una contradicción.

En cuanto a P = NP … es posible que no exista prueba, aunque lo dudo. Es decir, tengo razones para sospechar que hay una prueba, pero no hay razón para pensar que será fácil. Las pruebas sobre pruebas no dicen nada sobre la dificultad. Todo es cuestión de ingenio humano, un fenómeno decididamente finito que puede pasar siglos demostrando algo que inicialmente parece simple. Pregúntele a cada matemático entre Pierre Fermat y Andrew Wiles.

Answer 3

En general, si. Para una proposición “P es verdadera”, si podemos probar “! P es verdadera”, definitivamente no podemos probar también que “P es verdadera” ya que eso contradeciría una de las partes más fundamentales de la lógica.