Gödel dice: contables de las pruebas, infinidad de conjeturas?

Question

Yo pensaba que entendía Gödel del Teorema de la Incompletitud decir:

• A partir de ZF, no sólo una contables número de pruebas se puede escribir

• El número de posibles conjeturas es incontable.

• Por lo tanto, no es una conjetura de S tales que no se puede escribir una la prueba de la S, pero también no se puede escribir una prueba de -S.

Sin embargo, más tarde me di cuenta que el número de conjeturas se puede escribir también es contable.

Lo que me estoy perdiendo?

Answer 1

No hay nada acerca de countability o uncountability en la prueba de Gödel. Todos los conjuntos de declaraciones y pruebas, se asume contables.

Existe una relación lógica entre lo que Gödel hizo y cómo Cantor demostró que algunos conjuntos fueron "innumerables" - ambos son lo que llamamos "diagonal argumentos." Diagonal argumentos de los cultivos en lotes de la lógica, especialmente cuando estamos hablando acerca de los límites de lo que podemos hacer con los sistemas formales.

El abuelo de la diagonal argumento de la paradoja de Russell. Esencialmente, nos obliga a darnos cuenta de que no podemos hablar de "la colección de todo" en un modo tan ingenuo y no obtener una paradoja. Tiene una fuerte relación con la declaración, "Este enunciado es falso", que claramente no se puede asignar un valor de verdad.

Gödel fue capaz de demostrar que si (finitely descriptible) sistema de axiomas era lo suficientemente complicado como para contener la aritmética, entonces era lo suficientemente complicado como para hablar acerca de las pruebas en sí mismo, y, en particular, para escribir una declaración que dice: "Esta declaración no tiene la prueba en el X sistema de axiomas." Si esta declaración tenía una prueba, entonces seríamos capaces de refutar, así. Si la declaración no tiene pruebas, entonces es cierto.

Una manera de verlo es pensar en términos de algo que se llama "la computabilidad." El conjunto de comprobable declaraciones en un sistema de axiomas es "recursivamente enumerable." Pero si todos los teoremas son decidable por pruebas, entonces el conjunto de los comprobable declaraciones y el conjunto de disprovable declaraciones comprenden todas las declaraciones, y, si la teoría es consistente, son disjuntas. Un recursivamente enumerable conjunto cuyo complemento es también r.e. es necesariamente "recursiva." Gödel esencialmente demostrado que esto no puede ser.

(Tenga en cuenta que la teoría de la computabilidad, la distinción entre "recursivo" y "no recursiva" se parece mucho a la teoría de la distinción entre "contables" y "incontables.")

Answer 2

Aunque estoy de acuerdo con los otros carteles que la conexión directa que estás buscando no existe, no hay otra prueba del teorema de Gödel que probablemente tiene mucho el sabor que buscas; en esencia, algunas instrucciones improbable porque están demasiado complicado! En particular, considere la posibilidad de la declaración de '$x$ es el número más pequeño que puede ser calculada por una particular máquina de turing universal) programa de la longitud de menos de $N$' (donde $N$ es un número que se le va a dar específicamente más adelante). Ya que hay sólo $2^N$ % de programas de la longitud de menos de $N$, $x$ debe existir, lo tomamos $N$.

Pero la descripción de esta instrucción toma $k_1\log N+k_2$ bits para algunas constantes $k_1$ $k_2$ (desde $N$ puede ser escrito en binario); y los axiomas de la lógica formal del sistema, junto con un procedimiento para enumerar todas las consecuencias de los axiomas, tiene sólo un número finito $k_3$ de los bits adicionales. Así que si la declaración de '$x$ es el número más pequeño que puede ser calculado por un programa de la longitud de menos de $N$' fueron comprobable, luego de su prueba — como enumerado por la máquina de Turing — proporciona un programa de duración $k_1\log N+k_2+k_3$ bits para el cómputo de los $x$. Pero hay sin duda un $N$ tal que $N\gt k_1\log N+k_2+k_3$, lo que tomamos $k_1$, $k_2$ y $k_3$, por lo que si esta declaración se comprobable entonces tendríamos una contradicción - una descripción para $x$ de la longitud de menos de $N$!

Esto significa que por lo suficientemente grande como $N$ la instrucción debe ser improbable para todos los $x$, pero es sin duda cierto (como se señaló inicialmente) para algunos $x$. En esencia, los axiomas del sistema formal sólo tienen una cantidad finita de información en ellos, y así las declaraciones mucho más complicada que la cantidad finita de información son inherentemente improbable. (Esta interpretación del argumento — que es esencialmente un formalizado versión de la paradoja de Berry — es debido, AFAIK, a Gregory Chaitin, y usted puede comprobar sus escritos para un poco más de información sobre ella, un juego de palabras.)

Answer 3

Gödel primer teorema de la incompletitud de los estados que, si tenemos algo de primer orden de la teoría de la que se extiende la Aritmética de Peano (que en realidad no necesita toda la fuerza de la PA, pero que está al lado del punto) y es consistente y recursivamente enumerable (que, intuitivamente, significa que usted tiene un concreto procedimiento para escribir todos los axiomas), entonces hay una instrucción en el lenguaje de la teoría que es independiente de ella.

(Este teorema se aplica también a las teorías que se puede interpretar la aritmética de Peano, como ZF.)

La prueba de eso es por la diagonal argumento (como lo son casi todas las pruebas de las declaraciones de este tipo), pero que no depende de nada ser incontables. De hecho, todos los objetos considerados son contables. El concepto clave es el de no countability, pero recursiva enumerability.

Tal vez más interesante, de Gödel del segundo teorema de la incompletitud dice que para cualquier teoría de la $T$, $T\cup \{\varphi\}$ es coherente, donde el $\varphi$ es una afirmación que, si se interpreta como una declaración acerca de los números naturales, significa aproximadamente "$T$ es incoherente", o, más exactamente, "$T$ demuestra que $0=1$", mientras que si $T$ está satisfecho con números naturales, entonces $T\cup \{\neg\varphi\}$ también es consistente, por lo que en ese caso hay un "concreto" es un ejemplo de una afirmación que no puede ser decidido por $T$.

La plena comprensión de estos teoremas requeriría cierta familiaridad con la prueba de teoría y modelo de la teoría, creo.

Answer 4

Gödels es el teorema acerca de la aritmética, y, como los sistemas de ZF que se extienden, pero sobre todo acerca de la aritmética.

Hay un problema de countability que es relevante para el teorema de Gödel, pero el número de conjeturas que no tiene nada que ver con ella. El conjunto de los conjuntos de números es incontable, mientras que en la práctica formal del sistema define sólo countably muchos conjuntos. Esto significa que si se formaliza la noción de conjunto en el principio de la inducción (equivalentemente, si giramos el principio de la inducción en un esquema y evitar hablar de conjuntos directamente) una pequeña minoría de los conjuntos de jugar un papel en cualquier prueba formal. Esto deja abierta la posibilidad de que formalmente indefinible contraejemplos a la inducción. Pero no creo que esto es todo lo que hay a Gödel de la prueba, sin embargo. Tenía que demostrar por qué en este caso en particular es importante que las pocas series son definibles.

Answer 5

La prueba puede ser "entendida" como que :

Vamos a decir que todas las conjeturas son comprobable (en forma positiva o negativa). Así, para cada conjetura, hay un número finito de prueba.

Vamos a hacer un programa de $P$ que tiene una fórmula (una conjetura), una búsqueda de la prueba, por probar todas las pruebas hasta encontrar el correcto (es Un proceso muy largo). Si la prueba es positiva (la fórmula es verdadera), entonces $P(F)=1$ else $P(F)=0$

Pero un programa es algún tipo de fórmula. Así que puedo hacer una conjetura $C$, diciendo: "$P(C)=0$ " (este es el punto principal). Pero si es cierto $P(C)=1$ y si es false $P(C)=0$. Es simplemente imposible !

Así que no hay ningún programa de ese tipo,$P$, y algunas fórmula no tiene ninguna prueba (positiva o negativa).