Paradoja de Gödel: ¿por qué "una prueba de que una declaración universal no es demostrable" no es una prueba válida de que esta declaración es verdadera?

Question

Aquí hay una paradoja tengo algunos problemas para resolver:

Como tengo entendido, por uno de Gödel de los teoremas de incompletitud, en un primer orden de la lógica de la teoría con la aritmética de Peano, se pueden encontrar algunas no trivial universal cerrado frases (que comienza con un "para todos" cuantificador, todas las variables están enlazados) que puede ser demostrado ser improbable.

Consideran que un improbable universal de la declaración de la forma "Para todo x, P(x)". Hemos demostrado que no puede haber ningún contador de ejemplo de esta afirmación, precisamente porque encontrar un ejemplo contrario podría refutar la declaración de ahí que contradice el teorema de Gödel, que dijo que esta declaración no puede ser probada ni refutada. Por tanto, la declaración debe ser cierto.

Como se puede observar, mi párrafo anterior es una secuencia válida de argumentos que explican por qué mi considerados universales declaración debe ser cierto. Este párrafo anterior es, por la definición misma de la prueba, una prueba de la sentencia dada. Mi conclusión es que cualquiera de Gödel estaba equivocado, o de las matemáticas son inconsistentes :)

Lo que está mal con mi razonamiento ? Puede usted explicar por qué el segundo párrafo no sería una prueba válida? ¿Tiene algo que ver con el metalenguaje? Incluso si metalenguaje se mezcla con el lenguaje regular, no todo el metalenguaje utilizado aquí ser codificado en un primer orden de la lógica con la aritmética de Peano, y ver como no parte de una más fuerte de la teoría ?

Answer 1

El paso clave en su argumento es cuando te dicen que si hay un contraejemplo a $\forall x.P(x)$, entonces la teoría de la $T$ hablamos puede demostrar que en realidad es un contraejemplo.

La forma particular de $P(x)$ que sale de Gödel de la construcción tiene la propiedad de que cada vez que tenemos un determinado número $\bar n$, entonces la fórmula $P(\bar n)$ siempre será verdad, y $T$ demuestra que es cierto.

Sin embargo, no constituye una prueba de $\forall x.P(x)$. Pensar que hace invoca una suposición tácita de que todo nuestro $\forall x$ rangos puede ser expresado como un número. Para asegurarse de que esta es la verdad acerca de nuestra intención de interpretación de $T$ como el "real de los números naturales", pero en fin para $T$ a demostrar algo que no solo necesita ser verdadero en la intención de interpretación, sino también en todos los otros interpretación que satisface los axiomas de $T$.

Aquí el razonamiento que se ejecuta en problemas, porque sabemos que $T$ debe tener algunos de los modelos en algunos de los elementos que no corresponden a los números. (Esto es así independientemente de que el teorema de la incompletitud; la "costumbre compacidad argumento" muestra que un modelo debe existir para que cualquier teoría que pueda hablar acerca de los naturales). Por lo tanto, el hecho conocido de que $P$ es cierto y comprobable acerca de todos los números no implica que el $\forall x.P(x)$ es verdadera en todos los modelos, y por lo tanto no podemos concluir que debe ser comprobable. Y así todo el argumento se cae a pedazos.

---

Gödel de la noción de un "$\omega$coherente con la" teoría requiere que no hay ninguna fórmula $\varphi(x)$ tal que $T$ tanto resulta $\varphi(\bar n)$ acerca de cada número, y demuestra $\exists x.\neg\varphi(x)$ que es el mismo que $\neg \forall x.\varphi(x)$. Una manera de mostrar que un $T$ es $\omega$-consistente es demostrar que tiene algún modelo donde todos los elementos son números; interpretarse en el modelo de la sentencia de Gödel será cierto. El original de la incompletitud prueba explícitamente asumido que las $T$ es $\omega$-consistente y que utilizado para argumentar que $T$ no puede probar la $\neg\forall x.P(x)$. Más tarde, Rosser encontrado una manera de evitar este supuesto, y en lugar de simplemente asumir que $T$ es consistente.

Answer 2

Lo que está faltando es que "verdadero" y "falso" son siempre relativos al modelo, pero en la aritmética que se refieren al modelo estándar, a menos que se indique lo contrario.

Ahora, si hay un contraejemplo a una $\Pi_1$ declaración, entonces, es un testimonio de su negación, de una $\Sigma_1$ declaración. Pero aquí está la cosa, $\sf PA$ es $\Sigma_1$-completa: todos los $\Sigma_1$ declaración de que es verdadero en $\Bbb N$ es de hecho comprobable de $\sf PA$.

Ahora, si $\forall x\varphi(x)$ es $\Pi_1$ declaración de que no es ni demostrable ni disprovable de $\sf PA$, lo que significa que es necesariamente el caso de que $\exists x\lnot\varphi(x)$ es falso (en $\Bbb N$), de lo contrario, sería demostrable. Por lo tanto, $\forall x\varphi(x)$ es verdadero (en $\Bbb N$).

Answer 3

uno puede encontrar algunos no trivial universal cerrado frases (que comienza con un "para todos" cuantificador, todas las variables están enlazados) que puede ser demostrado ser improbable.

Específicamente, dada una lógica de $L_1$, usted puede construir (algoritmos) una declaración de $P(x)$ que no es una prueba de $P(0)$ y existe una prueba de $P(1)$ y existe una prueba de $P(2)$, etc, pero no hay ninguna prueba de $\forall k~P(k)$ (y de todos que supone la consistencia).

Hemos demostrado que no puede haber ningún contador de ejemplo de esta declaración

Hemos formalmente no lo demostró. No hay ninguna prueba formal en $L_1$ que $\lnot \exists k ~ \lnot P(k)$. Para mostrar $\lnot \exists k ~ \lnot P(k)$, en realidad debemos utilizar la suposición de que $P(k)$ representa la declaración de "$k \text{ is not a proof of } G$" (para una especialmente elegidas $G$). Pero esa suposición no es en realidad comprobable en $L_1$, es algo que sabemos que es verdad, porque fue diseñado de esa manera.

Mi conclusión es que cualquiera de Gödel estaba equivocado, o de las matemáticas son incompatibles

Gödel no estaba equivocado, ni es la lógica que el teorema de la trata. La lógica es algo incompleto. Y lo que es más importante, es incompletable.

Incluso si metalenguaje se mezcla con el lenguaje regular, no todo el metalenguaje utilizado aquí ser codificado en un primer orden de la lógica con la aritmética de Peano, y ver como no parte de una más fuerte de la teoría ?

Sí, y hay una enorme rama de la lógica que se ocupa de este enfoque. Se llama provability lógica: https://plato.stanford.edu/entries/logic-provability/ . Pero, incluso después de codificar todo el exterior de la lógica y la usa como su nueva lógica, entonces usted acaba de crear una nueva lógica de $L_2$, a partir de la cual un nuevo $P$ puede ser construido a través de algoritmos. No importa cómo mucho de la "meta" que mantenga la adición de un nuevo $P$ puede ser creado.

Sugiero la lectura a través de https://plato.stanford.edu/entries/goedel-incompleteness/ , es absolutamente fantástico de referencia para Gödel primer teorema de la incompletitud (pero lamentablemente deficientes de referencia para la segunda, que requiere un poco más de marco que en el artículo se presenta).

Answer 4

Unas declaraciones que no podía ser refutado por la presentación de un contraejemplo, ya que contraejemplo sería también un reclamo universal. Un contraejemplo a "todos los hombres son mortales" sería "nada puede matar a Bob". En matemáticas, sería más como, "para cualquier $x\in S$, hay algunos $y\in T$ tal que..."

Vamos a hablar de un ejemplo concreto. Escribe tu favorito entero positivo, como una suma de potencias de dos, donde los exponentes se escriben en el mismo formato, etc así que no hay ningún número $>2$ aparece, por ejemplo, $37$ hace $2^{2^2+1}+2^2+1$. Ahora vuelva a colocar todos los $2$ con $3$ y restar uno a saber. $3^{3^3+1}+3^3$. Ahora repita el movimiento $3$s a $4$s, viz. $4^{4^4+1}+3\times 4^3+3\times 4^2+3\times 4+3$. Los números crecen muy rápido al principio, pero se puede demostrar en ZF, una versión de la teoría de conjuntos, que con el tiempo llegarás a $0$. Por otro lado, también puede ser demostrado que los axiomas de Peano, los más débiles del sistema de Gödel considerado en sus teoremas de incompletitud, no se puede demostrar este resultado.

Answer 5

Lo que se puede demostrar, en PA (y de hecho, incluso más débil aritmética de las teorías que eso) a través de una cuidada versión del argumento que das es "Si PA es consistente, entonces hay una declaración de $G$ tal que $G$ sostiene y PA no puede probar la $G$." Si PA puede probar su propia consistencia, entonces podría resultar $G$ y PA que no puede probar, $G.$ por Lo tanto que el segundo es una declaración falsa y PA es falso. Por lo tanto, si PA es el sonido, entonces no puede probar su propia consistencia. Esto es esencialmente una prueba de (una forma débil de) el segundo teorema de la incompletitud de la primera.