Declaración comprobable para todos los parámetros, pero no demostrable cuando cuantificado

Question

He estado leyendo un libro sobre Gödel los teoremas de la incompletitud y hace la siguiente aseveración con respecto a provability de declaraciones en la aritmética de Peano (parafraseado):

No existe una fórmula $A(x)$ de manera tal que las declaraciones $A(0), A(1), A(2), \dots$ son todos comprobable, sino $\forall x\, A(x)$ no es demostrable.

Va a decir que mientras Gödel primer teorema de la incompletitud garantiza su existencia, no es fácil encontrar una propiedad para una teoría tan fuerte como PA.

Hay un ejemplo específico de una fórmula o ninguno ha sido encontrado todavía?

Answer 1

Gran pregunta! Sí, hay ejemplos específicos. Uno de los más famosos es el teorema de Goodstein. Si $A(n)$ es la declaración de que Goodstein de la secuencia a partir de a $n$ termina, entonces se la conoce (a través de la más fuerte de las teorías de PA, a saber, el uso de un ingenioso ordinal argumento) que $\forall n \; A(n)$ es cierto.

Por otra parte, para un específico $n$, dado que el $A(n)$ es cierto, debe ser comprobable: acaba de escribir la secuencia finita, y que da una prueba de que se termina. (Una vez que llegue a $n = 4$ o más, va a ser muy muy larga de la prueba, que nosotros, los humanos, de hecho, no tienen memoria o espacio para escribir.)

Sin embargo, $\forall n \; A(n)$ es conocido por ser no demostrable en PA.

Answer 2

Posiblemente el ejemplo más fácil es dejar que $A(x)$ $x$ no es el número de Gödel de una prueba de $0=1$ a partir de los axiomas de la PA.

Porque no hay ninguna prueba de ello, $A(0)$ es verdadero, $A(1)$ es verdadero, etc., y debido a su forma sintáctica de cada uno de estos es demostrable en PA.

Sin embargo, $(\forall x)A(x)$ es la declaración de $\text{Con}(\text{PA})$ que el segundo teorema de la incompletitud muestra no es demostrable en PA.

Hay otros ejemplos, como bien. Algunos están relacionados con la París-Harrington y teorema de otras independencia de los resultados; otros se relacionan más directamente a los teoremas de la incompletitud.

Answer 3

Deje $\phi(x)$ ser la fórmula que expresa "x no es un código para una prueba de '0 = 1' a partir de los axiomas de $\textsf{PA}$".

Desde $\textsf{PA}$ no demuestra que no hay ninguna prueba de '0 = 1' (es decir, $\textsf{PA}$ no prueba que $\textsf{PA}$ es consistente), entonces no es el caso que $\textsf{PA}$ demuestra que no hay ningún código para dicha prueba. Pero como si hubiera una prueba, su código podría no ser estándar (de lo contrario, sería un código para una prueba real, lo que implicaría que $\textsf{PA}$ realidad demuestra que es incompatible), entonces sabemos que $\phi(0), \phi(1)$, etc todos tienen.

Answer 4

Si usted simular una Máquina de Turing mediante una Máquina de Turing Universal y ejecutar la simulación para N pasos, verás que se Detiene la máquina en N pasos o que la máquina no se Detiene en N pasos.

Sin embargo, en general, usted no puede probar que una Máquina de Turing se Detiene por mera simulación, porque si no detener la simulación iría para siempre. Creo que es el mismo pero con palabras diferentes.

Usted sabe la respuesta a la pregunta:

• ¿La máquina detener en N pasos? (Decideable)

Usted no sabe la respuesta a la pregunta:

• No se detiene la máquina en cualquier número de pasos? (Undecideable)

Usted podría utilizar como fórmula de una máquina que requiere la máquina de turing para llegar a un determinado estado. Sabe usted si el estado puede ser alcanzado en una cantidad limitada de pasos, pero no se si dejar que se ejecute siempre con ilimitada cantidad de memoria.