George Boolos y Gödel ' s segundo Teorema de incompletitud

Question

En La Mente, Vol. 103, enero de 1994, pp 1-3, George Boolos escribió:

Y así sucesivamente. De hecho, si una reclamación puede ser demostrado, entonces se puede demostrar que la demanda puede ser demostrado. Y eso también puede ser demostrado.

Ahora, dos más dos no son cinco. Y se puede demostrar que dos más dos no es de cinco años. Y se puede demostrar que se puede demostrar que dos más dos no son cinco, y así sucesivamente.

Por lo tanto: se puede demostrar que dos más dos no son cinco. Puede probarse así que dos más dos son cinco? Sería un verdadero golpe a las matemáticas, a decir lo menos, si pudiera. Si se podía demostrar que dos más dos es cinco, luego se pudo comprobar que los cinco no son cinco, y luego hay no sería la afirmación de que no podía ser demostrado, y matemáticas sería un montón de litera.

Así que, ahora queremos preguntar, ¿puede probarse que no puede ser comprobado de que dos más dos es cinco? Aquí está el shock: no, no puede. O, para cobertura un poco: si se puede demostrar que no puede ser comprobado de que dos más dos es cinco, entonces puede ser probado, así que dos más dos es cinco, y las matemáticas son un montón de patrañas. De hecho, si las matemáticas no es un montón de literas, entonces ninguna reclamación de la forma "reclamo X no puede ser comprobado" que puede ser probada.

...y...

...sí, se puede demostrar que si se puede demostrar que no puede ser comprobado de que dos más dos es cinco, entonces se puede demostrar que dos más dos son cinco. [es decir, lo que se afirmó anteriormente puede ser probado]

[parentheticals agregado por mí]

Por favor, disculpe la potencialmente ignorante preguntas:

1. ¿Por qué probar que dos más dos son cuatro, no se constituyen como una prueba de que dos más dos puede ser igual a cinco (por lo tanto no puede ser probada como tal)?
2. Debo entender que la única manera de probar que no se puede demostrar que dos más dos no pueden hacer cinco es demostrar que el sistema de trabajo es constante, y que no hay otra manera? (Si es así, ¿cuál es la prueba de que no hay otra manera?)

Answer 1

Mientras que $2+2=4$ parece un objetivo fácil para una forma de demostrar $2+2\neq 5$, se está suponiendo implícitamente que el $4\neq 5$ y $4=5$ no puede ser probado. Pero si la aritmética es incoherente, puede demostrar que $4=5$, en cuyo caso $2+2=5$.

Lo que indica que $2+2=5$ no es comprobable, es una manera de decir que el $0=1$ no es demostrable. Pero ahora recuerdo que la formulación estándar de $\operatorname{Con}(T)$ " $T$ no demuestran $0=1$".

A su segunda pregunta, la respuesta es más sutil que eso. Usted necesidad de asumir que el sistema trabaja en es consistente, pero es por eso que tenemos una meta-teoría. La teoría de conjuntos demuestra que la aritmética es consistente, por lo que el trabajo dentro de la teoría de conjuntos se puede demostrar que $2+2=5$ no es demostrable a partir de los axiomas de la aritmética. Por supuesto, ahora es posible que desee pedir, podría teoría de conjuntos probar que $2+2=5$ es imposible? Y Gödel snarks en la esquina y dice: "inténtalo de nuevo". Así que usted tiene que mover a una más fuerte de la teoría, y así sucesivamente y así sucesivamente.

Es de las tortugas todo el camino hacia abajo.

Answer 2

¿Por qué probar que dos más dos son cuatro, no se constituyen como una prueba de que dos más dos puede ser igual a cinco (por lo tanto no puede ser probada como tal)?

Una prueba de que $2+2=4$ hace, de hecho, constituyen una prueba de que $2+2\neq 5$ (asumiendo que usted también puede demostrar que $4\neq 5$, que, presumiblemente, su sistema de matemáticas es lo suficientemente fuerte como para hacer). El problema está en su final entre paréntesis. Sólo porque podemos demostrar que $2+2\neq 5$ no significa que no haya prueba de $2+2=5$ existe. Tal vez existen pruebas de declaraciones falsas!

Debo entender que la única manera de probar que no se puede demostrar que dos más dos no pueden hacer cinco es demostrar que el sistema de trabajo es constante, y que no hay otra manera? (Si es así, ¿cuál es la prueba de que no hay otra manera?)

Bueno, no es tanto que no hay otro camino, sino que las dos afirmaciones son básicamente idénticos. Si el sistema en el que trabajamos fueron inconsistentes, entonces se podría probar de todo, ya nada se sigue de una contradicción. Así que si podemos demostrar que nuestro sistema no puede probar la $2+2=5$ (o cualquier otro tipo de declaración), que en sí mismo de inmediato demostrar que nuestro sistema es consistente. Por el contrario, si se demuestra que nuestro sistema es consistente, entonces llegamos a la conclusión de que no puede demostrar que $2+2=5$ (ya que, si podía, nuestro sistema resultaría una contradicción ya que también podemos probar que nuestro sistema de prueba $2+2\neq 5$). Para demostrar que nuestro sistema no puede probar la $2+2= 5$ es esencialmente la misma cosa como la demostración de que nuestro sistema es consistente.

Answer 3

1. A partir de una prueba de $2 + 2 = 4$ sigue una prueba de $2 + 2 \neq 5$, pero de ello no se sigue que el sistema no puede probar la $2 + 2 = 5$ debido a que si el sistema no es consistente, entonces el sistema puede demostrar todo de acuerdo con el principio de la explosión, en particular, para cada declaración de $A$ el sistema puede demostrar $A$ y su negación $\lnot A$.

2. Como consecuencia, la única manera de estar seguro de que $2 + 2 = 5$ no puede ser probado en el sistema es el hecho de que el sistema es consistente. De acuerdo con el principio de explosión, para demostrar$-$en la meta-teoría de la$-$que el sistema es consistente es suficiente para mostrar que no es una fórmula que el sistema no puede demostrar.

Gödel del segundo teorema de la incompletitud afirma que para cualquier constante y computable sistema axiomático $S$ que es lo suficientemente potente como para describir la aritmética de los números naturales (por ejemplo, los axiomas de Peano o de Zermelo–Fraenkel de la teoría de conjuntos con el axioma de elección), la consistencia de $S$ no puede ser probada dentro de $S$ sí. Esto significa que:

• en $S$ es posible canónicamente definir una fórmula $Cons(S)$ expresan que la consistencia de la $S$; normalmente, $Cons(S)$ indica "no hay ningún número natural que los códigos de una derivación de '$0=1$'$S$";

• $S \not\vdash Cons(S)$, es decir, no hay ninguna derivación de $Cons(S)$$S$; esto es suficiente para probar que el $S$ es consistente en la meta-teoría, pero significa que usted no puede probar la consistencia de $S$ dentro $S$.

Por supuesto, usted puede probar la consistencia de $S$ en un sistema más fuerte $S'$ contiene $S$, pero si $S'$ es consistente, entonces usted no puede probar la consistencia de $S'$ dentro $S'$ (o dentro de $S$).