La versión de Rosser:En 1936 John B. Rosser modificó la demostración de Gödel para que valiera para un sistema consistente, en lugar de un sistema omega-consistente. Veamos cómo lo hizo (para abreviar, esta vez omitiré algunos tecnicismos).
Definamos la función neg(x) del siguiente modo: neg(x) es la concatenación del código de "-" (símbolo de negación) con x. Si n es el código de una fórmula P entonces neg(n) es el código de -P. Es claro que neg es expresable.
Definamos P(z) como:
\( \forall{u}(Dem(u,z)\Rightarrow{\exists{w}(Dem(w,neg(z))\wedge w\leq{u})}) \)
Como antes, definimos Q(x) como:
\( \forall{z}(z=d(x)\Rightarrow{P(z)}) \)
Sea n = cód(Q(x)), luego \( d(n) = c\'od(Q[\overline{n}]) \).
Llamemos m = d(n).
Igual que hicimos antes, se prueba que \( Q[\overline{n}] \) es equivalente a \( P(x/\overline{m}) \).
Llamemos R al enunciado \( P(x/\overline{m}) \), es decir R es:
\( \forall{u}(Dem(u,\overline{m})\Rightarrow{\exists{w}(Dem(w,neg(\overline{m}))\wedge w\leq{u})}) \)
Podemos traducir a R como: "dada cualquier demostración de \( Q[\overline{n}] \) (que es un enunciado equivalente al propio R) existe una demostración de \( -Q[\overline{n}] \) que tiene un código menor que la demostración dada".
Más fácil: dada cualquier demostración de \( Q[\overline{n}] \) existe una demostración más corta de su negación.
Suponiendo que el sistema de axiomas es consistente, vamos a probar que ni R ni -R es demostrable.
Si R es demostrable, sea k el código de una demostración de k. Entonces \( Dem(\overline{k},\overline{m}) \) es un enunciado finitario verdadero y, por ende, demostrable.
Como R es demostrable, por aplicación del esquema lógico que permite reemplazar la variable u por el término \( \overline{k} \) tenemos que:
\( Dem(\overline{k},\overline{m})\Rightarrow{\exists{w}(Dem(w,neg(\overline{m}))\wedge w\leq{\overline{k}})}) \) es demostrable.
Por aplicación de la regla de modus ponens:
\( \exists{w}(Dem(w,neg(\overline{m}))\wedge w\leq{\overline{k}}) \) es demostrable.
Este último enunciado equivale a:
\( Dem(0,neg(\overline{m}))\vee Dem(\overline{1},neg(\overline{m}))\vee \ldots \vee Dem(\overline{k},neg(\overline{m})) \), que es también demostrable. Llamémoslo T.
Ahora bien, como el sistema es consistente entonces -R no es demostrable. Luego, \( -Dem(0,neg(\overline{m})) \), \( -Dem(\overline{1},neg(\overline{m})) \), \( -Dem(\overline{2},neg(\overline{m})) \),... son todos enunciados finitarios verdaderos y en consecuencia demostrables.
En consecuencia: \( -Dem(0,neg(\overline{m}))\wedge -Dem(\overline{1},neg(\overline{m}))\wedge \ldots \wedge -Dem(\overline{k},neg(\overline{m})) \) es un enunciado finitista verdadero y demostrable. Pero este enunciado es la negación de T, luego el sistema no sería consistente. Por lo tanto, R no puede ser demostrable.
(Al agregar el inciso \( w\leq{\overline{k}} \) al existencial \( \exists{w}Dem(w,neg(\overline{m})) \) el enunciado se vuelve equivalente a la disyunción de una cantidad finita de enunciados y es por eso que ya no es necesaria la hipótesis de la omega-consistencia.)
Falta ver que -R no es demostrable. Supongamos que sí lo fuera y sea k el código de una demostración de -R.
Entonces \( Dem(\overline{k},neg(\overline{m})) \) es demostrable.
Luego,\( \exists{w}Dem(w,neg(\overline{m})) \) es demostrable.
Luego, \( \overline{k}\leq u\Rightarrow (\exists{w}Dem(w,neg(\overline{m}))) \) es demostrable y también es demostrable \( \overline{k}\leq u\Rightarrow \exists{w}(w\leq u) \).
En consecuencia, \( \overline{k}\leq u\Rightarrow (\exists{w}(Dem(w,neg(\overline{m}\wedge w\leq u)))) \) es demostrable.
Por otra parte, por la consistencia del sistema, R no es demostrable. De ello puede deducirse que:
\( u\leq \overline{k}\Rightarrow -Dem(u,\overline{m}) \) es demostrable.
Finalmente, entre las hipótesis de la versión de Rosser del teorema habíamos supuesto que \( \overline{k}\leq u\vee u\leq \overline{k} \) es demostrable. Se deduce así que:
\( -Dem(u,\overline{m})\vee \exists{w}(Dem(w,neg(\overline{m}\wedge w\leq u))) \)
es demostrable. Pero este enunciado es sintácticamente equivalente a R. Luego R sería demostrable, lo que contradice la hipótesis de la consistencia del sistema. Concluimos así que -R no es demostrable. Una vez más, Q.E.D.
Como antes, si el sistema es consistente, R es un enunciado verdadero y no demostrable. Pero si el sistema no es consistente entonces R es falso y demostrable.