El primer teorema de incompletitud de Gödel establece
Cualquier teoría efectivamente generada capaz de expresar aritmética elemental no puede ser consistente y completa. En particular, para cualquier teoría formal consistente y efectivamente generada que demuestre ciertas verdades aritméticas básicas, hay una afirmación aritmética que es verdadera, pero no demostrable en la teoría (Kleene 1967, p. 250).
¿Cuáles son las implicaciones filosóficas de este teorema? En particular, ¿existen posiblemente análogos más generales de este teorema, necesariamente "verdades indemostrables" dentro de otros tipos de sistemas formales?
Cualquier sistema formal efectivamente axiomatizado que extienda una teoría muy básica de la aritmética formal llamada Aritmética de Robinson (Q) contendrá una oración indecidible. En general, puede enunciar la versión sintáctica del primer teorema de incompletitud de la siguiente manera:
(G1T) Para cualquier teoría T efectivamente axiomatizada que extienda Q, existe una oración T G tal que: (i) Si T es consistente, entonces T no puede probar G (ii) Si T es omega-consistente, entonces T no puede probar ¬G.
Este es el enunciado más general del teorema que se puede obtener. Tenga en cuenta que Kleene, en su cita, está hablando de la versión semántica del teorema. Sin embargo, lo que Godel probó originalmente no involucraba nociones semánticas como la verdad, la verdad aritmética, etc. Si puede o no ver/reconocer/reconocer G como verdadero depende de la comprensión semántica/intencional de G: es un error común que Gödel quería probar Las limitaciones de la verdad aritmética.. El trasfondo en el que estaba trabajando era el formalismo hilbertiano, por lo que su principal preocupación era demostrar las limitaciones puramente sintácticas de los sistemas formales. Entonces, en total generalidad sintáctica, (G1T) dice (informalmente) que ninguna manipulación apropiada de símbolos en cualquier sistema formal lo suficientemente complicado como para contener algo de aritmética terminará con G.
Entonces puede ver que (G1T) se aplica a una amplia gama de sistemas formales. Si elige ver las G obtenidas como ' verdades indemostrables ' depende de su semántica, de si su T tiene una interpretación prevista, etc. Pero en la mayoría de los casos habituales, ese tipo de conclusión se considera justificada. Pero solo surge debido a la falla sintáctica subveniente que (G1T) asegura.
Ahora bien, en cuanto a las implicaciones filosóficas, la literatura es inmensa. Mencionaré algunas cuestiones pertinentes:
Finalmente, me gustaría decir que innumerables autores/pensadores/hacks de mentalidad filosófica se han apropiado del Teorema de Gödel para tratar de señalar puntos sobre autorreferencia/bucles/Dios/metafísica/conciencia ambiental y Dios sabe qué más. Las tres implicaciones que planteé pueden parecer secas y académicas, pero también son precisas, bien estudiadas y libres de hipérboles. No hay duda de que los teoremas de Gödel impulsaron nuestra comprensión de los sistemas formales y, con ella, nuestra comprensión de las facultades y debilidades filosóficas del razonamiento formal.
Me gustaría hacer una pausa aquí para enunciar y demostrar con precisión el teorema de Gödel correctamente. La presentación original es anterior a la invención de la computadora y es complicada. Pero vivimos 80 años después, donde las computadoras son familiares.
Primero, en el teorema de Godel, siempre estás hablando de un sistema axiomático S. Este es un sistema lógico en el que puedes probar teoremas mediante un programa de computadora, debes pensar en la Aritmética de Peano, o ZFC, o cualquier otra teoría de primer orden con un esquema de axioma computable (axiomas que pueden enumerarse mediante un programa informático fijo).
Se supone que tal sistema de axiomas puede describir una computadora en cualquier tiempo finito. El contenido de la memoria de una computadora es una cadena de bits, un entero grande M, y las manipulaciones en la memoria al ejecutar un paso es una función muy simple, que hace algo desde el conjunto de instrucciones y cambia la memoria. Si hace esto un número finito de veces, obtiene un nuevo estado de memoria M'. La suposición básica en S es esta:
S puede seguir un programa de computadora: dada una computadora universal fija con memoria inicial M, probará que la memoria en el tiempo t es M' para cualquier tiempo finito t.
En Peano Arithmetic esto es trivial, porque puedes codificar la memoria de una computadora de maneras muy simples, y los axiomas sin inducción, solo los axiomas para calcular cosas, te dicen cuál es el resultado de un cálculo finito. Así que esto es cierto en la Aritmética de Peano sin inducción y sin cuantificadores. Es muy sencillo pedirle a un sistema de axiomas que pueda seguir un cálculo y demostrar que el resultado en un tiempo finito es correcto.
A continuación, asumimos que S puede afirmar cosas como "El programa P no se detiene". Esto requiere un cuantificador
Supongo que S es consistente. El enunciado "S es consistente" significa que si S demuestra que "P no se detiene", entonces P de hecho no se detiene. Dado que si P se detiene, S lo seguiría hasta que se detenga, y luego probaría esto también. Tenga en cuenta que S puede probar que "P se detiene" sin que P realmente se detenga, simplemente no puede probar que "P no se detiene" si esto es una mentira.
Teorema: Considere tal sistema de axiomas S. Hay un programa P que no se detiene para el cual S no puede probar que "P no se detiene":
Prueba: Escriba el programa de computadora SPITE para hacer lo siguiente:
Si lo piensas durante medio segundo, en el momento en que S prueba que "EL DESPRE no se detiene", el DESPRE se detiene (por construcción) y convierte a S en un mentiroso. La autorreferencia está en la primera línea --- imprimir su propio código en una variable, y que esto sea posible es un ejercicio dado a los programadores de pregrado.
Esa es la construcción completa, y la prueba completa.
Godel 2: S no puede probarse consistente
La prueba es la siguiente: si S es consistente, SPITE no puede detenerse, porque vemos que esto implica que S es inconsistente. Entonces, si S puede formalizar este argumento y puede demostrar que es consistente, prueba que SPITE no se detiene (lo cual es imposible).
Esa es la prueba completa. Se requiere familiaridad con la lógica para ver que para S apropiado, la deducción informal "S es consistente implica que SPITE no se detiene" se puede formalizar en S, pero si no fuera posible formalizar deducciones lógicas intuitivas como esta, no lo haríamos. t estar usando S en primer lugar.
Rosser: El problema con Godel1 y Godel2 (que son esencialmente el mismo teorema excepto por una elección trivial de ejemplo canónico), es que S aún podría ser completo pero incorrecto . En otras palabras, la prueba de Gödel no mostró que haya un programa P cuya detención no esté prevista en absoluto. Tal vez S decida que todos los programas se detienen o no se detienen, pero no lo hace bien --- le dice que algunos programas que no se detienen se detienen. Si le dijera que un programa que se detiene no se detuvo, esto sería una contradicción en S (después de suficiente tiempo), pero puede decirle que un programa que no se detiene se detiene sin contradicción (esto es obvio, pero sutil).
Así que escribe ROSSER:
Ahora S no puede probar ni "ROSSER imprime" ni la negación "ROSSER no imprime". De modo que si un segundo programa sigue a Rosser y se detiene cuando se imprime ROSSER, no se prueba que este programa se detenga o no se detenga.
La principal implicación filosófica es la más importante en la historia de la filosofía (esto no es una exageración):
Existe una noción universal de computación, que es independiente del sistema de axiomas.
Este es el resultado principal del trabajo de Gödel, aunque no se entendió del todo hasta la versión de Turing unos años más tarde. Pero Gödel estaba tanteando hacia esto, ya que comprendió que esto era cierto muy rápidamente después de probar el teorema, y reconoció que Turing había proporcionado la explicación y abandonó su propio enfoque de cálculo en favor del de Turing. La razón por la que puedo salirme con la mía con una prueba como la anterior es porque todos estamos familiarizados con la noción de "una computadora" y "un programa de computadora", y todos sabemos que cualquier algoritmo preciso se puede programar en una computadora, y que una computadora es tan buena como otra.
Implicaciones filosóficas inmediatas:
Existe una noción acordada de lo que significa tener un conjunto de reglas definidas con precisión.
De hecho, puede construir una máquina que pueda simular cualquier otro conjunto de reglas definidas con precisión.
Cualquiera de estas dos máquinas es equivalente --- A puede simular B y B puede simular A.
Si existe la física (si existe un conjunto preciso de reglas, incluso reglas probabilísticas, para modelar la naturaleza), la máquina universal (equipada con un generador de números aleatorios) puede simular cualquier cosa en la naturaleza.
De esto se sigue que:
El comportamiento completo del ser humano puede ser simulado por una computadora universal.
Con el supuesto positivista lógico plausible, esto significa que
Una computadora es una máquina capaz de pensar.
Esta idea se debe a Turing. Von Neumann tiene la siguiente idea:
Una computadora es una máquina que es capaz de modelar el comportamiento de los sistemas biológicos. El teorema de Godel es análogo a la autorreplicación.
Estas son, de lejos, las ideas filosóficas más importantes de todos los tiempos. El precursor de esto son los intentos de Liebnitz de hacer una máquina filosófica que pudiera razonar mecánicamente. Leibnitz entendió algunas de las implicaciones de una computadora.
El teorema de Gödel mostró que, si toma la posición filosófica de que la afirmación "el programa P no se detiene" tiene un significado absoluto, entonces no existe un sistema axiomático fijo capaz de probar todas estas verdades significativas. Esto es bastante obvio: el programa que se deduce de los axiomas no puede probar demasiado sobre sí mismo sin contradicción.
Pero lo que es más importante, le muestra cómo producir sistemas más fuertes: al agregar el axioma "S es consistente", obtiene un nuevo sistema que lo hace más fuerte. Esto significa que cualquier sistema de axiomas tiene uno más fuerte, la reflexión de Godel.
S + "S es consistente"
es estrictamente más fuerte que S.
Puede iterar este procedimiento iterando la reflexión de Godel. No hay barrera en el infinito --- se puede considerar que el sistema que es la reflexión de Godel en el infinito es la unión de todos los teoremas probados en la etapa n (hay un programa específico que imprimirá las deducciones --- no necesita la teoría de conjuntos para hacer que la iteración sea precisa, al menos no para ordinales infinitos lo suficientemente pequeños). El proceso de iteración de la reflexión de Gödel reproduce los ordinales de Cantor.
Esto responde a la pregunta de la filosofía matemática.
¿Por qué son necesarios los ordinales?
Justifica completamente la teoría de conjuntos de Cantor. Se requiere la teoría de conjuntos de Cantor para dar a Gödel reflexiones sobre teorías anteriores a omega. Sin embargo, no justifica toda la metafísica, solo los ordinales más allá de los números enteros.
A medida que avanza en la lista de ordinales, los ordinales son programas de computadora cada vez más complicados (cada ordinal es un "proceso" en palabras de Paul Cohen). Tradicionalmente, puede definir el límite de todos los ordinales que se pueden representar en una computadora dentro de una teoría de conjuntos, y esto se llama el ordinal de Chuch-Kleene. Solo puede acercarse al ordinal de Church-Kleene en complejidad.
Después de Godel, Gentzen probó la consistencia de Peano Arithmetic dentro de un sistema axiomático muy limitado (PRA--- un fragmento débil de PA) con la suposición adicional
El ordinal epsilon-nada está bien fundado
A partir de este punto, quedó claro que las pruebas de consistencia de teorías complicadas se pueden dar a partir de teorías simples con la única suposición compleja de la fundamentación de cierto ordinal computable contable. Para PA, el ordinal ni siquiera era tan complicado, por lo que hay preguntas (como el problema de Paris-Harrington, o el problema de la hidra, o el teorema de Goodstein) que son equivalentes a la bien fundamentada de épsilon-cero, y así no pueden ser probados dentro de PA, pero que son equivalentes a la consistencia de PA, por lo que son demostrables en cualquier teoría que pueda probar la consistencia de PA.
El tema de la teoría de la prueba ordinal intenta hacer coincidir un ordinal, tan explícitamente descriptible como sea posible, con cada teoría matemática. Este programa ha tenido éxito con ciertas teorías de conjuntos, y no hay barrera para probar la consistencia de cualquier teoría, por infinita que sea. Así que otra implicación es
Es posible completar el programa de Hilbert y probar la consistencia de sistemas matemáticos incontablemente infinitos, solo usando ordinales computables contables que pueden representarse en una computadora.
Este programa está activo hoy, pero aún no ha demostrado la consistencia de ZF. En parte esto se debe a que muchas personas continúan diciendo que esto no se puede hacer, debido al teorema de Gödel.
La suposición principal de estas ideas es que el proceso de producción de ordinales que se acercan al ordinal de Church Kleene puede entenderse de alguna manera, aunque no es formalizable como un programa de computadora. Este proceso es una ganancia en complejidad análoga a la evolución biológica, y no se comprende hasta dónde podemos llegar dentro de nuestras limitaciones humanas.
Hay muchas implicaciones falsas del teorema de Gödel.
Somos más que computadoras
Esta interpretación proviene del hecho de que podemos entender que un programa P no se detiene (a saber, A PESAR de un sistema formal dado) aunque el sistema formal no lo haga. Para ver que esta es una conclusión falsa, solo hay que mirar lo que hace SPITE: simula el sistema, busca la predicción, ¡y lo despeina! No hay ninguna razón por la que no puedas hacerle eso a una persona:
Si puede simular a una persona, puede predecir su elección y a pesar de su decisión, de modo que puede colocar un millón de dólares en la casilla A solo si la persona elige la casilla B.
Este es el análogo exacto del teorema de Gödel en el ámbito humano, y es un famoso problema filosófico. También hay declaraciones
John Searle no puede creer consistentemente esta declaración
que son exactamente análogas, y que John Searle no puede creer, aunque es cierto. Aunque para convertirlo en una declaración lógica de primer orden sobre aritmética, debe proporcionar un modelo computacional de las creencias de Searle, lo que podría no ser posible debido a la aleatoriedad. Pero la idea es la misma: las cosas que el sistema de axiomas no puede saber, pero nosotros podemos saber, son cosas sobre el sistema mismo.
Hay otras construcciones debidas a Chaitin, que reformulan el teorema de incompletitud de la siguiente manera
Ningún programa puede probar que cualquier cadena tiene una complejidad de Kolmogorov mayor que la longitud del programa más una constante fija
Pero en una vista computacional de las personas, esto solo significa que ningún ser humano puede probar que una cadena tiene una complejidad de Kolmogorov mayor que la complejidad de un programa que simula a este ser humano. Dado que tenemos tantas dificultades incluso con una pequeña complejidad de Kolmogorov, esta es una predicción segura.
Entonces, no hay consecuencias del teorema de Gödel que impliquen que la teoría computacional de la mente sea falsa. hay otras ideas
El teorema de Gödel dice que la semántica no es formalizable
Esto tampoco es exactamente cierto: el teorema de Godel dice que la semántica de detener los programas de computadora solo se puede axiomatizar aproximadamente mediante el fortalecimiento de los sistemas, y el proceso de fortalecimiento no es algorítmico en el extremo superior. Pero la naturaleza precisa de la no algoritmia podría ser tan simple como nombrar ordinales contables computables cada vez más grandes que se acerquen al ordinal de Church Kleene, y esto podría ser evolutivamente posible de una manera razonable.
El teorema de Gode mata el programa de Hilbert
en la medida en que el programa de Hilbert desarrolló el análisis ordinal en respuesta al teorema de Gödel, esto no es cierto. Hace imposible una implementación ingenua del programa de Hilbert, pero la visión del análisis ordinal no es nada ingenua, y es precisamente el tipo de fundamentos que uno puede esperar para las matemáticas que son infinitamente ricas e infinitamente complejas.
Creo que también hay algunas consecuencias para la filosofía de las matemáticas, en particular para la visión formalista radical que considera las matemáticas como un mero juego formal sin ningún significado real. Este punto de vista tiene un problema con el resultado de Gödel: el teorema de hecho muestra que podemos hacer inferencias matemáticas fuera de cualquier entorno formal fijo (y lo suficientemente fuerte), por lo que si las matemáticas son solo "jugar con reglas formales", no está claro cómo identificar estas reglas de una manera razonable, ya que cualquier posible conjunto de reglas que pueda proporcionar resulta irrazonablemente débil según el resultado de Gödel.
Ninguna medición desde el interior del sistema observado puede ser informacionalmente completa.
usuario21820