¿Son demostrables todas las propiedades de los números enteros?

Question

He estado investigando sobre la demostrabilidad de las propiedades, y me he encontrado con un argumento interesante que afirma que todas las propiedades de los números enteros son demostrables, pero ¿no nos dice el teorema de incompletitud que esto es falso? La prueba es:

Dejemos que $P(n)$ sea una propiedad de los números enteros. Supongamos que ( $\forall n:P(n)$ ) es indemostrable, por lo que es imposible demostrar su falsedad. Esto significa que es imposible dar un contraejemplo, y por tanto no existe tal contraejemplo. Dado que no existe ningún contraejemplo, la afirmación debe ser verdadera y, por lo tanto, es demostrable (acabamos de demostrarla), lo cual es una contradicción.

¿No significaría esto que todas las propiedades de los números enteros son demostrables?

Answer 1

No. La prueba contiene todo tipo de maldades. En cualquier definición particularmente útil de "demostrable" (es decir, demostrable por un sistema consistente con un conjunto recursivamente enumerable de axiomas), el teorema de Godel se cumple. El hecho de que la prueba no aborde exactamente lo que quiere decir con "demostrable" es otra cuestión totalmente distinta, y algo peor es que no diga lo que quiere decir con "propiedad".

Permítanme abordar dos cuestiones. La primera es que lo que esta prueba realmente afirma es:

Si $P(n)$ es indemostrable, entonces $P(n)$ es verdadero .

Sin embargo, para ampliarlo a $P(n)$ es comprobable tendríamos que demostrar que $P(n)$ es indemostrable, no sólo lo tome como una suposición. Esta prueba no supone que podamos demostrar $P(n)$ es indemostrable - simplemente que lo es. Si no podemos demostrar $P(n)$ es indemostrable, entonces no podemos demostrar que es verdadera por la lógica de la prueba. En realidad, es una consecuencia necesaria del teorema de Godel que hay enunciados que son indemostrables ( ver aquí ). La prueba no hace nada para arreglar este agujero.

Un problema mucho peor es que la prueba asume que es "fácil" verificar cualquier contraejemplo. La prueba está introduciendo otra suposición al pensar que un contraejemplo sería demostrable - en realidad, la afirmación que demuestra lo es:

Si $P(n)$ es indemostrable, pero se podría construir una prueba de $\neg P(n)$ para cualquier contraejemplo $n$ entonces $P(n)$ es cierto.

Podríamos considerar algo así como la negación del Último Teorema de Fermat - en particular dejemos que $P(n)$ sea la afirmación de que existen soluciones para $x^{n}+y^n=z^n$ . Para demostrar $P(n)$ era falsa para algunos $n$ En este caso, tendríamos que demostrar que no hay soluciones, y no hay ninguna fórmula para hacerlo. Claro, podemos salirnos con la suya estableciendo $P(n)$ a afirmaciones como "esta máquina de Turing se detiene en $n$ pasos", donde podemos ejecutarlo para $n$ pasos para verificar o refutar la afirmación (es decir, una prueba de $\neg P(n)$ existe si es cierto), pero esto está lejos de chaque declaración que podría interesarnos.

Answer 2

Una de las muchas buenas estrategias para entender lo que ocurre en una demostración (ya sea una buena o una mala demostración) es repasarla con un ejemplo. Sabes que el teorema de incompletitud debe proporcionar ejemplos de propiedades $P(n)$ tal que $\forall n : P(n)$ es indemostrable, así que elijamos una. El ejemplo que usaré es que $P(n)$ afirma que $n$ no codifica una prueba de una contradicción en la aritmética de Peano (PA).

Así que $\forall n : P(n)$ afirma que PA es consistente, y por el teorema de incompletitud, sabemos que PA no puede demostrar esta afirmación a menos que ella misma sea inconsistente. Así que veamos qué ocurre cuando pasamos este ejemplo por la prueba. El problema está aquí:

Como no existe ningún contraejemplo, la afirmación debe ser verdadera, y por lo tanto es demostrable

¡No! Parte de la lección de todo este asunto de la incompletitud es que puede haber afirmaciones que son verdaderas pero indemostrables, como la consistencia de PA (¡suponiendo que sea verdadera!).

(lo acabamos de probar)

No lo probamos ¡en PA! Cuando se dice que un enunciado es indemostrable, se quiere decir indemostrable con respecto a algún sistema de axiomas fijo, que aquí es PA. Esta prueba no es una prueba en ese sistema de axiomas. En cambio, es una prueba en una "metateoría" que estamos utilizando para analizar las propiedades de los sistemas de axiomas como PA.

Además, suponiendo que $\forall n : P(n)$ es indemostrable equivale a suponer que PA es consistente, y como sabemos, PA no puede demostrarlo.

Answer 3

Esto es cierto para ciertos tipos de expresión $P$ pero de ninguna manera todos.

Por ejemplo, si la declaración es de la forma $\exists m>n(Q(m,n))$ Entonces puede que no haya un ejemplo.

Y si esto $P$ es cierto, todavía podría no ser demostrable porque se puede encontrar, para cada $n$ un valor $m$ por ensayo y error, pero no se puede demostrar con una prueba finita. De hecho, éste es uno de los límites de la prueba: la finitud. Por ejemplo, la conjetura de Collatz podría ser cierta, pero no podría demostrarse con un número finito de pasos.

¿Cómo demuestras que tienes un contraejemplo de la conjetura de Collatz? Puede que no sea posible.

Answer 4

Creo que se trata de un contraejemplo sencillo: todo número entero representa una máquina de Turing y "se detiene" es una propiedad.

Así que si entiendo bien lo que quieres decir con demostrar y propiedad, secretamente estás tratando de resolver el problema de detención. Así que, de hecho, hay una propiedad que no sólo es indemostrable sino, peor aún, indecidible.