No entiendo Gödel del teorema de la incompletitud más

Question

Aquí está la imagen que tengo en mi cabeza de Modelo de la Teoría:

• una teoría es un sistema axiomático, por lo que permite probar algunas de las declaraciones que se aplican a todos los modelos consistentes con la teoría
• un modelo es un particular, consistente! -- función que asigna a cada declaración a su valor de verdad, es para ser considerado como un "concreto" del objeto, el tipo de cosa que suele pensar. Es sólo cuando se trata de modelos que tenemos la ley del medio excluido.

Mi comprensión de Gödel del primer teorema de la incompletitud es que no hay teoría que satisface una condición de finitud únicamente pueden precisar un modelo.

Así que no estoy realmente sorprendido por ella. La idea de las teorías de ser incompleta, de no completamente denir un modelo en particular-es bastante normal. El hecho de que ninguna teoría es completa parece análoga a cómo ninguna máquina de Turing se puede calcular cada función.

Pero luego he leído este hilo y hay dos afirmaciones en las respuestas que no tenían sentido para mí:

1. Auto-referencial declaraciones como ejemplos de improbable declaraciones , Como en "no hay un número cuya representación ASCII demuestra esta declaración".

Una declaración como esta no puede ser construido en la lógica proposicional. Supongo que esto tiene que ver con el concepto de un "lenguaje", pero ¿por qué iba alguien a usar un lenguaje que permite la auto-referencia?

No se que sería completamente derrota el propósito de utilizar la lógica clásica como el sistema para sintáctica implicaciones?

Si permitimos que esta como válida la pena, ¿no tenemos también para permitir que la paradoja del mentiroso (y, a continuación, el sistema sería incompatible)?

2. No demostrable declaraciones se "intuitivamente verdadero/falso" - de Acuerdo a esta respuesta, si encontramos que la conjetura de Goldbach era improbable, entonces, en particular, eso significa que no podemos producir un contra-ejemplo, por lo que sería "intuitivamente" sabemos que la conjetura es verdadera.

Cómo es esto sólo intuitiva? Si existe el $\sf PA$compatible con los modelos de $M_1$, $M_2$ donde Goldbach es verdadera en $M_1$ pero no $M_2$, a continuación, $\exists n, p, q$ tal que $n= p+q$ en $M_1$ pero no en $M_2$. Pero si $n=p+q$ es decidable de $\sf PA$, por lo que sea "$\sf{PA}+\sf{Goldbach}$" o "$\sf{PA}+\lnot\sf{Goldbach}$" debe ser incompatibles, y de Goldbach no puede ser improbable. A la derecha?

En cualquier caso, no sé lo que significa para la extensión a ser "intuitivamente correcto". ¿Sabemos algo acerca de la coherencia de cada una de las extensiones o ¿no?

Además de añadir a mi confusión, la respuesta afirma que la irracionalidad de la $e+\pi$ es no tal declaración, que puede ser realmente improbable. No veo cómo esto puede ser -- seguramente el mismo argumento se aplica; si $e+\pi$'s de la racionalidad es improbable, no existe $p/q$ que es igual, por lo tanto es irracional. A la derecha?

Answer 1

Esta respuesta sólo se aborda la segunda parte de su pregunta, pero le hizo muchas preguntas, así que espero que esté bien.

En primer lugar, hay en los comentarios una declaración: "Si Goldbach es no demostrable en PA luego es necesariamente cierto en todos los modelos." Esto es incorrecto. Si Goldbach eran ciertas en todos los modelos de PA, a continuación, PA resultaría Goldbach por Gödel Integridad Teorema (menos popular, siendo importante).

Lo que es cierto es:

Lema 1: Cualquier $\Sigma_1$ verdadera en $\mathbb{N}$ (el "modelo estándar" de la PA) es demostrable a partir de PA.

Estas notas (ver Lema 3) tiene una explicación: http://journalpsyche.org/files/0xaa23.pdf

Así que la afirmación correcta es:

Corolario 2: Si PA no decide Goldbach la conjetura se cumple en $\mathbb{N}$.

Prueba: La negación de Goldbach la conjetura es $\Sigma_1$. Así que si PA no demostrar la negación, entonces la negación de Goldbach no es cierto en $\mathbb{N}$ por el Lema 1.

Recuerde que $\mathbb{N}$ es un modelo, por lo que cualquier afirmación es verdadera o falsa en ella (en nuestra lógica). Pero PA es una teoría incompleta (suponiendo que es constante), por lo que no nos da la misma dicotomía de las cosas que puede probar.

Ahora, podría ser el caso de que el PA no resultar Goldbach (por tanto, su verdadera en todos los modelos de PA incluyendo a $\mathbb{N}$). Pero si estamos en la situación de Corolario 2 (PA no prueba Goldbach o su negación), a continuación, Goldbach es verdadera en $\mathbb{N}$ pero falsa en algún otro modelo de PA. (Esto podría ser suficiente para el número de teóricos de la imagino.) Este es también el lugar donde el problema de tu razonamiento. NO es cierto que si Goldbach falla en algunos modelos de $M$ de PA, a continuación, hay un estándar $n$ en $\mathbb{N}$ que no es la suma de dos números primos. Más bien, el testimonio del fracaso de Goldbach es sólo un elemento que $M$ cree que es un número natural. En algunos aleatoria del modelo, este elemento no debe ser en el sucesor de de la cadena de $0$.

Por otro lado, la racionalidad de la $\pi+e$ no es conocido por ser expresable por una $\Sigma_1$ declaración. Así que no se puede utilizar el Lema 1 de la misma manera.

Editado más tarde: no tengo mucho que decir sobre la cuestión de la auto-referencial declaraciones más allá de lo que otros han dicho. Pero yo sólo voy a decir que se debe ser cuidadoso para distinguir la lógica proposicional y de predicados de la lógica. Esto también va para su "panorama general de los modelos de la Teoría". Parte de lo interesante de los teoremas de incompletitud es la de que permiten la auto-referencia, sin ser tan obvio. En el PA hay suficiente potencia expresiva a las instrucciones de código y pruebas, y así la auto-referencial declaraciones acerca de las pruebas y demás son totalmente riguroso y claro.

Answer 2

Permítanme tratar de llegar al corazón de su incomprensión tan conciso como sea posible:

1. No estamos elegir deliberadamente el uso de un lenguaje que permite la auto-referencia, estamos obligados a hacerlo.

La única decisión que hemos tomado es la de una lógica que es lo suficientemente fuerte como para incluir aritmética de enteros. Lo que Gödel luego la prueba es que el acceso a los números enteros de forma automática nos permite construir un poco de auto-referencial declaraciones. Si queremos que los números enteros, entonces tenemos que aceptar la auto-referencialidad. Lo mismo es cierto en la teoría de la computabilidad. Máquinas de Turing no son elegidos porque se puede emular a sí mismos, ellos son los elegidos porque permiten todas las operaciones esperamos que un general de la computadora para hacer, que sólo pasa a incluir emulación de máquinas de turing.

2. Estamos auto-referencial con respecto a la teoría, no el modelo.

El tipo de sentencias que Gödels procedimiento nos permite construir son de la forma "X no puede ser infered de Y", como los enteros sólo se utilizan para crear una copia de un razonamiento lógico. Si tomamos el conjunto de axiomas de una teoría dada como Y, a continuación, podemos construir oraciones como: "X no es demostrable en la teoría", que es lo que conduce al teorema de la incompletitud si X es la frase en sí mismo. No hay manera de acceder a un modelo específico de la teoría y por lo tanto no hay forma de construir oraciones como "X es falso", que sería necesario para la del mentiroso paradoxon.

Answer 3

Permítanme comenzar por señalar que Gödel los teoremas generalmente son estudiados en el contexto de la lógica de primer orden, mientras que usted está describiendo lógica proposicional en su comprensión de la teoría y modelo.

Mientras que una teoría es más o menos la misma idea de una colección de sentencias y reglas de inferencia (aunque algunas personas definen una teoría como también ser cerrado bajo deducciones), un modelo es muy diferente. No es sólo una asignación de valores de verdad. Así, mientras lógica proposicional se ocupa mucho de "interruptores" que han verdadero y lo falso, la lógica de primer orden ofertas con colecciones de objetos, algunos de relaciones, algunas de las funciones, y algunas constantes con nombre, y lo que las declaraciones de una colección de objetos de la interpretación de estos sintáctica ideas va a satisfacer.

Las dos cosas, modelos y teorías, están conectados por Gödel de la integridad teorema que establece la lógica de primer orden es completa (que no es lo mismo que una teoría completa). Así que un enunciado es demostrable a partir de una teoría, si y sólo si es verdadera en todos los modelos de la teoría. Y es importante destacar, "la mayoría de las teorías" tienen un montón de modelos diferentes, ya sea por razones de cardinalidad (si una teoría tiene una infinita modelo, tiene uno de cada cardinalidad infinita) o incompleto (si una teoría no es completa tiene modelos completamente diferentes, incluso en la misma cardinalidad), o por otras razones (por ejemplo, tal vez la teoría es completa, pero hay cosas que están más allá del alcance de la lengua que no está decidido).

Y mientras utilizamos esta profunda conexión todo el tiempo en las matemáticas, sin siquiera pensar en ello la mayor parte del tiempo, la sintaxis y la semántica son independientes. Las teorías son no modelos, modelos y no teorías.

Cuando usted consigue el análisis de estas definiciones, se verá que una de primer orden lenguaje no puede ser auto-referencial. Se puede hablar de su propio modelo, ya que las herramientas para hacerlo son, simplemente, no sintáctico.

Pero, y aquí está la importancia de las condiciones de Gödel de la incompletitud teorema, algunos idiomas son suficientes para la internalización de la totalidad de la lógica de primer orden, y bajo algunos supuestos básicos de una teoría puede seguramente hacerlo.

En otras palabras, si $T$ es una teoría en un lenguaje que es "lo suficientemente rico" (donde "lo suficientemente rico" es realmente muy pobre: un binario relación o una función binaria sería suficiente), y $T$ puede internalizar la lógica de primer orden, entonces no es completa.

La idea clave es que una vez que tenemos las fórmulas que podemos llegar a ser una interpretación de la lógica de primer orden, podemos hacer todo tipo de extrañas construcciones. Esto no es auto-referencial, como es la "auto-conciencia". Pero incluso eso es un nombre inapropiado.

El punto sutil del teorema de la incompletitud es que en los diferentes modelos de la misma teoría, la internalización puede ser muy diferente. Es siempre incluir una copia fiel de lo real, la lógica de primer orden se utiliza "fuera" de la teoría, pero se pueden incluir nuevas partes y piezas que puede o no puede ser "razonable".

Por otra parte, dado que la noción de "finitud" no es capturado internamente por la lógica de primer orden, una vez que se interpretó que la lógica de primer orden, y se encontró un predicado para representar a la interpretación de una teoría de la $T'$si $T'$ tenía un número infinito de axiomas, si la internalización del proceso añade que "los nuevos bits", que invariablemente va a añadir nuevas frases a su propia interpretación de $T'$.

Así, entre los diferentes modelos de la teoría de la $T$, se puede obtener muy diferentes copias de la lógica de primer orden y las diferentes copias de $T'$. Gödel utiliza esto para construir una frase que no es demostrable a partir de $T$ sí.

Pero esto no es la paradoja del mentiroso. En ningún punto una frase realmente se refiere a sí mismo. Simplemente habla de una interpretación de la misma. Porque "verdadero/falso" es no es el mismo como "comprobable/improbable", a menos que se puede cuantificar sobre todos los modelos, que no se puede, ya que no son parte de su lenguaje.

Gödel quería evitar que la gente busca en todo esto y diciendo: "Oh, los locos de los lógicos... bueno cosas que realmente preocupa a los números naturales y no todos los de este formalismo a su alrededor". Así que en el proceso se demostró que todos los de esta codificación se puede hacer en un extremadamente robusto mediante el uso de los números naturales y algunos muy básicos número teórico de los resultados. Ahora los matemáticos tenían que prestar atención, esto ya no puede ser ignorado.

Finalmente, en cuanto a las observaciones sobre la Conjetura de Goldbach, que voy a dirigir su atención a Decidability de la Hipótesis de Riemann frente a la Conjetura de Goldbach.

Answer 4

1. Auto-referencial declaraciones como ejemplos de improbable declaraciones , Como en "[no es el número cuya representación ASCII demuestra esta afirmación][1]".

Una declaración como esta no puede ser construido en la lógica proposicional. Supongo que esto tiene que ver con el concepto de un "lenguaje", pero ¿por qué iba alguien a usar un lenguaje que permite la auto-referencia?

Aquí está el quid de la cuestión. En realidad, esta declaración puede ser construida. (O, al menos, una declaración en la que actúa como tal declaración puede ser construido.)

Como ustedes saben, no es posible tomar la frase "Esta frase no se puede demostrar en ZFC" y simplemente traducir directamente en el lenguaje de ZFC. Esto es porque, como usted sabe, no hay nada en el lenguaje de ZFC que significa "esta sentencia".

Lo que puede hacer, sin embargo, es crear una frase de G que es verdadera si y sólo si G no se puede demostrar en ZFC. ¿Cómo podemos hacer esto?

Bueno, echa un vistazo a las siguientes frases en inglés:

Si usted escriba lo siguiente y, a continuación, escribir de nuevo entre comillas, entonces la expresión resultante no se puede demostrar en ZFC: "Si usted escriba lo siguiente y, a continuación, escribir de nuevo entre comillas, entonces la expresión resultante no se puede demostrar en ZFC:"

Observe que la parte entre comillas es idéntica a la parte de fuera de las comillas, y por lo tanto "la resultante de la declaración" es idéntica a la de la declaración original. Esta declaración se refiere a sí mismo sin tener que hacer uso de la frase "esta declaración"!

Es posible hacer algo similar a los de arriba "complicado frase" en el lenguaje de ZFC. La frase deseada "es La frase con número de Gödel $N$ no se puede demostrar en ZFC", donde $N$ es un número en particular que es elegido de una manera similar a la anterior "complicado sentencia", por lo que $N$ es el número de Gödel de una frase que es lógicamente equivalente a "La sentencia con número de Gödel [$N$] no se puede demostrar en ZFC".

La razón de que esto no puede ser extendido a la forma de la paradoja del mentiroso es que el predicado "la declaración de $p$ no se puede demostrar en ZFC" puede ser definido en el lenguaje de ZFC, mientras que el predicado "la declaración de $p$ es falso" no se puede. (De hecho, la paradoja del mentiroso que mencionar es la prueba de que el predicado "la declaración de $p$ es falso" no puede ser definido en el lenguaje de ZFC.)

Answer 5

La prueba de Gödel del primer teorema de la incompletitud se basa en la invención de una proposición-a-entero de asignación. Las teorías se considera que son capaces de describir esto, como una función de cadenas de símbolos para los números enteros. Resulta que, incluso sin la auto-referencia, proposiciones puede incluso hablar acerca de sus propios números de Gödel. (No hay manera de prohibir esto en las teorías de interés). Y algunos son equivalentes a sus propios unprovability. Tales afirmaciones son verdaderas pero no demostrable, o falso, pero demostrable.

Si Goldbach la conjetura es falsa, tiene un contraejemplo, por lo que es decidable. Por lo tanto, si una teoría de la $T$ demuestra que la conjetura es indecidible en $T^\prime$, $T$ también demuestra la conjetura de verdad.