No es cierto que un sistema matemático no pueda ser consistente y completo. Lo que es cierto, y puedo mostrarle la razón, es que un sistema de axiomas no puede ser estas cuatro cosas simultáneamente:
- Recursivo, lo que significa que se puede implementar en una computadora.
- Suficientemente poderoso para probar cosas básicas sobre los números naturales.
- Completo, lo que significa que puede probar X o refutar X, para cualquier declaración X que pueda escribirse en el lenguaje formal que estamos usando.
- Consistente, lo que significa que nunca prueba tanto X como la negación de X.
Para ver por qué esto es cierto, supongamos por un momento que fortalecemos la propiedad 2: el sistema no solo es lo suficientemente fuerte como para probar datos básicos sobre números naturales, sino que es lo suficientemente fuerte como para razonar sobre programas de computadora. Puede probar declaraciones como “este programa finalmente se detendrá” o “este programa nunca se detendrá”.
Debido a la propiedad 1, nuestro sistema puede implementarse como un programa de computadora. Debido a las propiedades 3 y 4, resuelve correctamente el problema de detención para cada programa (estoy suprimiendo un tecnicismo aquí, al que volveré más adelante).
- ¿Por qué son importantes los functores adjuntos?
- ¿Qué sucederá si se demuestra que el teorema de Pitágoras está equivocado o hipotéticamente no existe?
- ¿Cómo funciona la calculadora integrada en la búsqueda de Google?
- ¿Las matemáticas son reales?
- ¿Qué es 2.5 factorial?
Por lo tanto, dicho sistema implicaría la existencia de un programa de computadora que resuelva el problema de detención. Pero es bastante fácil demostrar que dicho programa no existe (consulte ¿Cómo describiría el problema de detención de Turing a un niño de 13 años que usa analogía o metáforas?). Por lo tanto, como el sistema axiomático tampoco puede existir.
Este es el corazón de la prueba. Lo que queda son dos tecnicismos:
- Demuestre que “probar hechos simples sobre números naturales” es equivalente a “razonar sobre programas de computadora”, por lo que nuestro fortalecimiento de la propiedad 2 no es problemático. Esto es cierto porque una computadora, con su memoria y código, puede describirse completamente como un gran número natural, y la operación de cómo computa puede describirse como una secuencia de operaciones aritméticas.
- Interpreté que “completo” y “consistente” implican que el sistema axiomático solo está demostrando afirmaciones verdaderas , es decir, cuando dice que un programa de computadora se detiene, en realidad lo hace, y cuando dice que no lo hace, no lo hace. Esto es realmente un requisito llamado “solidez” que es más fuerte que la consistencia. Para una comprensión filosófica básica, sin embargo, la diferencia no tiene sentido. La gente normalmente interpreta “consistente” como “sonido” de todos modos. Puede tomar la prueba por la que pasamos para significar simplemente que un sistema no puede ser recursivo, lo suficientemente potente, completo y sólido.
La prueba original de Gödel abordó el primer tecnicismo, excepto que no tenía la noción de un programa de computadora, por lo que razonó sobre los sistemas lógicos formales. Mostró que los sistemas de aritmética de axiomas pueden representar la idea misma de un sistema de aritmética de axiomas, y esto lo llevó a la misma contradicción que el problema de detención.
Pero en casi todos los sentidos, este es un arenque rojo histórico. El contexto natural para la prueba es el razonamiento sobre programas de computadora o funciones recursivas. Esto hace que la prueba sea casi completamente transparente.
Gödel en realidad no abordó por completo el segundo tecnicismo. El resultado que probó es, en consecuencia, algo más débil de lo que casi todos citan. Necesitaba que la propiedad 4 fuera “[math] \ omega [/ math] -consistency”, que está mucho más cerca de la “solidez” que la mera consistencia.
Cinco años después, el lógico estadounidense John Barkley Rosser encontró una forma muy inteligente de evitar este tecnicismo, y demostró que las cuatro propiedades son incompatibles incluso si requerimos mera consistencia. Su prueba de 1936 fue, por lo tanto, la primera prueba real de lo que la mayoría de la gente hoy llama “teorema de Gödel”.
(No quiero quitarle nada al fantástico avance de Gödel, solo para ser precisos sobre lo que realmente sucedió).
En cualquier caso, el corazón de la prueba es realmente simple: los programas de computadora son cosas tan poderosas que vencen su propia capacidad para determinar si tienen ciertas propiedades simples, como finalmente detenerse. Esto se sigue simplemente de la idea de que un programa llama a otro: si tuviéramos un Oracle detenido, podríamos hacer un programa un poco más grande que se detenga precisamente cuando el oráculo diga que no se detendrá. Ese es el corazón de la “diagonalización” del argumento.
Todo lo demás, en esta y otras pruebas, es “reducción”. Está demostrando que los programas de computadora pueden simularse por medios muy simples. Pueden ser simulados por máquinas de Turing, que simplemente manipulan números, y por lo tanto la teoría de números no puede ser mecanizada (Gödel, Tarski). Se pueden simular mediante las propiedades multiplicativas de los elementos en semigrupos (fácil) y grupos (muy complicado), y por lo tanto, el problema de la palabra en grupos no tiene solución (Novikov, Boone). El problema del mosaico, de si un conjunto de mosaicos puede enlosar todo el plano, tampoco se puede resolver (Chow).
Y así sucesivamente: en términos generales, cualquier sistema suficientemente complejo que pueda acomodar procesos potencialmente infinitamente largos no puede describirse algorítmicamente en su totalidad. Esto no es ni más ni menos filosóficamente profundo que la observación de que el problema de detención no tiene solución.