[Cristian C]

Tengo una duda concreta acerca de la expresabilidad de relaciones en teorías aritméticas que me surge de la lectura de "Lógica y Teoría de Conjuntos" de Carlos Ivorra. La anoto aquí para valerme del latex como ya le he comentado a Carlos por mail.
Obviamente, cualquiera puede participar, pero haré referencia a los pasajes donde  el tema está formalizado en el citado libro.

Copio de la página 164 (con leves modificaciones en la redacción):

Definición 6.3
Dada una teoría aritmética T, diremos que una relación R n-ádica (sobre números naturales) es expresable en T si y solo si existe una fórmula aritmética \( \alpha(y_{1},\ldots,y_{n}) \), cuyas variables libres sean a lo sumo \( y_1,\ldots , y_n \) tal que para todos los naturales \( a_1,\ldots ,a_n \) se cumple:

Si \( R(a_{1},\ldots,a_{n}) \) entonces \( \underset{T}{\vdash}\alpha(a_{1},\ldots\,,a_{n}) \)
y
Si \( \textsf{no } R(a_{1},\ldots,a_{n}) \) entonces \( \underset{T}{\vdash}\neg\alpha(a_{1},\ldots\,,a_{n}) \)

De aquí surge que, dada una teoría aritmética T, una relación n-ádica
R (sobre números naturales) no es recursiva en T si y solo si para
toda fórmula n-ádica \( \alpha(y_{1},\ldots,y_{n}) \) con variables libres
a lo sumo \( y_{1},\ldots,y_{n} \) existen naturales \( a_{1},\ldots,a_{n} \)
tales que no se cumple:

Si \( R(a_{1},\ldots,a_{n}) \) entonces \( \underset{T}{\vdash}\alpha(a_{1},\ldots\,,a_{n}) \)
y
Si \( \textsf{no } R(a_{1},\ldots,a_{n}) \) entonces \( \underset{T}{\vdash}\neg\alpha(a_{1},\ldots\,,a_{n}) \)


Para abreviar anoto \( R \) y \( \alpha \) sin los argumentos, omito subindicar
\( T \) y reescribo la estructura lógica así:

Para todo \( \alpha \) con variables libres a lo sumo \( y_{1},\ldots,y_{n} \)
existen naturales \( a_{1},\ldots,a_{n} \) tales que:

no ((\( R \) entonces \( \vdash\alpha \)) y (no \( R \) entonces \( \vdash\neg\alpha \)))

Luego calculo

no (no \( R \) o \( \vdash\alpha \)) o no (\( R \) o \( \vdash\neg\alpha \))

(\( R \) y no \( \vdash\alpha \)) o (no \( R \) y no \( \vdash\neg\alpha \))

(\( R \) o no \( R \)) y (\( R \) o no \( \vdash\neg\alpha \)) y (no \( \vdash\alpha \)
o no \( R \)) y (no \( \vdash\alpha \) o no \( \vdash\neg\alpha \))

Entonces, de la última disyunción de la conjunción se sigue

no (\( \vdash\alpha \) y \( \vdash\neg\alpha \))

Restituyendo argumentos y subíndices

no (\( \underset{T}{\vdash}\alpha(a_{1},\ldots,a_{n}) \) y \( \underset{T}{\vdash}\neg\alpha(a_{1},\ldots,a_{n}) \))

Resumiendo, hemos obtenido que si \( R \) no es expresable en \( T \) entonces
para toda fórmula \( \alpha \) con variables libres a lo sumo \( y_{1},\ldots,y_{n} \)
existen naturales \( a_{1},\ldots,a_{n} \) tales que

no (\( \underset{T}{\vdash}\alpha(a_{1},\ldots,a_{n}) \) y \( \underset{T}{\vdash}\neg\alpha(a_{1},\ldots,a_{n}) \))

Esto es, hay al menos un enunciado que no es demostrable y refutable.
Entonces \( T \) es consistente.

Esto prueba que dada una teoría aritmética \( T \), si una relación \( R \)
(acerca de naturales) no es expresable en \( T \) entonces \( T \) es consistente.(1)

Ahora tenemos el siguiente teorema (Ivorra lo deja como ejercicio
en pag. 173):

Si una relación \( R \) es expresable en una teoría aritmética \( T \),
entonces \( R \) es recursiva.

Cuyo contrarecíproco es:

Si una relación \( R \) no es recursiva entonces para toda teoría aritmética
\( T \), \( R \) no es expresable en \( T \)

y luego por (1)

Si una relación \( R \) no es recursiva entonces para toda teoría aritmética
\( T \), \( T \) es consistente.

¿Está bien esto?

Entiendo allí que si existe una relación no recursiva (acerca de naturales)
entonces todas las teorías aritméticas son consistentes. Y si existiera
una inconsistente, no habría relaciones no recursivas.

¿Es esto así?

[Carlos Ivorra]

Hola, Cristian.

No hace falta dar tantas vueltas: si T es una teoría contradictoria, en ella se puede demostrar cualquier cosa, y eso hace que la definición de representabilidad se cumpla trivialmente, luego toda relación es representable en toda teoría contradictoria y, por lo tanto, si una relación no se puede representar en una teoría, es que es consistente.

Eso no es más extraño que el hecho de que si existe una fórmula que no puede demostrarse en una teoría, es que es consistente.

Lo que pasa es que en el ejercicio que citas hace falta la hipótesis de que la teoría sea consistente (que acabo de añadir). De hecho, también hace falta la hipótesis de que la teoría sea recursiva (la cual ya estaba en mi libro antes de que añadiera la hipótesis de consistencia que faltaba, pero tú la has omitido, y también es necesaria).

La idea de la prueba es la siguiente: si una relación R está representada por una fórmula \( \alpha \) en una teoría aritmética recursiva y consistente T, tienes un procedimiento práctico para saber si R se cumple o no en unos números dados, \( n_1,\ldots, n_r \): sólo tienes que ir enumerando los teoremas de T y esperar a ver si te aparece una demostración de \( \alpha(0^{(n_1)},\ldots, 0^{(n_r)}) \) o bien una de \( \lnot\alpha(0^{(n_1)},\ldots, 0^{(n_r})) \).

Como la relación está representada por \( \alpha \) te ha de aparecer una de las dos, y como la teoría es consistente no te pueden aparecer las dos, luego en cuanto encuentres una de ambas, ya puedes saber, según cuál sea, si la relación se cumple o no.

Naturalmente, puedes dar una prueba que no involucre la tesis de Church-Turing probando que R equivale a una relación recursiva definida en términos de las relaciones recursivas asociadas a las teorías aritméticas (la relación que dice que la sustitución en \( \alpha \) de unos numerales dados es demostrable en T).

[Cristian C]

Clarísimo Carlos.

Tus últimos párrafos también me disipan otras dudas porque eso que razonas allí, ya lo había razonado yo en otras exploraciones, pero sin saber si estaba siendo lo suficientemente riguroso.
Obviamente, la tesis de Crunch es muy cómoda para la intuición.

Saludos y Gracias.

Pdta: Creo que reservaré este hilo para otras dudas que me pudieran surgir sobre estos temas fascinantes.

[Carlos Ivorra]

Pdta: Creo que reservaré este hilo para otras dudas que me pudieran surgir sobre estos temas fascinantes.

Sí, claro. Puedes preguntar lo que quieras cuando quieras.

[Cristian C]

Hola Carlos:

He abandonado por ahora el estudio de las versiones conjuntistas de los teoremas de Gödel porque aún debo terminar de aclararme algunas ideas respecto a la presentación general. Concretamente respecto a teorías aritméticas no recursivas.

La relación \( Dem(x)\equiv\exists y\: Dm(y,x) \) es no recursiva y sin embargo puede designarse con una fórmula del lenguaje.
En lo que sigue, diré que una relación es designable si es la interpretación natural de alguna fórmula del lenguaje. Evidentemente, una relación puede ser no recursiva y designable, como en el ejemplo.
Diré que una teoría aritmética es designable si la relación \( Ax(x) \) que define los códigos de sus axiomas es designable.
Me queda por ver qué puede significar que una relación sea no designable. No abordo ese tema ahora.

A continuación van dos teoremas. El primero es una extensión del 2° teorema de incompletitud extendido al caso de teorías aritméticas designables (recursivas o no) y el segundo se sigue del primero, y he visto después que tal vez, podría haberse derivado del teorema de Tarski.

Nada asegura que todo esto esté bien, ni que sea claro ni que las pruebas sean suficientes. Te pido pues, que lo revises, si tienes ganas. Si hay algún error, me serviría mucho saber cuál es para seguir acomodando estas ideas en mi cabeza.


Teorema 1

Si \( T \) es una teoría aritmética designable, entonces
\( \underset{T}{\vdash}consis(T) \) ssys \( T \) es contradictoria.

(Observemos que si \( T \) es no designable, entonces \( consis(T) \) no se puede definir, y la tesis carece de sentido).

Demostración:
Si \( T \) es contradictoria entonces todo es demostrable en \( T \) y en
particular \( \underset{T}{\vdash}consis(T) \) .

Si \( \underset{T}{\vdash}consis(T) \) sea \( d \) el código de una demostración de \( consis(T) \) en \( T \), sean \( a_{1},\ldots\,,a_{n} \) los axiomas de \( T \) presentes en \( d \) y sea \( T^{*} \) la teoría que resulta de agregarle \( a_{1},\ldots\,,a_{n} \) a los axiomas de Peano. Entonces se tiene que \( T^{*} \) es una teoría aritmética recursiva y además \( d \) es una demostración de \( consis(T) \) en \( T^{*} \) , esto es,

\( \underset{T^{*}}{\vdash}consis(T) \)   (1).

Ahora veremos que si \( \underset{T^{*}}{\vdash}consis(T) \) entonces \( \underset{T^{*}}{\vdash}consis(T^{*}) \)

Sean \( Ax_{T^{*}}(x) \) y \( Ax_{T}(x) \) las fórmulas definidoras de los códigos de los axiomas de \( T^{*} \) y \( T \) respectivamente.
Ahora observemos que el hecho de que \( T \) sea no recursiva, implica que no para todo natural \( n \) se tiene que si \( Ax_{T}(n) \) entonces \( \underset{T}{\vdash}Ax_{T}(0^{(n)}) \), pero podrían existir algunos naturales donde esa condición sí se verifique. Eso es lo que ocurre con los naturales \( a_{1},\ldots\,,a_{n} \), ya que si \( d \) es una demostración en \( T \) y \( a_{1},\ldots\,,a_{n} \) son los axiomas de \( T \) presentes en \( d \), entonces las afirmaciónes \( Ax_{T}(a_{i}) \) son finitamente verificables y las sentencias \( Ax_{T}(0^{(a_{i})}) \) son demostrables en \( \mathcal{P} \), esto es, \( \underset{\mathcal{P}}{\vdash}Ax_{T}(0^{(a_{i})}) \), con \( 0<i\leq n \). Lo mismo ocurre con los axiomas de Peano, ya que si \( T \) es una teoría aritmética, debe poder verificarse en un número finito de pasos que los axiomas de Peano son axiomas de \( T \) (o teoremas demostrables a partir de axiomas de \( T \) finitamente verificables). Pero entonces, para todos los axiomas de \( T^{*} \), la implicación “si \( n \) es un axioma de \( T^{*} \) entonces \( n \) es un axioma de \( T \)” puede verificarse en un número finito de pasos, entonces es demostrable en \( \mathcal{P} \), esto es:

\( \underset{\mathcal{P}}{\vdash}\forall x\:(Ax_{T^{*}}(x)\rightarrow Ax_{T}(x)) \)

De donde se sigue que

\( \underset{\mathcal{P}}{\vdash}\forall xy\:(Dm_{T^{*}}(y,x)\rightarrow Dm_{T}(y,x)) \)

donde \( Dm_{T^{*}} \)y \( Dm_{T} \) son las relaciones que "\( y \) es una demostración de \( x \)'' en \( T^{*} \) y \( T \) respectivamente. Equivlentemente:

\( \underset{\mathcal{P}}{\vdash}\forall xy\:(\neg Dm_{T}(y,x)\rightarrow\neg Dm_{T^{*}}(y,x)) \)

Particularizado para \( x=0^{(k)} \), donde \( k \) es el código de la sentencia \( \neg(x_{0}=x_{0}) \), tenemos

\( \underset{\mathcal{P}}{\vdash}\forall y\:(\neg Dm_{T}(y,0^{(k)})\rightarrow\neg Dm_{T^{*}}(y,0^{(k)})) \).

Pero si esta sentencia es demostrable en \( \mathcal{P} \) entonces es demostrable en toda teoría aritmética. En particular, es demostrable en \( T^{*} \), resultando

\( \underset{\mathcal{\mathrm{\mathit{T^{*}}}}}{\vdash}\forall y\:(\neg Dm_{T}(y,0^{(k)})\rightarrow\neg Dm_{T^{*}}(y,0^{(k)})) \)   (2)

Recordemos ahora que en (1) llegamos a \( \underset{T^{*}}{\vdash}consis(T) \) que por definición de \( consis(T) \) es

\( \underset{\mathcal{\mathrm{\mathit{T^{*}}}}}{\vdash}\forall y\:\neg Dm_{T}(y,0^{(k)}) \)   (3)

de (2) y (3) sigue

\( \underset{\mathcal{\mathrm{\mathit{T^{*}}}}}{\vdash}\forall y\:\neg Dm_{T^{*}}(y,0^{(k)}) \)

Esto es

\( \underset{T^{*}}{\vdash}consis(T^{*}) \)

Luego, \( T^{*} \) es contradictoria por 2° teorema de incompletitud y \( T \) contradictoria por ser una extensión de \( T^{*} \)
-------------

Teorema 2

Toda teoría aritmética designable y estandar es incompleta.

Demostración:
Sea \( T \) una teoría aritmética designable y estandar. Veremos que \( consis(T) \) es indecidible en \( T \).

Si \( \underset{T}{\vdash}consis(T) \) entonces por teorema anterior, \( T \) es contradictoria y por lo tanto no admite un modelo estandar. Luego no\( \underset{T}{\vdash}consis(T) \)

Si \( \underset{T}{\vdash}\neg consis(T) \) y \( T \) es estandar, entonces \( \neg consis(T) \) es verdadera en su interpretación natural, entonces \( T \) es contradictoria y por lo tanto no es estandar. Absurdo. Luego no\( \underset{T}{\vdash}\neg consis(T) \).

Por lo tanto \( consis(T) \) es indecidible en \( T \) y \( T \) es incompleta.
------------

Este teorema está en línea con el teorema de Tarski, ya que si existiera una teoría aritmética designable, estandar y completa \( T \), entonces la fórmula \( \exists y\: Dm_{T}(y,x) \) se interpretaría como "x es el código de una sentencia aritmética verdadera'' y la verdad aritmética sería definible.

Saludos

[Carlos Ivorra]

... ya que si \( d \) es una demostración en \( T \) y \( a_{1},\ldots\,,a_{n} \) son los axiomas de \( T \) presentes en \( d \), entonces las afirmaciónes \( Ax_{T}(a_{i}) \) son finitamente verificables y las sentencias \( Ax_{T}(0^{(a_{i})}) \) son demostrables en \( \mathcal{P} \), esto es, \( \underset{\mathcal{P}}{\vdash}Ax_{T}(0^{(a_{i})}) \), con \( 0<i\leq n \).

¿Por qué dices que las afirmaciónes \( Ax_{T}(a_{i}) \) son finitamente verificables? Según tu planteamiento, esas afirmaciones son verdaderas en la interpretación natural si y sólo si el correspondiente \( a_i \) es el número de Gödel de un axioma de T. En tu argumento estás llamando \( a_i \) al número de un axioma de T, luego, por definición de \( a_i \), la afirmación \( Ax_{T}(a_{i}) \) es verdadera en la interpretación natural, pero eso no significa que tú puedas saberlo en un caso concreto, ni mucho menos que lo puedas demostrar a partir de los axiomas de Peano.

Retomando desde un poco antes tu argumento: partes de una teoría no recursiva y supones que en ella puede demostrarse consis T y consideras una demostración. No hay nada que objetar a lo que dices, pero ten presente que una cosa es que esa demostración exista y otra muy distinta que tú, al verla, puedas reconocerla como tal, pues cuando veas en ella fórmulas que no se deducen de ninguna fórmula anterior, lo máximo que podrás decir es "esto será una demostración en T" si estas fórmulas que no se deducen de otras son axiomas de T, pero no tendrás medios para saber si es o no el caso. Eso no invalida nada de lo que dices hasta la frase que te he citado, pues ahí no sólo hablas de una demostración que puede existir aunque tú no sepas reconocerla como tal, sino que pretendes que dicha demostración, no sólo existe, sino que existe y tú la reconoces. Pero si realmente puedes reconocer cuándo una cadena de fórmulas es o no una demostración de T, es porque los axiomas de T son recursivos.

[Cristian C]

Veré si te he entendido, porque si lo que me dices es lo que he entendido, entonces tengo otra duda.

Si \( \underset{T}{\vdash}consis(T) \), entonces existe un natural \( d \) que es el código de una demostración de \( consis(T) \) en \( T \). Con el supuesto \( \underset{T}{\vdash}consis(T) \) yo puedo afirmar que \( d \) existe, pero no que puedo saber cuál es. Ahora bien, si \( d \) codifica una demostración, puedo saber también que existen unos \( a_{1},\ldots\,,a_{n} \) presentes en \( d \) que codifican axiomas de \( T \), pero, nuevamente, no se cuales son esos \( a_{1},\ldots\,,a_{n} \). Luego, con estos \( a_{i} \) desconocidos construyo una teoría \( T^{*} \) consistente en agregarle los \( a_{i} \) a los axiomas de Peano. La fórmula definidora de los códigos de axiomas de \( T^{*} \) es entonces:

\( Ax_{T^{*}}(x)\equiv Ax_{\mathcal{P}}(x)\vee x=0^{(a_{1})}\vee\ldots\:\vee x=0^{(a_{n})} \)

Llegado a este punto, no sé cómo aclararme entre este par de interpretaciones de los hechos:

1. \( T^{*} \) no es recursiva pues dado un número natural \( n \) cualquiera, no puedo saber si es el código de un axioma o no, ya que, tal lo dicho, no se cuáles son los \( a_{1},\ldots\,,a_{n} \) (solo se que existen) y entonces \( Ax_{T^{*}}(x) \) solo puede verificarse cuando \( x \) es el codigo de un axiona de \( \mathcal{P} \).

2. Se que \( T^{*} \) existe y es una teoría aritmética recursiva, pero no se cuál es.

No sé cual de las dos interpretaciones es la correcta (si es que alguna de ellas lo es) y qué criterio lo decide.
Perdón si lo que pregunto es muy básico, pero aquí estoy realmente.

Saludos

[Carlos Ivorra]

La teoría \( T^* \) es recursiva, porque su conjunto de axiomas es la unión de dos conjuntos recursivos: el conjunto de axiomas de Peano y un conjunto finito (y todo conjunto finito es recursivo).

La forma más cruda de lo que te confunde es la siguiente:

Define el conjunto \( A \) que es igual a \( \{0\} \) si ZFC es consistente y a \( \{1\} \) si ZFC es contradictoria. En cualquiera de los dos casos, el conjunto \( A \) es finito, luego es recursivo, pero es imposible saber si \( 0\in A \) o no.

Lo que sucede es que existe un algoritmo para saber si un número natural está o no en A, pero no sabemos cuál es ese algoritmo. Si ZFC es consistente, el algoritmo es "mira si el número es 0, en cuyo caso di que sí, y si no, di que no", mientras que si ZFC no es consistente, el algoritmo es "mira si el número es 1, en cuyo caso di que sí, y si no, di que no".

No pidas disculpas por preguntar. Estas cosas marean al más pintado.

[Cristian C]

Hola Carlos.

He modificado la prueba del Teorema 1 para evitar los problemas que me señalaste.

Recordemos que estoy diciendo que una relación es designable cuando es la interpretación natural de alguna fórmula del lenguaje, independientemente de que sea recursiva o no. Y que una teoría aritmética es designable cuando lo es la relación que define los códigos de sus axiomas. De este modo, todas las teorías aritméticas recursivas son designables pero también lo son algunas no recursivas.

La prueba que se me ha ocurrido es la siguiente:

Teorema 1

Si \( T \) es una teoría aritmética designable, entonces

\( \underset{T}{\vdash}consis(T) \) ssys \( T \) es contradictoria.

(Observemos que si \( T \) es no designable, entonces \( consis(T) \) no
se puede definir, y la tesis carece de sentido)

Demostración:

Si \( T \) es contradictoria entonces todo es demostrable en \( T \) y en particular \( \underset{T}{\vdash}consis(T) \) .

Si \( \underset{T}{\vdash}consis(T) \) sea \( d \) el código de una demostración de \( consis(T) \) en \( T \), sean \( a_{1},\ldots\,,a_{n} \) los códigos de la sucesión de sentencias de dicha demostración. Observemos que todos los \( a_{i} \) codifican teoremas de \( T \). Sea \( T^{*} \) la teoría que resulta de agregarle las sentencias de códigos \( a_{1},\ldots\,,a_{n} \) a los axiomas de Peano. Entonces se tiene que \( T^{*} \) es una teoría aritmética recursiva y además \( d \) codifica una demostración de \( consis(T) \) en \( T^{*} \), esto es, \( \underset{T^{*}}{\vdash}consis(T) \) (1).

Observemos que la relación que define los códigos de los axiomas de \( T^{*} \) es \( \alpha^{*}(x)\equiv Ax_{\mathcal{P}}(x)\vee x=a_{1}\vee\ldots\:\vee x=a_{n} \), donde \( Ax_{\mathcal{P}}(x) \) es la relación definidora de los códigos de los axiomas de Peano.

Sea \( \Gamma \) un sistema de axiomas de \( T \) y \( \alpha(x) \) la relación que define los códigos de sus elementos.

Sea ahora \( \Delta=\Gamma\cup\{A_{1},\ldots,\: A_{n}\}\cup P \), donde los \( A_{1},\ldots,\: A_{n} \) son las sentencias codificadas por los \( a_{i} \) y \( P \) el conjunto de axiomas de Peano. Es claro que \( \Delta \) es también un sistema de axiomas de \( T \) ya que contiene a \( \Gamma \) y todos sus elementos son teoremas de \( T \).

Entonces, la relación definidora de los códigos de los elementos de \( \Delta \) queda definida por:

\( \beta(x)\equiv\alpha(x)\vee x=a_{1}\vee\ldots\:\vee x=a_{n}\vee Ax_{\mathcal{P}}(x) \)
Asi pues, \( \beta(x) \) es la relación definidora de un sistema de axiomas de \( T \).

Ahora olvidemos el significado de las relaciones y operemos sintácticamente con sus fórmulas. Se tiene la siguiente cadena de implicaciones:

\( \underset{\mathcal{P}}{\vdash}\alpha^{*}(x)\rightarrow\alpha^{*}(x) \)
\( \underset{\mathcal{P}}{\vdash}\alpha^{*}(x)\rightarrow(\alpha^{*}(x)\vee\alpha(x)) \)
\( \underset{\mathcal{P}}{\vdash}\alpha^{*}(x)\rightarrow(Ax_{\mathcal{P}}(x)\vee x=0^{(a_{1})}\vee\ldots\:\vee x=0^{(a_{n})}\vee\alpha(x)) \) (por definición de \( \alpha^{*}(x) \))
\( \underset{\mathcal{P}}{\vdash}\alpha^{*}(x)\rightarrow\beta(x) \) (por definición de \( \beta(x) \)) (2)

Recordemos ahora que \( \alpha^{*}(x) \) es la fórmula definidora de los códigos de los axiomas de \( T^{*} \) en tanto que \( \beta(x) \) define los de \( T \). Entonces la fórmula \( Dm_{T}(y,x) \) es la que resulta de reemplazar en \( Dm_{T^{*}}(y,x) \) la fórmula \( \alpha^{*}(x) \) por la fórmula \( \beta(x) \). Luego, si se verifica (2), se tiene que:

\( \underset{\mathcal{P}}{\vdash}Dm_{T^{*}}(y,x)\rightarrow Dm_{T}(y,x) \)
Cuyo contrarecíproco es
\( \underset{\mathcal{P}}{\vdash}\neg Dm_{T}(y,x)\rightarrow\neg Dm_{T^{*}}(y,x) \)
Particularizado para \( x=0^{(k)} \), donde \( k \) es el código de la sentencia \( \neg(x_{0}=x_{0}) \), tenemos
\( \underset{\mathcal{P}}{\vdash}\neg Dm_{T}(y,0^{(k)})\rightarrow\neg Dm_{T^{*}}(y,0^{(k)}) \)
Generalizando
\( \underset{\mathcal{P}}{\vdash}\forall y\:(\neg Dm_{T}(y,0^{(k)})\rightarrow\neg Dm_{T^{*}}(y,0^{(k)})) \)
Si esta sentencia es demostrable en \( \mathcal{P} \) entonces es demostrable en toda teoría aritmética, en particular, es demostrable en \( T^{*} \)
\( \underset{\mathcal{\mathit{T^{*}}}}{\vdash}\forall y\:(\neg Dm_{T}(y,0^{(k)})\rightarrow\neg Dm_{T^{*}}(y,0^{(k)})) \) (3)

Por (1), \( \underset{T^{*}}{\vdash}consis(T) \), esto es,  \( \underset{\mathcal{\mathit{T^{*}}}}{\vdash}\forall y\:(\neg Dm_{T}(y,0^{(k)}) \) (4)

De (3) y (4)

\( \underset{\mathcal{\mathit{T^{*}}}}{\vdash}\forall y\:\neg Dm_{T^{*}}(y,0^{(k)}) \) que por definición implica \( \underset{T^{*}}{\vdash}consis(T^{*}) \)

Luego, \( T^{*} \) es contradictoria por 2° teorema de incompletitud y \( T \) es contradictoria por ser una extensión de \( T^{*} \).
------------

Bueno, he allí mi segundo intento de prueba. Ya me dirás tu si se me sigue colando algo.

Saludos.

[Carlos Ivorra]

¡Uf! Esta vez has hilado muy fino. Me ha costado mucho encontrar un fallo, pero creo que lo hay.

Tú quieres demostrar en \( T^* \) que no es posible probar una contradicción a partir de los axiomas de \( T^* \), es decir, a partir de los axiomas descritos por

\( \alpha^{*}(x)\equiv Ax_{\mathcal{P}}(x)\vee x=a_{1}\vee\ldots\:\vee x=a_{n} \)

y lo que demuestras es que si existiera una prueba de una contradicción a partir de los axiomas de \( T^* \), ella misma sería también la prueba de una contradicción a partir de los axiomas descritos por

\( \beta(x)\equiv\alpha(x)\vee x=a_{1}\vee\ldots\:\vee x=a_{n}\vee Ax_{\mathcal{P}}(x) \).

Esto es cierto. Por otra parte, en \( T^* \) puedes demostrar que es imposible llegar a una contradicción a partir de los axiomas descritos por \( \alpha(x) \). Para llegar a una contradicción (sé que tú no lo planteas como una reducción al absurdo, pero el "agujero" es equivalente y creo que así se ve más claro)  necesitarías demostrar que a partir de una deducción que parta de los axiomas \( \beta(x) \) puedes obtener una deducción con la misma conclusión a partir de los axiomas \( \alpha(x) \). No te basta con que esto sea verdad en su interpretación natural (que lo es). Necesitas demostrarlo en \( T^* \). Y ello requiere demostrar en \( T^* \) que las fórmulas codificadas por los \( a_i \) se deducen de los axiomas descritos por \( \alpha(x) \).

Y aun suponiendo que conocieras una deducción de \( A_i \) a partir de los axiomas descritos por \( \alpha(x) \), con ello sólo sabrías que los axiomas de \( T \) que intervienen en la deducción tienen números de Gödel \( n \) tales que \( \alpha(0^{(n)}) \) es verdadera en la interpretación natural, pero eso no significa que puedas demostrar \( \alpha(0^{(n)}) \) en \( T^* \) y, si no puedes, tampoco puedes demostrar en \( T^* \) que la deducción que supuestamente conoces de \( A_i \) es realmente una deducción a partir de los axiomas de \( T \) y ahí se rompe tu argumento.

Lo he planteado así porque creo que se ve mejor, pero ahora voy a tratar de seguir paso a paso tu razonamiento. El problema aparece cuando dices:

Sea ahora \( \Delta=\Gamma\cup\{A_{1},\ldots,\: A_{n}\}\cup P \), donde los \( A_{1},\ldots,\: A_{n} \) son las sentencias codificadas por los \( a_{i} \) y \( P \) el conjunto de axiomas de Peano. Es claro que \( \Delta \) es también un sistema de axiomas de \( T \) ya que contiene a \( \Gamma \) y todos sus elementos son teoremas de \( T \).

Llamemos \( T' \) a la teoría que tiene por axiomas a las sentencias de \( \Delta \). Tú dices que \( T' \) es la misma que \( T \), y eso es cierto en el sentido de que ambas tienen los mismos teoremas, pero lo que he tratado de explicar antes es que no puedes demostrar en \( T^* \) que eso es así. O, en otras palabras, no puedes probar en \( T^* \) que \( Dm_{T'}(y,x)\rightarrow Dm_T(y,x) \), aunque esta afirmación es verdadera en su interpretación natural.

Esto hace que no puedas usar \( T' \) como si fuera \( T \) en el resto de tu argumento. Tu argumento demuestra correctamente que

\( \underset{\mathcal{\mathit{T^*}}}{\vdash} \mbox{consis} T'\rightarrow \mbox{consis} T^* \)

y por otra parte tienes \( \underset{\mathcal{\mathit{T^*}}}{\vdash} \mbox{consis} T \).

Aparte de esto, sólo sabes que la sentencia \(  \mbox{consis} T'\leftrightarrow \mbox{consis} T \) es verdadera, pero nada te asegura que sea demostrable en \( T^* \), y ahí está el "agujero".