Pruebas del teorema de Gödel

Question

Estoy interesado en los diferentes contextos en los que Gödel los teoremas de incompletitud surgir. Además de los tradicionales Gödelian prueba a través de arithmetization y formalización de la paradoja del mentiroso también puede ser obtenido a partir de undecidability resultados de Turing y de la Iglesia. En el contexto de la teoría de la complejidad, no es difícil ver que el teorema de Gödel (así como de Turing del resultado) se sigue de la siguiente Chaitin del resultado: existe algún número natural N tal que para cualquier programa P de tamaño más que N es imposible demostrar, por ejemplo, en ZFC) que es la más pequeña (en el sentido de tamaño, yo. e. número de bits) de los programas que tienen las mismas entradas-salidas como P tiene. El número N depende en particular de la axiomática del sistema (es decir, ZFC) y no es muy grande, por lo que en realidad puede ser calculado.

Si Usted sabe de otras maneras a la Gödel los teoremas de la incompletitud, por favor, que las presente. En particular, puede Goedel del teorema de ser obtenidos sin el uso de la auto-referencial ideas?

Answer 1

Aparte de las habituales pruebas de diagonalización, tener una mirada en el modelo teórico de las pruebas (Kotlarski prueba, Kreisel la izquierda-rama de la prueba, etc..), entonces hay algunas otras pruebas que formalizar paradojas (Kikuchi, de Boolos, etc... hay cerca de una docena, la mayoría de ellos se mencionan en Kotlarski del libro).

Si usted no desea completa de la generalidad ("por cada rec. ax. la teoría T") luego, por supuesto, casi todas las pruebas en las modernas Unprovability Teoría no utiliza ningún tipo de auto-referencia (se puede construir un modelo de la teoría de las manos, el uso de algunos improbable combinatoria principio). Eche un vistazo a algunas de reciente modelo accesible de la teoría de pruebas de la París-Harrington Principio.

En el extremo inferior de la consistencia de la fuerza de espectro (ISigma_n, PA, ATR_0), para las teorías que ya tienen un buen clasificaciones de sus demostrablemente funciones recursivas, PH y otros improbable declaraciones también puede ser demostrado no demostrable mediante ordinal análisis (por ejemplo, Ketonen-Solovay estilo), sin el uso de diagonalización trucos.

Para más extremos de la fuerza de espectro (SMAH, SRP, etc), H. Friedman altamente técnicos resultados también no usar ningún tipo de diagonalización. Esta es una enorme maquinaria, y la nueva investigación que está sucediendo allí.

MDRP teoría da ejemplos interesantes: una mirada a la Jones expresión polinómica: de hecho, puede sustituir los números en ella y golpear a todos consistencia declaración de sus instancias. Hay otros similares para la n-consistencia para cada n.

Hay mucho más para decir: este es un gran tema, con un enorme bibliografía. Y, sí, mucho de el cuerpo de resultados en el tema es inédito. Puedo dar más punteros si es necesario.

Answer 2

Para Goedel del primer teorema de la incompletitud, usted puede apelar a la existencia de cualquier computably (de forma recursiva) conjunto enumerable $A$ que no computable (recursivo). En concreto, supongamos $T$ es $\omega$-de acuerdo, computable en teoría lo suficientemente potente como para representar todas las funciones computables. Deje $f$ total computable función de listado de todos los números Naturales en $A$, y deje $F$ representa a $f$ en la teoría de la $T$. Entonces no debe existir $n \in \mathbb{N}$ para que:

(1) $T \nvdash \exists m F(m, n)$ ni (2) $T \nvdash \lnot\exists m F(m, n)$

De lo contrario podríamos determinar si existe o no un determinado $n$ es de $A$ mediante la eficaz listado de todos los teoremas de $T$ hasta que recibió una de estas declaraciones, contradiciendo el hecho de que $A$ no es computable. Específicamente, (1) nos diría que $n \in A$ a $\omega$-consistencia de $T$ (es decir, existe un cierto número Natural $m$ lo $f(m) = n$), mientras que (2) nos diría que $n \notin A$ porque nunca se enumeran por $f$.

Si recuerdo correctamente, prueba a lo largo de estas líneas se menciona en la Introducción a la Complejidad de Kolmogorov y Sus Aplicaciones por Ming Li y Pablo Vitányi.

Answer 3

Gregor Lafitte del papel corto: "G\"odel de la incompletitud revisited" es es un descargables gratuitamente agradable y concisa descripción general de los diferentes tipos de pruebas con una larga lista de referencias:

hal.archives-ouvertes.fr/docs/00/27/45/64/PDF/74-89.pdf

Suplemento de 11 de octubre de 2011:

En un trabajo reciente, `La Sorpresa de Examen de la Paradoja y la Segunda Teorema de la incompletitud', los Avisos de la AMS Volumen 57, Número 11 (es puede ser descargado desde http://www.ams.org/notices/201011/rtx101101454p.pdf), los autores dan una nueva prueba de Gödel segundo incompleto teorema, basado en la complejidad de Kolmogorov, Chaitin de la imperfección teorema, y un argumento similar al examen sorpresa paradoja.

Answer 4

Posiblemente el argumento menos "autorreferencial" para el teorema de incompletitud de Gödel es el que se debe a Gentzen. Su análisis ordinal de las pruebas en PA muestra que cualquier orden que PA pueda probar que es un buen orden tiene ordinal menor que$\varepsilon_0$. Por lo tanto, cualquier pedido, definible en PA, que resulte ser un buen orden de longitud al menos$\varepsilon_0$ no puede probarse que sea un buen orden en PA.

Answer 5

Queridos Sergei y Juan. No es demasiado decir. Si te doy los 3 punteros - no significa que estos son buenos puntos de partida o que estos son los acontecimientos más importantes.

El polinomio de Jones es de JSL 43 (1978), no 2. pero de mí y De Smet mejorado recientemente el polinomio un poco (reducido por los 7 símbolos)... :)

Friedman libro es en su página web. La introducción es bastante fácil de leer, y contiene una larga lista de improbable declaraciones.

También puede echar un vistazo a mi "Breve introducción" en mi página de inicio, aunque estoy un poco avergonzado de que ingenuo papel de la mina escrito hace 6 años. Ahora estoy escribiendo mucho mejor pieza, con todas las motivaciones y explicaciones, y la Aritmética de Dividir la historia.... pero va a tomar algún tiempo.