Sea "Undec(x)" un predicado en aritmética de Peano que dice "x es el número de Gödel de una frase que no es demostrable ni refutable" Es fácil ver que este predicado es de hecho expresable en aritmética de Peano. Podemos seguir iterando este operador "Undec". Mi pregunta es, ¿puede alguien exhibir una fórmula específica F tal que F es verdadera, Undec(F) es verdadera, Undec(Undec(F)) es verdadera, Undec(Undec(F)) es verdadera, y así sucesivamente.
Respuesta
¿Demasiados anuncios?
Puede dejar que su $F$ sea cualquier sentencia indecidible por PA que resulta ser cierto. Esto es porque la AP, si es consistente, puede nunca demostrar cualquier afirmación de la forma $\mathsf{Undec}(\cdots)$ porque eso implicaría demostrar la consistencia de PA, lo que prohíbe el segundo teorema de incompletitud. Por lo tanto, cada uno de sus $\mathsf{Undec}(\cdots)$ ser verdadera implica la verdad de la siguiente.
Si no quieres apelar al segundo teorema de incompletitud, aquí tienes un argumento más pedestre que se limita a suponer que existe alguna sentencia indecidible (y suficientemente simple):
Será un poco menos confuso hablar en términos de decidible en lugar de "indecidible", por lo que $\newcommand{\D}{\mathop{\sf D}\nolimits} \D\phi$ significa la sentencia aritmética que afirma que PA demuestra o refuta $\phi$ . Entonces está buscando un $\psi$ tal que $\psi$ , $\D\psi$ , $\D\D\psi$ y demás son todos falso . (Aquí, "falso" y "verdadero" siempre significan falso y verdadero en los enteros estándar).
Afirmo que podemos tomar $\psi$ para ser cualquier indecidible $\Sigma^0_1$ y la negación de la sentencia habitual de Gödel para PA es exactamente una sentencia de este tipo.
Para demostrar que $\D^n\psi$ es falso para todos los $n\ge 0$ , proceda por inducción.
$\D^0\psi\equiv\psi$ es falsa porque todo verdadero $\Sigma^0_1$ es demostrable, y elegimos $\psi$ sea indecidible.
$\D^1\psi\equiv \D\psi$ es falso porque estamos asumiendo que $\psi$ es indecidible.
Para el paso de inducción, supongamos que para $n\ge 2$ que $\D^{n-1}\psi$ es falso, y supongamos para una contradicción que $\D^n\psi$ es cierto. Entonces, como $\D^{n-1}\psi$ es falso pero decidible debemos tener $$ \tag1 PA\vdash \neg\D^{n-1}\psi$$
Ahora, sin embargo, $\D^{n-2}\psi$ es un $\Sigma^0_1$ frase esto es por construcción para $n=2$ y, por otra parte, porque $\D\phi$ es siempre $\Sigma^0_1$ por cada $\phi$ . Es bien sabido que para cada $\Sigma^0_1$ sentencia $\varphi$ tenemos $PA\vdash \varphi\to[PA\vdash \varphi]$ Así que, en particular $$\tag 2 PA \vdash \D^{n-2} \psi \to \D^{n-1} \psi $$ y por razonamiento proposicional (1) y (2) se combinan para $$ PA \vdash \neg\D^{n-2} \psi $$ Pero esto implica que $\D^{n-1}\psi$ es verdadera, lo que contradice la hipótesis de inducción. Así que $\D^n\psi$ es falso, como se requiere.
(La idea que subyace a la prueba anterior está robada de esta respuesta de Timothy que me costó mucho tiempo entender por estar en prosa. Espero que el simbolismo aquí haga más fácil mantener los metaniveles).
