Lema diagonal

Declaración en lógica matemática

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 enunciados autorreferenciales en ciertas teorías formales de los números naturales —específicamente aquellas teorías que son lo suficientemente fuertes para representar todas las funciones computables . Las oraciones cuya existencia está asegurada por el lema diagonal pueden, a su vez, usarse para demostrar resultados limitativos fundamentales como los teoremas de incompletitud de Gödel y el teorema de indefinibilidad de Tarski . ^[2]

Fondo

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

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

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

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

El lema diagonal se aplica a teorías capaces de representar todas las funciones recursivas primitivas . Tales teorías incluyen la aritmética de Peano de primer orden y la aritmética de Robinson más débil, 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 tienen esa capacidad también.

Declaración del lema

Lema ^[4]  -  Sea una teoría de primer orden en el lenguaje de la aritmética y capaz de representar todas las funciones computables , y sea una fórmula con una variable libre. Entonces existe una oración tal que ${\displaystyle T}$ ${\displaystyle {\mathcal {F}}(y)}$ ${\displaystyle T}$ ${\displaystyle {\mathcal {C}}}$

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

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

Prueba

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

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

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

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

que es decir

${\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 con una variable libre , defina la fórmula como: ${\displaystyle {\mathcal {F}}(y)}$ ${\displaystyle y}$ ${\displaystyle {\mathcal {B}}(z)}$

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

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

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

que es decir

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

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

${\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}})}$

cual es el resultado deseado.

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

Historia

El lema se llama "diagonal" porque guarda cierta semejanza con el argumento de la diagonal de Cantor . ^[5] Los términos "lema diagonal" o "punto fijo" no aparecen en el artículo de Kurt Gödel de 1931 ni en el artículo de Alfred Tarski de 1936 .

Rudolf Carnap (1934) fue el primero en demostrar el lema general autorreferencial , ^[6] 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 funciones computables aún no estaba 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. Gödel conocía el trabajo de Carnap en 1937. ^[7]

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

Ver también

• Autorreferencia indirecta
• Lista de teoremas del punto fijo
• Aritmética recursiva primitiva
• autorreferencia
• Paradojas autorreferenciales

Notas

1. Hájek, Petr ; Pudlák, Pavel (1998) [primera impresión 1993]. Metamatemáticas de la aritmética de primer orden . Perspectivas en lógica matemática (1ª ed.). Saltador. 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, art. 15) y Mendelson (1997, Prop. 3.37 y Cor. 3.44).
3. Para obtener detalles sobre la representabilidad, consulte Hinman 2005, p. 316
4. Smullyan (1991, 1994) son referencias especializadas estándar. El lema es la Proposición 3.34 de Mendelson (1997) y se trata en muchos textos sobre lógica matemática básica, como Boolos y Jeffrey (1989, sec. 15) y Hinman (2005).
5. Véase, por ejemplo, Gaifman (2006).
6. Kurt Gödel , Obras completas, Volumen I: Publicaciones 1929-1936 , Oxford University Press, 1986, p. 339.
7. Véase las obras completas de Gödel , vol. 1 , Oxford University Press, 1986, pág. 363, nota 23.

Referencias

• 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 Enciclopedia de Filosofía de Stanford , ed. Zalta. Suplemento de Raatikainen (2015b).
• Panu Raatikainen, 2015b. Teoremas de incompletitud de Gödel. En Enciclopedia de Filosofía de Stanford , 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" (PDF) . Estudios Filosóficos . 1 : 261–405. Archivado desde el original (PDF) el 9 de enero de 2014 . Consultado el 26 de junio de 2013 .
  • Alfred Tarski , tr. JH 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.