Lema diagonal

En lógica matemática, el lema diagonal (también conocido como lema de diagonalización, lema de autorreferencia[1]​ o teorema del punto fijo) establece la existencia de sentencias autorreferenciadas en ciertas teorías formales de los números naturales, específicamente aquellas teorías que son lo suficientemente fuertes como para representar todas las funciones computables. Las oraciones cuya existencia está asegurada por el lema diagonal pueden, a su vez, usarse para probar resultados limitativos fundamentales como los teoremas de incompletitud de Gödel y el teorema de indefinibilidad de Tarski.[2]​

Antecedentes

Sea ${\displaystyle \mathbb {N} }$ el conjunto de los números naturales. Una teoría de primer orden ${\displaystyle T}$ en el lenguaje de la aritmética representa[3]​ la función computable ${\displaystyle f:\mathbb {N} \rightarrow \mathbb {N} }$ si existe una fórmula expresable como un "grafo" ${\displaystyle {\mathcal {G}}_{f}(x,y)}$ en el lenguaje de ${\displaystyle T}$ tal que para cada ${\displaystyle n\in \mathbb {N} }$

${\displaystyle \vdash _{T}\,(\forall y)[(^{\circ }f(n)=y)\Leftrightarrow {\mathcal {G}}_{f}(^{\circ }n,\,y)]}$

Aquí, ${\displaystyle {}^{\circ }n}$ es el numeral correspondiente al número natural ${\displaystyle n}$, que se define como el ${\displaystyle n}$º sucesor del presunto primer numeral ${\displaystyle 0}$ en ${\displaystyle T}$.

El lema diagonal también requiere una forma sistemática de asignar a cada fórmula ${\displaystyle {\mathcal {A}}}$ un número natural ${\displaystyle \#({\mathcal {A}})}$ (también escrito como ${\displaystyle \#_{\mathcal {A}}}$) llamado su número de Gödel. Entonces, las fórmulas se pueden representar dentro de ${\displaystyle T}$ mediante los números correspondientes a sus números de Gödel. Por ejemplo, ${\displaystyle {\mathcal {A}}}$ está representada por ${\displaystyle ^{\circ }\#_{\mathcal {A}}}$

El lema diagonal se aplica a teorías capaces de representar todas las funciones primitivas recursivas. Tales teorías incluyen la aritmética de Peano de primer orden y la más débil aritmética de Robinson, e incluso una teoría mucho más débil conocida como R. Una declaración común del lema (como se indica a continuación) supone más firmemente que la teoría puede representar todas las funciones computables, pero todas las teorías mencionadas también tienen esta capacidad.

Enunciado del lema

Sea ${\displaystyle T}$ una teoría de primer orden en el lenguaje de la aritmética capaz de representar todas las funciones computables, y sea ${\displaystyle {\mathcal {F}}(y)}$ una fórmula en ${\displaystyle T}$ con una variable libre. Entonces, existe una sentencia ${\displaystyle {\mathcal {C}}}$ tal que ${\displaystyle \vdash _{T}\,{\mathcal {C}}\Leftrightarrow {\mathcal {F}}({}^{\circ }\#_{\mathcal {C}})}$

Intuitivamente, ${\displaystyle {\mathcal {C}}}$ es una oración autorreferenciada: ${\displaystyle {\mathcal {C}}}$ afirma que ${\displaystyle {\mathcal {C}}}$ tiene la propiedad ${\displaystyle {\mathcal {F}}}$. La oración ${\displaystyle {\mathcal {C}}}$ también puede verse como un punto fijo de la operación que asigna, a la clase de equivalencia de una oración determinada ${\displaystyle {\mathcal {A}}}$, la clase de equivalencia de la oración ${\displaystyle {\mathcal {F}}(^{\circ }\#_{\mathcal {A}})}$ (la clase de equivalencia de una oración es el conjunto de todas las oraciones a las que es demostrablemente equivalente en la teoría ${\displaystyle T}$). La oración ${\displaystyle {\mathcal {C}}}$ construida en la demostración no es literalmente la misma que ${\displaystyle F(^{\circ }\#_{\mathcal {C}})}$, pero es demostrablemente equivalente a ella en la teoría ${\displaystyle T}$.

Demostración

Sea ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ la función definida por:

${\displaystyle f(\#_{\mathcal {A}})=\#[{\mathcal {A}}(^{\circ }\#_{\mathcal {A}})]}$

para cada fórmula ${\displaystyle {\mathcal {A}}(x)}$ con una sola variable libre ${\displaystyle x}$ en la teoría ${\displaystyle T}$, y ${\displaystyle f(n)=0}$ en caso contrario. Aquí, ${\displaystyle \#_{\mathcal {A}}=\#({\mathcal {A}}(x))}$ denota el número de Gödel de la fórmula ${\displaystyle {\mathcal {A}}(x)}$. La función ${\displaystyle f}$ es computable (lo que en última instancia es una suposición sobre el esquema de numeración de Gödel), por lo que existe una fórmula ${\displaystyle {\mathcal {G}}_{f}(x,\,y)}$ que representa ${\displaystyle f}$ en ${\displaystyle T}$. Nominalmente

${\displaystyle \vdash _{T}\,(\forall y)\{{\mathcal {G}}_{f}(^{\circ }\#_{\mathcal {A}},\,y)\Leftrightarrow [y={}^{\circ }f(\#_{\mathcal {A}})]\}}$

lo que equivale a decir que

${\displaystyle \vdash _{T}\,(\forall y)\{{\mathcal {G}}_{f}(^{\circ }\#_{\mathcal {A}},\,y)\Leftrightarrow [y={}^{\circ }\#({\mathcal {A}}(^{\circ }\#_{\mathcal {A}}))]\}}$

Ahora, dada una fórmula arbitraria ${\displaystyle {\mathcal {F}}(y)}$ con una variable libre ${\displaystyle y}$, se define la fórmula ${\displaystyle {\mathcal {B}}(z)}$ como:

${\displaystyle {\mathcal {B}}(z):=(\forall y)[{\mathcal {G}}_{f}(z,\,y)\Rightarrow {\mathcal {F}}(y)]}$

Entonces, para todas las fórmulas ${\displaystyle {\mathcal {A}}(x)}$ con una variable libre:

${\displaystyle \vdash _{T}\,{\mathcal {B}}(^{\circ }\#_{\mathcal {A}})\Leftrightarrow (\forall y)\{[y={}^{\circ }\#({\mathcal {A}}(^{\circ }\#_{\mathcal {A}}))]\Rightarrow {\mathcal {F}}(y)\}}$

lo que equivale a decir que

${\displaystyle \vdash _{T}\,{\mathcal {B}}(^{\circ }\#_{\mathcal {A}})\Leftrightarrow {\mathcal {F}}(^{\circ }\#[{\mathcal {A}}(^{\circ }\#_{\mathcal {A}})])}$

Ahora, se sustituye ${\displaystyle {\mathcal {A}}}$ por ${\displaystyle {\mathcal {B}}}$ y se define la oración ${\displaystyle {\mathcal {C}}}$ como:

${\displaystyle {\mathcal {C}}:={\mathcal {B}}(^{\circ }\#_{\mathcal {B}})}$

Entonces la línea anterior se puede reescribir como

${\displaystyle \vdash _{T}\,{\mathcal {C}}\Leftrightarrow {\mathcal {F}}(^{\circ }\#_{\mathcal {C}})}$

que es el resultado buscado.

(El mismo argumento en términos diferentes se presenta en [Raatikainen (2015a)].)

Historia

El lema se llama "diagonal" porque tiene cierto parecido con el argumento de la diagonal de Cantor.[4]​ Los términos "lema diagonal" o "punto fijo" no aparecen en el artículo de 1931 de Kurt Gödel ni en el artículo de 1936 publicado por Alfred Tarski.

Rudolf Carnap (1934) fue el primero en demostrar el lema autorreferencial general,[5]​ que dice que para cualquier fórmula F en una teoría T que satisfaga ciertas condiciones, existe una fórmula ψ tal que ψ ↔ F(°#(ψ)) es demostrable en T. El trabajo de Carnap fue redactado en un lenguaje alternativo, ya que el concepto de función computable aún no se había desarrollado en 1934. Mendelson (1997, p. 204) cree que Carnap fue el primero en afirmar que algo así como el lema diagonal estaba implícito en el razonamiento de Gödel, quien conocía el trabajo de Carnap en 1937.[6]​

El lema diagonal está estrechamente relacionado con el teorema de recursión de Kleene en la teoría de la computabilidad, y sus respectivas demostraciones son similares.

Véase también

• Autorreferencia indirecta
• Teorema del punto fijo
• Aritmética recursiva primitiva
• Autorreferencia
• Paradojas autorreferentes

Referencias

1. Hájek, Petr; Pudlák, Pavel (1998) [first printing 1993]. Metamathematics of First-Order Arithmetic. Perspectives in Mathematical Logic (1st edición). Springer. ISBN 3-540-63648-X. ISSN 0172-6641. «En los textos modernos, estos resultados se prueban utilizando el conocido lema de diagonalización (o autorreferencia), que ya está implícito en la prueba de Gödel.» 
2. Véase Boolos y Jeffrey (2002, sec. 15) y Mendelson (1997, Prop. 3.37 and Cor. 3.44 ).
3. Para obtener detalles sobre la representabilidad, consúltese Hinman 2005, p. 316
4. Véase, por ejemplo, Gaifman (2006).
5. Kurt Gödel, Collected Works, Volume I: Publications 1929–1936, Oxford University Press, 1986, p. 339.
6. Véase la recopilación de los trabajos de Gödel Collected Works, Vol. 1, Oxford University Press, 1986, p. 363, fn 23.

Bibliografía

• George Boolos y Richard Jeffrey, 1989. Computabilidad y Lógica, 3ª ed. Prensa de la Universidad de Cambridge. ISBN 0-521-38026-X ISBN 0-521-38923-2
• Rudolf Carnap, 1934. Logische Syntax der Sprache. (Traducción al inglés: 2003. La sintaxis lógica del lenguaje. Open Court Publishing.)
• Haim Gaifman, 2006. 'Denominación y diagonalización: de Cantor a Gödel y a Kleene'. Revista Lógica del IGPL, 14: 709–728.
• Hinman, Peter, 2005. Fundamentos de la lógica matemática. AK Peters. ISBN 1-56881-262-0
• Mendelson, Elliott, 1997. Introducción a la Lógica Matemática, 4ª ed. Chapman y Hall.
• Panu Raatikainen, 2015a. El lema de la diagonalización. En Stanford Encyclopedia of Philosophy, ed. Zalta. Suplemento de Raatikainen (2015b).
• Panu Raatikainen, 2015b. Teoremas de incompletitud de Gödel. En Stanford Encyclopedia of Philosophy, ed. Zalta.
• Raymond Smullyan, 1991. Teoremas de incompletitud de Gödel. Universidad de Oxford. Prensa.
• Raymond Smullyan, 1994. Diagonalización y autorreferencia. Universidad de Oxford. Prensa.
• Alfred Tarski (1936). «Der Wahrheitsbegriff in den formalisierten Sprachen». Studia Philosophica 1: 261-405. Archivado desde el original el 9 de enero de 2014. Consultado el 26 de junio de 2013. 
  • Alfred Tarski, tr. J. H. Woodger, 1983. "El concepto de verdad en los lenguajes formalizados". traducción al inglés del artículo de Tarski de 1936. En A. Tarski, ed. J. Corcoran, 1983, Lógica, Semántica, Metamatemática, Hackett.

• Datos: Q2904195