Límite inferior en la prueba de longitud

Question

Dado cualquier entero positivo $n$, hay una manera de construir rápidamente una declaración de $S$, de tal manera que la menor prueba de $S$, si es que existe, deben tener una longitud de, al menos,$n$?

Y de tal manera que uno de $S$ o no $S$, es demostrable.

---

Y la pregunta 2:
Si S, entonces una prueba de S debe tener la longitud de al menos n.
Si no, entonces una prueba de que no S debe tener la longitud de al menos n.

Editar:

Yo tenía en mente que el número de símbolos en S ser del mismo orden que el número de símbolos necesarios para especificar n.

Answer 1

Hay un famoso ejemplo que creo que es debido a Gödel. Es análogo a la llamada "Gödel frase" $G$, lo que puede ser interpretado como "$G$ no tiene ninguna prueba en PA", y que por lo tanto es cierto, pero no es demostrable en PA. (Suponiendo que la PA es consistente.)

El ejemplo análogo es una frase $S$ cuya interpretación es

$S$ no puede ser probado en el PA en menos de un millón de pasos.

Supongamos $S$ es falso. A continuación, $S$ puede ser demostrado en PA (en menos de un millón de pasos) y por lo tanto PA es inconsistente.

Supongamos $S$ es cierto. A continuación, $S$ no puede ser probado en el PA en menos de un millón de pasos.

Así que la suposición de que la PA es consistente nos lleva a la conclusión de que $S$ es improbable, o comprobable, pero no en menos de un millón de pasos.

Pero no es una prueba de $S$: enumerar todas las pruebas de hasta un millón de pasos, y comprobar cada una para asegurarse de que no se demuestra $S$. (Esta prueba se lleva mucho más de un millón de pasos.) Por lo $S$ es a la vez verdadera y comprobable, y la menor prueba se requiere de al menos un millón de pasos.

Ajá, veo que esto es discutido en la Wikipedia.