¿Qué le pasa a esta "prueba" de que el primer teorema de incompletitud de Gödel es incorrecto?

Question

Edit: he añadido una respuesta a mí mismo, basado en las respuestas y comentarios.

---

Aquí es muy muy informal "prueba" (boceto) que el teorema de Gödel es malo (o al menos que la idea de la prueba es la incorrecta) :

Aproximadamente, la prueba de Gödel del teorema es la siguiente: Para cualquier decidable y conjunto consistente de axiomas $\Phi$ que contienen (o implica) el primer fin de los axiomas de Peano de primer orden lenguaje, podemos construir una sentencia de Gödel $G^\Phi$, de tal manera que ninguno $\Phi\vdash G^\Phi$ ni $\Phi\vdash \neg G^\Phi$, pero en el que conocemos a partir de un argumento en el meta-lenguaje que $G^\Phi$ es cierto. Para cualquier $\Phi$, por lo tanto, tendremos un contraejemplo a la integridad de la teoría de la $Th(\Phi)$. Por lo tanto sabemos que no $\Phi$ puede ser completa (donde completa significa que todos los de primer orden, las declaraciones pueden ser probada o refutada a partir de él).

Aquí es un fracaso de la propuesta para "eludir" el teorema de Gödel que ya he oído a alguien hacer: Simplemente defina $\Phi_1=\Phi\cup \{G^\Phi\}$, y ya sabemos que $G^\Phi$ que es verdad en la aritmética, sabemos que $\Phi_1$ es consistente. El problema es: podemos ahora formular una nueva sentencia de Gödel $G^{\Phi_1}$, que no pueden ser probadas de en $\Phi_1$, aunque es cierto que en el estándar de la aritmética.

---

Ahora, aquí está mi propuesta:

En lugar de tratar de añadir Gödel frases para el conjunto de axiomas, simplemente tomamos la enumeración de procedimiento, que enumera $\phi_i \in \Phi$ para el conjunto original de axiomas $\Phi$, y también enumera todas las sucesivas Gödel condenas $G^{\Phi}, G^{\Phi_1}, G^{\Phi_2},...$. Esto es posible, ya que $\Phi$ es decidable, y decidable conjuntos finitos cadenas son enumerables, por lo que podemos enumerar ellos sucesivamente, como $\phi_1, \phi_2, \phi_3$ donde $\phi_1$ es la primera declaración de la enumeración de $\Phi$, e $\phi_2 = G^\Phi$, e $\phi_3$ es la segunda declaración de la enumeración de $\Phi$, etc...

Podemos entonces definir el conjunto de axiomas $\Phi_\infty = \{\phi_1, \phi_2, ...\}$. Esto también tiene una sentencia de Gödel $G^{\Phi_\infty}$. Pero lo que podemos hacer, es agregar esto a la enumeración de procedimiento. Y luego el siguiente, y el siguiente, y así sucesivamente. Nos tomamos este proceso hasta el infinito, tal como lo hicimos para $\Phi$, y sólo seguir adelante.

Cada vez que un Gödel frase aparece, sólo tenemos que añadir a la enumeración. Ahora tenga en cuenta que: el conjunto de primer orden de las frases es contable, el conjunto de Gödel frases contables como bien (ya que es un subconjunto del conjunto de primer orden de las oraciones). Por lo tanto, podemos en este procedimiento se describe anteriormente enumerar todos los posibles Gödel frases.

El conjunto resultante de las sentencias constituye un enumerable y coherente conjunto de oraciones $\Psi$ que contiene el original de la $\Phi$, y además contiene la Gödel sentencias de todos los posibles conjuntos de axiomas $\Phi_x$. Por lo tanto, La sentencia de Gödel de $\Psi$ debe ser en $\Psi$ sí.

Por otra parte, podemos crear un "decidable versión" de $\Psi$, mediante la definición de $\Psi^*=\{\psi_1, \psi_1 \land \psi_2, \psi_1 \land \psi_2\land \psi_3, ... \}$, para todos los $\psi_1, \psi_2,... \in \Psi$. Por lo tanto, tiene una constante y decidable conjunto de primer orden de las oraciones que son verdaderas en el estándar de la aritmética, de contener los axiomas de Peano, y derivación de Gödel de la prueba de incompletitud.

Obviamente, esto es una contradicción con el teorema de Gödel. Entonces, ¿dónde está mi "prueba de croquis" mal?

Answer 1

Hay al menos dos problemas aquí.

En primer lugar, cuando dices "nos tomamos este proceso hasta el infinito y sólo seguir adelante", esa es una descripción informal, y sin tener que gastar algo de trabajo en lo que es más concreto que usted no tiene ninguna buena razón para pensar que se puede ser en realidad hecho para trabajar.

Afortunadamente, este tipo de trabajo ha sido, de hecho, hecho, y la manera estándar de hacer de concreto es hablar acerca de los pasos en el proceso de indexado por ordinal transfinito números, que es lo que voy a suponer que es lo que ustedes están proponiendo.

Entonces, sin embargo, un problema real que surge es: Gödel del procedimiento sólo funciona cuando la teoría original es de forma recursiva axiomatized, es decir, es computable si una determinada frase propuesta es uno de sus axiomas o no. Con el fin de hacer esto por su intermedio teorías, usted necesita ser capaz de algorítmicamente describir el proceso que produjo la teoría. Y hay (claramente hablando, pero pueden ser hechas precisa) por el momento hasta el infinito que no hay suficientes máquinas de Turing para describir la estructura de cada una de las teorías a las que te encuentres por el camino. Así que en algún momento vas a acercarse a un punto donde el proceso que produce los axiomas que ya tenemos es tan complejo que la combinación de la teoría no es recursivamente axiomatized más, y entonces el teorema de la incompletitud deja de funcionar.

---

Un segundo, comparativamente menor, el problema viene más adelante en su argumento:

desde el conjunto de primer orden de las frases es contable, el conjunto de Gödel frases contables como bien (ya que es un subconjunto del conjunto de primer orden de las oraciones). Por lo tanto, podemos en este procedimiento se describe anteriormente enumerar todos los posibles Gödel frases.

Este argumento parece ser la forma: "Hay un infinito contable de foos en total; aquí tenemos un conjunto de countably-una cantidad infinita de foo; por lo tanto, el conjunto que contiene a todos ellos", que no es válido, considere por ejemplo, la situación en la que un "foo" es un número natural y el conjunto en cuestión contiene todos los cuadrados perfectos.

(Tenga en cuenta también que no parecen tener definido lo que es un "posible Gödel frase" significa, que usted realmente debe hacer, antes de pretender que usted tiene todas las de ellos).

Answer 2

Tomando este argumento, refinado por Henning Makholm la observación acerca de la cuantificación con los números ordinales, y combinando esto con el hecho de que la conclusión del teorema de la incompletitud dice que usted no puede realmente lograr su objetivo demuestra un interesante teorema:

Teorema: No son contables números ordinales que no puede ser calculada por la máquina de Turing

Creo que no me he encontrado esto antes, pero he encontrado algunas referencias sobre este fenómeno. Aquí están los enlaces a wikipedia:

• Recursiva ordinal — las órdenes que se puede expresar mediante funciones computables
• Churck-Kleene ordinal — la primera no recursivo ordinal. Es contable.
• Gran contables ordinal — más cosas

En mi opinión, lo que está pasando aquí en cuanto a funciones computables en realidad es el mismo fenómeno como uncountability es en la teoría de conjuntos. Comparar, por un conjunto infinito $S$,

• "$S$ es recursivamente enumerable" significa "hay una computable bijection $\mathbb{N} \to S$"
• "$S$ es contable" significa "no existe un bijection $\mathbb{N} \to S$"

La única diferencia entre las dos nociones es qué tipo de funciones que permiten: si dibujamos las funciones de un universo de conjuntos o simplemente desde el universo de las máquinas de Turing.

En lenguaje alternativo haciendo hincapié en esta analogía, Gödel demuestra que todo completa, coherente extensión de PA es computably incontables. Las limitaciones de su argumento está el hecho de que usted no puede llegar a la primera computably innumerables ordinal $\omega_1^{CK}$.

Answer 3

Algunos tardía comentarios en su auto-respuesta por escrito:

Todo esto es más o menos correcto. Hay una teoría que se refiere como "Aritmética", que es el conjunto de todas las sentencias en el lenguaje de la aritmética, que son verdaderas en "la intención de modelo".⁽1⁾ Por definición, la Verdadera Aritmética es consistente y completa, por lo que por el primer teorema de la incompletitud no debe ser recursivamente enumerable. De ello se desprende que, para cualquier teoría de la aritmética T que es recursivamente enumerable, el conjunto de oraciones de Verdadero Aritmética que T no puede probar por sí misma no es recursivamente enumerable, como la que usted observó.

Tengo un ser quisquilloso con una cosa que usted escribió, aunque no es esencial para el razonamiento:

Por "en principio", me refiero a que si un oráculo nos dijo que la próxima gödel oración de esta enumeración cada vez que nos lo pidieron, nosotros podría, el uso de este oráculo, enumerar todos los gödel frases en mi de la construcción, y de ese modo "bypass" las limitaciones implícitas por el teorema de gödel.

Todo esto está bien,⁽2⁾ mientras nos mantenemos en mente que el "próximo" Gödel frase en la enumeración no se corresponden con la "nueva" teoría de la medida ordenada por el correspondiente ordinales. Softonic no en el hecho de necesitar un oráculo que nos diga la siguiente frase, en este último sentido: el oráculo es necesario para dar un único y uniforme listado de todos los Gödel frases, pero el orden en el que se produce esa lista no se corresponden con el orden de la correspondiente ordinales.

Para ilustrar esto, recordemos que su idea original dependía (recursivo) las listas de los números ordinales va de alguna manera más allá de lo finito. Tales listas no existe, pero el orden de la lista no se corresponden con el orden natural de los números ordinales, ya que de otra forma nunca podríamos conseguir más allá de lo finito. Por ejemplo, he aquí una lista recursiva de todos los ordinales a continuación ω+ω (donde ω es la primera infinito ordinal): 0,½, 1, ω+1, 2, ω+2, ...

⁽1⁾ la referencia a "La intención de modelo" es necesario para acomodar el siguiente hecho: para cualquier recursivamente enumerable de la teoría de la aritmética T, hay modelos de T, es decir, conjuntos de "números", junto con las definiciones de 0, 1, +, · que satisfacen los axiomas de T, y que no "la intención de modelo", porque por ejemplo, un determinado Gödel frase es falsa en esos modelos. Este hecho es resultado de la aplicación de Gödel integridad del teorema (que no debe confundirse con sus teoremas de incompletitud!) a la existencia de una sentencia de Gödel.

Técnicamente, el bien definedness de "la intención de modelo", y, por tanto, de la Verdadera Aritmética, depende de la suposición de que todas las sentencias en el lenguaje de la aritmética, de hecho tienen una "correcta" valor de verdad - una suposición de que la mayoría de los matemáticos damos por sentado, pero que algunas personas interesados en los fundamentos de la matemática rechazar o, al menos, pregunta: véase, por ejemplo, http://jdh.hamkins.org/question-for-the-math-oracle/

⁽2⁾ Si por "omisión del teorema de Gödel" te refieres a que la lista de axiomas se obtiene al final de este proceso debe ser completa, es decir, suficiente para deducir todos los enunciados Verdaderos de la Aritmética, usted puede ser que necesite para tener cuidado no sólo de que Gödel frases de la lista, pero lo que de orden de la lista de ellos: este es el objeto del ordinal notaciones, que he principalmente evitarse salvo para señalar que la Iglesia-Kleene ordinal, que estamos utilizando de forma efectiva aquí, no tiene un recursivamente enumerable.

Hay más detalles sobre esto en las respuestas a https://mathoverflow.net/questions/67214/pi1-sentence-independent-of-zf-zfconzf-zfconzfconzfconzf-etc - una pregunta de cerca en espíritu a los suyos, a pesar de que utiliza ZFC en lugar de la aritmética de Peano, y el segundo teorema de la incompletitud lugar de la primera.

Answer 4

Aquí es una condensación de mis pensamientos basados en las otras respuestas y comentarios.

Esta enumeración que he propuesto puede ser comparado con el de las funciones de los números naturales: Mientras que hay una contables de número de números naturales, hay un incontable número de funciones de los números naturales a los números naturales. Puesto que hay una contables número de máquinas de Turing (desde un TM debe ser descrito por un número finito de cadena), no debe ser, por tanto, un incontable número de funciones de $N$ $N$que no puede ser calculada.

El mismo principio es válido para la secuencia de gödel frases que he formulado: Esta secuencia de gödel frases "en principio" existe, y es contable, y podría, por tanto, "en principio" se hizo en un enumerable conjunto de axiomas (combinado con PA). Por "en principio", me refiero a que si un oráculo nos dijo que la próxima gödel oración de esta enumeración cada vez que nos lo pidieron, nosotros podría, usando este oráculo, enumerar todos los gödel frases en mi construcción, y de ese modo "bypass" las limitaciones implícitas por el teorema de gödel. Sin embargo, no tenemos un oráculo, y tiene que usar un TM para calcular estos gödel frases. Y el problema es, que así como hay incomputable funciones de $f:N\to N$ debido a uncountability del espacio de tales funciones, también hay un incontable número de orden en los números naturales, por lo que necesariamente habrá contables ordinales cuya enumeración en términos de números naturales no pueden ser calculadas. En otras palabras, si tenemos una colección con el fin de tipo igual a un ordinal, no podemos calcular la enumeración de los elementos de esta colección. (Aunque las sentencias en este conjunto de todos consiste finito de cadenas, y el conjunto es contable)

Por otra parte, dado que el teorema de Gödel se cumple para cualquier enumerable conjunto de axiomas, se podría emplear la inducción transfinita: Vamos a $\alpha(\Phi)$ significa algo así como: "no hay una sentencia de gödel $G^\Phi$ $\Phi$ (que no está implícita $\Phi$) o $\Phi$ no es recursivamente enumerable". Podríamos utilizar la inducción transfinita combinado con el teorema de gödel para mostrar que para cualquier ordinal $\beta$, se debe sostener que $\alpha(\Phi_\beta)$.

Pero si $\Phi_\alpha$ es recursivamente enumerable, siempre podemos añadir su sentencia de gödel y las de todos sus sucesores para la próxima $\Phi_\gamma$, así que si continuamos con este proceso que he descrito, la adición de todos los gödel oraciones, entonces debemos, finalmente, llegar a un conjunto de $\Psi^*$ cuyos elementos no son recursivamente enumerables. Por otra parte, si dejamos $\Psi=\Psi^* / PA$ (donde $PA$ son los axiomas de peano), a continuación, $\Psi$ tampoco es recursivamente enumerable, sin embargo, este conjunto contiene sólo los gödel frases que sabemos a partir de meta-análisis lógico son verdaderas en el estándar de la aritmética, pero no demostrable de $PA$.

Por lo tanto podemos afirmar que la extensión de el teorema de Gödel:

Teorema. Deje $\Phi$ ser un recursivamente enumerable y coherente conjunto de axiomas que contiene los axiomas de peano. Entonces existe un no-recursivamente enumerable y countably conjunto infinito de oraciones $\Psi$, de tal manera que para todos los $\psi\in \Psi$: Ni $\Phi \vdash \psi$ ni $\Phi \vdash \neg \psi$

Este resultado (en la medida de lo informal a prueba de sketch es correcto) es mucho más fuerte que el teorema de gödel, y sigue muy directamente desde el teorema de gödel.

Esencialmente dice: Hay una infinita cantidad de oraciones que son verdaderas en el estándar de la aritmética, pero nunca se puede saber qué frases que sean, no dejan de demostrar que a partir de un conjunto de primer orden de los axiomas. (podemos enumerar un subconjunto de ellos, incluso un subconjunto infinito, pero también hay un subconjunto infinito que nunca podemos encontrar).

EDIT: creo que el teorema se puede fortalecerse aún más: tenga en cuenta que el hecho de que no existe tal no enumerable $\Psi$ puede por sí mismo no ser que interesante, porque, en principio, puede ser que, si tomamos la lista de todos los enunciados que son verdaderos pero no es demostrable a partir de $PA$, que esta lista es de repente enumerable. ($\Psi$ es un subconjunto de este conjunto, y si un subconjunto no es enumerable, todavía puede ser que el superconjunto es enumerable). Pero este no es el caso: Supongamos que el conjunto $\Omega$ de las frases que son verdaderas pero no demostrable de $PA$ son enumerables. Luego, se puede crear un nuevo conjunto $\Phi_\Omega=PA \cup \Omega$, que es enumerable. Pero entonces, por el teorema de gödel no existe una sentencia de gödel $G^{\Phi_\Omega}$ tal que, y su negación, no es demostrable a partir de $\Phi_\Omega=PA \cup \Omega$, pero sigue siendo cierto. Pero entonces, por la definición de $\Omega$,$G^{\Phi_\Omega}\in \Omega$, por lo que el $\Omega \vdash G^{\Phi_\Omega}$. Esta es una contradicción. Por lo tanto, $\Omega$ no puede ser enumerable.

Teorema. Deje $\Phi$ ser un recursivamente enumerable y coherente conjunto de axiomas que contiene los axiomas de peano. A continuación, el conjunto de oraciones $\Omega=\{\psi : \text { neither } \Phi \vdash \psi \text{ nor } \Phi \vdash \neg \psi\}$ es countably infinito y no de forma recursiva-enumerable.

Answer 5

Por lo tanto, si partimos de una base axiomática, y encontrar la sentencia de Gödel y agregar, tenemos otro conjunto de axiomas que tiene un diferente sentencia de Gödel.

Se observó que todos son de estructura similar, y de forma recursiva enumerados a todos y que acaba de agregar nuevas axiomas. Es una idea interesante.

Por desgracia, no está en primer orden la lógica más. Yo tengo en el mismo lugar años atrás. He encontrado una construcción que derrotó a la detención problema y, por tanto, pateó la base de Gödel en algo tan corto que se puede verificar con facilidad. Después de un montón de voladuras alguien finalmente me dijo. La capacidad para ejecutar el infinito de pasos como que, invariablemente, los resultados en un segundo orden de la lógica teorema. Gödel sólo se aplica a la primera orden de la lógica de teoremas.

(En algunas formulaciones de las leyes de la física (como el de definir recursiva enumeraciones de acabado en un tiempo finito) podemos demostrar que de la lógica de primer orden es equivalente a la lógica de segundo orden. Si has llegado hasta aquí significa que la formulación de las leyes de la física no es en primer orden de la lógica.)