Teorema de la incompletitud

Teorema de la incompletitud

Teorías indecid…

Dar un enunciado matemáticamente preciso del Teorema de Incompletitud de Godel sólo ocultaría su importante contenido intuitivo a casi cualquier persona que no sea especialista en lógica matemática. Así que, en su lugar, lo reformularé y simplificaré en el lenguaje de los ordenadores.
Imaginemos que tenemos acceso a un ordenador muy potente llamado Oracle. Al igual que los ordenadores con los que estamos familiarizados, Oracle pide que el usuario “introduzca” instrucciones que sigan unas reglas precisas y proporciona la “salida” o respuesta de una forma que también sigue estas reglas. La misma entrada producirá siempre la misma salida. La entrada y la salida se escriben como enteros (o números enteros) y Oracle sólo realiza las operaciones habituales de suma, resta, multiplicación y división (cuando es posible). A diferencia de los ordenadores normales, no hay que preocuparse por la eficiencia o el tiempo. Oracle llevará a cabo las instrucciones correctamente dadas sin importar el tiempo que le lleve y sólo se detendrá cuando se hayan ejecutado, incluso si tarda más de un millón de años.

Ver más

En matemáticas, el programa de Hilbert, formulado por el matemático alemán David Hilbert a principios del siglo XX, fue una propuesta de solución a la crisis fundacional de las matemáticas, cuando se descubrió que los primeros intentos de aclarar los fundamentos de las matemáticas adolecían de paradojas e incoherencias. Como solución, Hilbert propuso basar todas las teorías existentes en un conjunto finito y completo de axiomas, y proporcionar una prueba de que estos axiomas eran consistentes. Hilbert propuso que la consistencia de los sistemas más complicados, como el análisis real, pudiera demostrarse en términos de sistemas más simples. En última instancia, la consistencia de todas las matemáticas podría reducirse a la aritmética básica.
Muchas de las líneas actuales de investigación en lógica matemática, como la teoría de la prueba y la matemática inversa, pueden verse como continuaciones naturales del programa original de Hilbert. Gran parte de él puede rescatarse cambiando ligeramente sus objetivos (Zach 2005), y con las siguientes modificaciones se logró completar parte de él:

Prueba del teorema de incompletitud de gödel

4En la lógica matemática, se dice que una teoría es un conjunto de oraciones, en un lenguaje fijo (véase, por ejemplo, [Chiswell & Hodges 2007]; en [Kaye 2007], por ejemplo, la palabra “teoría” no aparece en absoluto en este sentido, y en su lugar se utiliza “un conjunto de oraciones”). A veces se requiere que una teoría sea cerrada bajo deducción (lógica), es decir, un conjunto de oraciones T se llama teoría si para cualquier oración φ que satisfaga T ⊢ φ tenemos φ ∈ T (véase, por ejemplo, [Enderton 2001]). Aquí, por una teoría entendemos cualquier conjunto de oraciones (no necesariamente cerradas bajo deducción). La completitud sintáctica de una teoría se suele considerar como completitud de negación: una teoría T es completa cuando para cualquier sentencia φ, o bien T ⊢ φ o bien T ⊢ ¬φ. Veamos la completitud con respecto a otras conectivas:
6Notamos que la mitad de la ¬ – completitud es la consistencia: una teoría se llama consistente cuando para toda sentencia φ, si T ⊢ ¬φ entonces T ⊬ φ. Normalmente, la otra mitad se llama completitud, es decir, cuando si T ⊬ φ entonces T ⊢ ¬φ para cada sentencia φ.

Heinrich franz friedrich t…

El primer teorema de incompletitud afirma que ningún sistema consistente de axiomas cuyos teoremas puedan enumerarse mediante un procedimiento eficaz (es decir, un algoritmo) es capaz de demostrar todas las verdades sobre la aritmética de los números naturales. Para cualquier sistema formal consistente, siempre habrá afirmaciones sobre los números naturales que sean verdaderas, pero que no se puedan demostrar dentro del sistema. El segundo teorema de incompletitud, una extensión del primero, muestra que el sistema no puede demostrar su propia consistencia.
Los teoremas de incompletitud se aplican a los sistemas formales que tienen la complejidad suficiente para expresar la aritmética básica de los números naturales y que son consistentes, y efectivamente axiomatizados, conceptos que se detallan a continuación. En particular, en el contexto de la lógica de primer orden, los sistemas formales también se denominan teorías formales. En general, un sistema formal es un aparato deductivo que consiste en un conjunto particular de axiomas junto con reglas de manipulación simbólica (o reglas de inferencia) que permiten la derivación de nuevos teoremas a partir de los axiomas. Un ejemplo de este sistema es la aritmética de Peano de primer orden, un sistema en el que todas las variables denotan números naturales. En otros sistemas, como la teoría de conjuntos, sólo algunas sentencias del sistema formal expresan afirmaciones sobre los números naturales. Los teoremas de incompletitud se refieren a la demostrabilidad formal dentro de estos sistemas, más que a la “demostrabilidad” en un sentido informal.