¿Es posible deducir Godel ' primer teorema de incompletitud s de Chaitin ' Teorema del estado incompleto de s?

Question

Quiero preguntar si es posible deducir de Gödel primer teorema de la incompletitud de Chaitin del teorema de la incompletitud. Estoy leyendo el siguiente AMS-Aviso de artículo. Los autores afirman que:

La principal dificultad conceptual en Gödel original prueba de ello es el auto-referencia de la declaración de "esta declaración no tiene ninguna prueba." Conceptualmente más simple prueba del primer teorema de la incompletitud, basado en Berry paradoja, fue dado por Chaitin.....

Pero la declaración que probé es la Chaitin del teorema de la incompletitud, que apareció diferente de la de Gödel primer teorema de la incompletitud. También contendeded que:

Una diferente de la prueba de Gödel primera incompleto teorema, también basado en el de la paradoja de Berry, fue dada por Boolos [Boolos89] (ver también [Vopenka66, Kikuchi94]). Otras pruebas para el primer incompleto teorema también son conocidos (para una encuesta reciente, ver [Kotlarski04]).

¿Significa esto que Chaitin del teorema de la incompletitud de Gödel implica el primer teorema de la incompletitud? Pido aquí me siento un poco confundido con la relación lógica.

Los autores también hizo una dudosa afirmación de que:

Gödel considera los relacionados con la declaración de "esta declaración no tiene ninguna prueba." Él mostró que esta declaración puede ser expresado en cualquier teoría que es capaz de expresan elementales de la aritmética. Si la declaración de tiene una prueba, entonces es falso; pero ya en una constante la teoría de cualquier instrucción que tiene una prueba debe ser cierto, podemos concluir que, si la teoría es consistente, la declaración no tiene pruebas. Desde la declaración de no tiene pruebas, es cierto (sobre N). Por lo tanto, si la teoría de la es consistente, tenemos un ejemplo de un verdadero declaración (sobre N) no tiene ninguna prueba. La principal dificultad conceptual en Gödel original prueba de ello es el auto-referencia de la declaración de "esta declaración no tiene ninguna prueba."

que es muy similar a Wittegenstein la observación en la prueba de Gödel:

Me imagino que alguien pidiendo mi consejo; él dice: "he construido una proposición (voy a usar 'P' para designar a) en Russell simbolismo, y por medio de algunas de las definiciones y de las transformaciones que puede ser interpretada de este modo que se dice: 'P no es comprobable en Russell del sistema'. Debo decir que esta proposición, por un lado, es cierto, y por otro lado no demostrable? Para suponer que eran falsas; entonces es cierto que es demostrable. Y que seguramente no puede ser! Y si se demuestra, entonces se demuestra que no es demostrable. Por lo tanto sólo puede ser cierto, pero no demostrable."[8]

y esto ha sido refutado por Gödel mismo:

"Es evidente a partir de los pasajes que citan que Wittgenstein "no" entender [el primer teorema de la incompletitud] (o fingió no entender). Él lo interpretó como una especie de paradoja lógica, mientras que en realidad es justo lo contrario, es decir, un teorema matemático dentro de un absolutamente incuestionable parte de las matemáticas (finitary de la teoría de números o combinatoria)." (Wang, 1996:197)

Creo que debo la opinión de otra persona como estoy bastante confundido - ¿qué es lo correcto, lo que está mal aquí?

Answer 1

Es posible deducir de Gödel primer teorema de la incompletitud de Chaitin del teorema de la incompletitud?

Gödel del teorema de la incompletitud, en su forma moderna, el uso de Rosser del truco, sólo requiere que (más allá de ser eficaz y lo suficientemente fuerte), la teoría debe ser coherente. No hay ningún requisito de que la teoría tiene que ser $\omega$-consistente o cumplir con cualquiera de solidez suposición más allá de la simple consistencia. No se puede aplicar el teorema de Chaitin en su forma habitual a estas teorías, en general, debido a la forma habitual de Chaitin del teorema de asume (por ejemplo, muchas pruebas de Chaitin del teorema de asumir como un extra solidez supuesto de que la teoría sólo demuestra la verdad de las declaraciones.)

Muchas de las "pruebas alternas" también requiere de una mayor supuestos que el estándar de la prueba del teorema de la incompletitud. Tienes que ser muy cuidadoso al leer acerca de esto para comprobar que los supuestos que se incluyen en cada teorema.

En particular, la prueba de Chaitin del teorema presentado por Kritchman y Raz, sin embargo, no es necesario para asumir cualquier particular solidez más allá de la coherencia. Voy a explicar esto en detalle.

Se necesita asumir que $T$ es lo suficientemente fuerte. En particular, se supone que si $n$ $L$ satisfacer $K(n) < L$,$T \vdash \hat K(\dot n) < \dot L$. Aquí $\dot n$ $\dot L$ son términos de la forma $1 + 1 + \cdots + 1$ correspondiente a$n$$L$, e $\hat K$ es una fórmula de la aritmética definida directamente a partir de la definición de $K$. (Tenga en cuenta que el conjunto de pares $(n,L)$ $K(n) < L$ es recursivamente enumerable, por lo que no hay problema en asumir la $T$ demuestra que todos los verdaderos frases de ese formulario.)

Dada la suposición $T$, su prueba es como sigue (reformulado en términos más precisos):

Comenzar la prueba

Dado $L$, podemos hacer un programa de $e_L$ que hace lo siguiente:

1. La búsqueda de cualquier $n$ tal que $T \vdash \hat K (\dot n) > \dot L$. Hacemos esto mediante la búsqueda a través de todos los $T$-pruebas de manera exhaustiva.

2. Salida de la primera de dichas $n$ encontramos, si alguna vez encontramos uno.

Porque podemos código de $L$ en el programa como una constante fija, usando el estándar de codificación de los métodos, la longitud de la $|e_L|$ $e_L$ no es peor que la $2\log(L) + C$ para algunas constantes $C$. En particular, se puede fijar un $L$$|e_L| < L$. Asumir un $L$ es fijo.

Para esto $L$, supongamos $e_L$ devuelve un valor, $n$. A continuación,$K(n) \leq |e_L| < L$. Por nuestra suposición de que $T$ es lo suficientemente fuerte, esto significa $T$ demuestra $\hat K (\dot n) < \dot L$.

Pero si $e_L$ vuelve $n$ $T$ también es $\hat K(\dot n) > \dot L$. Esto significa que si $e_L$ devuelve un valor, a continuación, $T$ es inconsistente. Así, si asumimos $T$ es consistente, entonces $e_L$ no puede devolver un valor. Esto significa que, para nuestra fijo $L= L_T$, $T$ no puede probar la $\hat K(\dot n) > \dot L$ cualquier $n$.

Por lo tanto, si tomamos $n = n_T$ a ser tal que $K(n) > L$, $\hat K (\dot n) > \dot L$ es una verdadera declaración de que no es demostrable en $T$.

Final de la prueba

Esta prueba sólo se da (en cursiva) resulta:

Si $T$ es una constante, eficaz de la teoría de la aritmética que resulta cada fórmula verdadera de la forma $\hat K(\dot n) < \dot L$, entonces no es una declaración verdadera de la forma $\hat K(\dot n) > \dot L$ que no es demostrable en $T$.

Este es casi el mismo como Gödel del teorema de la incompletitud. La única diferencia es que la costumbre de la prueba del teorema de la incompletitud nos da una explícita fórmula que es verdad, pero no es demostrable en $T$ (es decir, la Rosser frase de $T$). Por otro lado, la prueba en cursiva nos obliga a encontrar $n_T$ para tener un ejemplo claro, y no existe ningún algoritmo para hacer esto.

Esta es una motivación para lo que creo que es el "estándar" de Chaitin del teorema. En esa forma, nos fijamos en su lugar para no demostrable oraciones de la forma ($\dagger$): $(\exists x)[\hat K(x) > \dot L]$.

Porque podemos calcular $L= L_T$, se puede calcular una sentencia específica de esa forma para $T$. Pero, para que la prueba funcione, necesitamos tener un $n$ tal que $T \vdash \hat K(\dot n) > \dot L$. Así que tenemos que agregar un adicional de solidez hipótesis del teorema, es decir, que si $T$ demuestra una frase de la forma ( $\dagger$ ), a continuación, hay un $n$ tal que $T$ demuestra $\hat K(\dot n) > \dot L$.

En general, en esta versión de Chaitin del teorema, tenemos una explícita condena, pero con una mayor solidez de la asunción. La prueba de Gödel del teorema de la incompletitud el uso de Rosser del método nos da una explícita condena sin más fuerte solidez de la asunción.

Answer 2

Por lo que puedo juzgar, un muy buen libro introductorio sobre los Teoremas de Gödel es Torkel Franzén, el teorema de Gödel : Una guía incompleta para su uso y el abuso (2005).

Es sencillo, pero vacío de la "costumbre" lógicas y filosóficas erróneas.

En ella se puede ver Cap.8 : la Incompletitud, la Complejidad y el Infinito, con una discusión sobre el teorema de Chaitin [página 139] :

Supongamos $T$ es una constante en el sistema formal incorporación de la habitual "cierta cantidad de la aritmética." Chaitin del teorema de la incompletitud de los estados que entonces hay un número $c$ dependiendo $T$ tal que $T$ no demuestra ninguna declaración de la forma "la complejidad de la cadena de $s$ es mayor que $c$."

Ya que hay cierto que ese tipo de declaraciones, se sigue que, a menos que $T$ demuestra declaraciones falsas acerca de la complejidad, hay afirmaciones de la forma "la complejidad de la cadena de $s$ es mayor que $c$" que se indecidible en $T$.

Por lo tanto, es una "variante" de Gödel del Teorema de la Incompletitud.

La esencia de Gödel del primer teorema de la incompletitud es no el hecho de que construir un auto-referencial frase: sabemos que ya desde los antiguos Griegos (véase la Paradoja del Mentiroso).

La clave-el resultado de la primera teorema de la incompletitud es que se establezca :

que en cualquier sistema formal consistente $F$ dentro de la cual una cierta cantidad de la aritmética puede ser llevado a cabo, están las declaraciones de la lengua de $F$ que puede ser probada ni refutada en $F$.

Suponga $F$ es un sistema formalizado que contiene Robinson aritmética $\mathsf Q$. A continuación, una frase $G_F$ de la lengua de $F$ puede ser mecánicamente construido a partir de $F$ tal forma que:

Si $F$ es consistente, entonces $F ⊬ G_F$.

Si $F$ $1$- de acuerdo, entonces $F ⊬ ¬G_F$.

Tal independientes, o "indecidible" (que es, ni demostrable ni rebatible en $F$) declaración de $G_F$ $F$ es a menudo llamado "la sentencia de Gödel" de $F$.

De hecho, en circunstancias favorables, se puede demostrar que $G_F$ es cierto, siempre que $F$ es de hecho consistente. [...] Por esta razón, la sentencia de Gödel es a menudo llamado "cierto, pero no demostrable".

---

Puede ser útil citar Gödel las declaraciones de cierre en la introducción :

• K. Gödel, SOBRE FORMALMENTE INDECIDIBLE PROPOSICIONES DE PRINCIPIA MATHEMATICA Y SISTEMAS RELACIONADOS con la I (1931) [véase Jean van Heijenoort, (editor) De Frege a Gödel : Un Libro Fuente en la Lógica Matemática, 1879-1931 (1967), página 598-599] :

La analogía de este argumento con el Richard antinomia salta a la vista. Está estrechamente relacionado con el" Mentiroso"; por la proposición indecidible [...] los estados que [él] no es demostrable. Por tanto, tenemos ante nosotros una proposición que dice acerca de sí misma que no es comprobable [ PM]$^{15}$.

[$footnote^{15}$ : Contrariamente a las apariencias, una proposición no implica defectuosa de la circularidad, para inicialmente onlyl afirma que un determinado bien definido por la fórmula [...] es improbable. Sólo posteriormente (y por así decirlo por casualidad) hace que esta fórmula es, precisamente, el uno por el cual la propuesta se expresó.]

El método de la prueba sólo se explica claramente puede ser aplicado a cualquier sistema formal que, en primer lugar, cuando se interpreta como la representación de un sistema de nociones y proposiciones, tiene a su disposición suficientes medios de expresión para definir las nociones que ocurren en el argumento anterior (en particular, la noción de "comprobable fórmula") y en el que, en segundo lugar, cada comprobable fórmula es verdadera en la interpretación considerado.

El propósito de llevar a cabo la prueba con total precisión en lo que sigue es, entre otras cosas, para sustituir el segundo de los supuestos que acabamos de mencionar [es decir, "cada comprobable fórmula es verdadera en la interpretación considera"] por una puramente formal y mucho más débil [énfasis añadido].

---

---

Respecto de Wittgenstein argumento, parece un poco demasiado "simplificado" :

• parece que Wittgenstein "equiparar" verdadero con comprobable; el resultado de Gödel dice exactamente lo contrario: en general, no podemos hacerlo.

• Wittgenstein formación acerca de la lógica fue con Frege y W&R Principia Mathematica, es decir, con logicismo y me parece que en el momento de la observación que él todavía la concepción de un single, "universal" logico-matemático del sistema; Gödel el resultado es relativa a una teoría formalizada $F$ con ciertas propiedades (básicamente, que contiene la aritmética).

• Wittgenstein omite lo esencial de la "condición inicial" que la teoría de la $F$ debe ser consistente.

Pero sobre Wittgenstein y su "incomprensión" del teorema de Gödel, se puede ver un análisis mucho más profundo de Julieta Floyd, En la que dice Lo Que Realmente Quiere Decir: Wittgenstein, Gödel, y el Trisection del Ángulo, en Jaakko Hintikka (editor), De Dedekind a Gödel : Ensayos sobre el Desarrollo de los Fundamentos de las Matemáticas, (1995), pp 373-425.

---

Notas : usted puede encontrar aquí una revisión de Franzén del libro.

Se puede ver también : Panu Raatikainen, En la Relevancia Filosófica de Gödel de los Teoremas de Incompletitud.