¿Por qué es $\omega$ -consistencia necesaria en la prueba original de Incompletitud de Gödel?

Question

No veo por qué la versión original del primer teorema de incompletitud de Gödel (antes de la mejora de Rosser, quiero decir) tenía que incluir la suposición de $\omega$ -consistencia para demostrar que $F \nvdash \neg G_F $ -- a diferencia de la otra dirección, $F \nvdash G_F $ En cualquier caso, a mi entender, basta con la coherencia.

¿Podría alguien señalar el fallo en el siguiente (incompleto) argumento?

(1) La relación de demostrabilidad para un sistema formal F es débilmente representable en F, es decir, un predicado $PRV_F$ existe s.t. $F \vdash A \Leftrightarrow F \vdash PRV_F(A)$

(2) Definimos la frase $G_F$ s.t. $F \vdash G_F \leftrightarrow \neg PRV_F(/G_{F}/)$

(3) Para mostrar: Si F es consistente, entonces $F \nvdash \neg G_F$ (segunda parte de Incompletitud I)

Supongamos que $F \vdash \neg G_F$ .

Entonces, por (2), $F \vdash \neg \neg PRV_F(G_F)$ Así que $F \vdash PRV_F(G_F)$ .

Entonces, por (1), $F \vdash G_F$ por lo que F es inconsistente (y $\omega$ -inconsistente como resultado también) de la suposición de que $F \vdash \neg G_F$ .

Answer 1

El problema ya está presente en el paso 1. La consistencia no es una suposición lo suficientemente fuerte en la teoría para garantizar que la relación de demostrabilidad es representable.

Por ejemplo, si $T$ se toma como $\text{PA} + \lnot\text{Con}(PA)$ que no es $\omega$ -consistente, entonces tenemos $T \vdash \text{Pvbl}_T(\phi)$ para todos $\phi$ pero $T$ es consistente, por lo que para muchos $\phi$ también tenemos $T \not \vdash \phi$ . Por lo tanto, no tenemos todo el esquema $T \vdash \phi \Leftrightarrow T \vdash \text{Pvbl}_T(\phi)$ como se afirma en (1).

La fuente de confusión puede ser que parece que estás cuantificando sobre predicados cuando escribes "un predicado $PRV_F$ existe s.t. $F \vdash A \Leftrightarrow F \vdash PRV_F(A)$ ". De hecho, construimos un predicado específico $\text{Pvbl}$ para derivar el esquema (1) de la pregunta.

Para demostrar que $T \vdash A$ implica $T \vdash \text{Pvbl}(A)$ que es parte de la demostración de que $\text{Pvbl}$ representa la relación de demostrabilidad, nos basamos en $\text{Pvbl}$ siendo el predicado de demostrabilidad real, por lo que podemos transformar cualquier derivación de $A$ en una derivación de $\text{Pvbl}(A)$ .

Del mismo modo, al demostrar que $T \vdash \text{Pvbl}(A)$ implica $T \vdash A$ utilizamos el $\omega$ -consistencia de $T$ para saber que, si $T \vdash \text{Pvbl}(A)$ entonces hay realmente un número natural $n$ que codifica una derivación de $A$ de $T$ .

Puede que estés pensando en resultados generales que muestran que ciertas teorías son capaces de representar todo conjunto computable, o de representar débilmente todo conjunto r.e. Es cierto que la representabilidad de la relación de demostrabilidad se desprende de estos resultados generales. Pero las pruebas de estos resultados generales también suponen que la teoría es $\omega$ -consistente, o al menos $1$ -consistente, no sólo que la teoría sea consistente.

Answer 2

Como yo también he tenido algunos problemas con este tema, me gustaría compartir mis ideas al respecto.

Obsérvese que utilizo $\color{red}{red}$ siempre que las cosas así denotadas sean sintácticas. Esta fue (y sigue siendo) para mí siempre la clave para tener las cosas claras: ¿en qué "mundo" están estos objetos en los que estoy pensando?

1. Se trata de dos predicados diferentes:

En primer lugar se construye el prueba -predicado $Pr_F(x,y)$ en el mundo recursivo que establece que $x$ codifica una prueba (en $F$ con el Cálculo de Hilbert) para la fórmula que está codificada por $y$ . Esto es fuertemente representable en $F$ Por lo tanto, hay un fórmula $\color{red}{Pr_F}$ tal que:

$$\begin{align}Pr_F(x,y) &\Leftrightarrow F\vdash \color{red}{Pr_F(\overline{x},\overline{y})}\\\neg Pr_F(x,y)&\Leftrightarrow F \vdash\color{red}{\neg Pr_F(\overline x,\overline y)}\end{align}$$

Ahora, lo que nos interesa es más: queremos decir que alguna fórmula es demostrable, es decir, que existe una prueba. Por lo tanto, segundo definimos el comprobable -predicado en el mundo lingüístico de primer orden :

$$\color{red}{P_F(y)\leftrightarrow\exists x . Pr_F(x,y)}$$

Ahora bien, lo que has afirmado en (1) es válido para $Pr_F$ pero no tiene sentido afirmar tal propiedad para $\color{red}{P_F}$ ya que se trata de una fórmula, pero no de un predicado recursivo primitivo. Más aún: si quisiéramos definirlo como un predicado recursivo primitivo (al principio, para luego llevarlo por medio de la representabilidad al mundo sintáctico), no podríamos, ¡ya que hay un cuantificador no ligado involucrado!

2. Estos predicados no son equivalentes en $F$

Lo que tenemos ahora es lo siguiente:

$$\begin{align} F \vdash \color{red}\phi &\Longleftrightarrow \text{exists closed term $\color{red}{t}$, such that }F\vdash\color{red}{Pr_F(t,\ulcorner\phi\urcorner)}\\&\Longrightarrow F\vdash\color{red}{P_F(\ulcorner\phi\urcorner)}\end{align}$$

pero la otra dirección no tiene por qué mantenerse. Lo puedes ver claramente aquí, lo que necesitaríamos es un término cerrado $\color{red}t$ .

Considere la siguiente nota: Los cuantificadores abarcan el universo de agujeros, pero no todos los elementos del universo deben ser expresables dentro del lenguaje dado. (Si encuentras algo de tiempo, hay ejemplos bastante sencillos que podrías construir. El más obvio es, por supuesto, el lenguaje con un símbolo constante, etc.)

Ahora, $\omega$ -la consistencia al rescate nos lleva a la $\color{red}t$ .

3. Una nota histórica

Aunque la prueba original de Gödel suponía $\omega$ -consistencia ya tuvo su efecto en la comunidad. Así que no hay que sobrevalorarla, es más bien una pequeña mancha.