Lema diagonal

En llògica matemàtica, el lema diagonal (també conegut com a lema de diagonalisació, lema de autorreferencia o teorema del punt fix) establix l'existència de sentències autorreferenciadas en certes teories formals dels número natural, específicament aquelles teories que són lo suficientment fortes com per a representar totes les funcions computables. Les oracions l'existència de les quals està assegurada pel lema diagonal poden, a la seua volta, usar-se per a provar resultats limitativos fonamentals com els teoremes de incompletitud de Gödel i el teorema de indefinibilidad de Tarski.

Antecedents

Siga $\mathbb{N}$ el conjunt dels número natural. Una teoria de primer orde $T$ en el llenguage de l'aritmètica representa la funció computable $f:\mathbb{N}\to \mathbb{N}$ si existix una fòrmula expressable com un «grafo» ${𝒢}_f(x,y)$ en el llenguage de $T$ tal que per a cada $n\in \mathbb{N}$

${⊢}_T(\mathrm{\forall }y)[{(}^{\circ }f(n)=y)\iff {𝒢}_f{(}^{\circ }n,y)]$

Ací, ${}^{\circ }n$ és el numeral corresponent al número natural $n$, que es definix com el $n$º successor del presunt primer numeral $0$ en $T$.

El lema diagonal també requerix una forma sistemàtica d'assignar a cada fòrmula $𝒜$ un número natural $\mathrm{\#}(𝒜)$ (també escrit com ${\mathrm{\#}}_{𝒜}$) cridat el seu número de Gödel. Llavors, les fòrmules es poden representar dins de $T$ per mig dels números corresponents als seus números de Gödel. Per eixemple, $𝒜$ està representada per ${}^{\circ }{\mathrm{\#}}_{𝒜}$

El lema diagonal s'aplica a teories capaces de representar totes les funcions primitives recursivas. Tals teories inclouen l'aritmètica de Peano de primer orde i la més dèbil aritmètica de Robinson, i inclús una teoria molt més dèbil coneguda com R. Una declaració comuna del lema (com s'indica a continuació) supon més fermament que la teoria pot representar totes les funcions computables, pero totes les teories mencionades també tenen esta capacitat.

Enunciat del lema

Intuitivamente, $𝒞$ és una oració autorreferenciada: $𝒞$ afirma que $𝒞$ té la propietat $ℱ$. L'oració $𝒞$ també pot vore's com un punt fix de l'operació que assigna, a la classe d'equivalència d'una oració determinada $𝒜$, la classe d'equivalència de l'oració $ℱ{(}^{\circ }{\mathrm{\#}}_{𝒜})$ (la classe d'equivalència d'una oració és el conjunt de totes les oracions a les que és demostrablemente equivalent en la teoria $T$). L'oració $𝒞$ construïda en la demostració no és lliteralment la mateixa que $F{(}^{\circ }{\mathrm{\#}}_{𝒞})$, pero és demostrablemente equivalent a ella en la teoria $T$.

Vore també

• Autorreferencia indirecta
• Teorema del punt fix
• Aritmètica recursiva primitiva
• Autorreferencia
• Paradoxes autorreferentes

Bibliografia

• George Boolos i Richard Jeffrey, 1989. Computabilidad i Llògica, 3ª ed. Prensa de l'Universitat de Cambridge. ISBN 0-521-38026-X ISBN 0-521-38923-2
• Rudolf Carnap, 1934. Logische Syntax der Sprache. (Traducció a l'anglés: 2003. La sintaxis llògica del llenguage. Open Court Publishing.)
• Haim Gaifman, 2006. 'Denominació i diagonalisació: de Cantor a Gödel i a Kleene'. Revista Llògica de el IGPL, 14: 709–728.

• Hinman, Peter, 2005. Fonaments de la llògica matemàtica. AK Peters. ISBN 1-56881-262-0
• Mendelson, Elliott, 1997. Introducció a la Llògica Matemàtica, 4ª ed. Chapman i Hall.
• Panu Raatikainen, 2015a. El lema de la diagonalisació. En Stanford Encyclopedia of Philosophy, ed. Zalta. Suplement de Raatikainen (2015b).
• Panu Raatikainen, 2015b. Teoremes de incompletitud de Gödel. En Stanford Encyclopedia of Philosophy, ed. Zalta.
• Raymond Smullyan, 1991. Teoremes de incompletitud de Gödel. Universitat d'Oxford. Prensa.
• Raymond Smullyan, 1994. Diagonalisació i autorreferencia. Universitat d'Oxford. Prensa.
• Alfred Tarski (1936). “Der Wahrheitsbegriff in donen formalisierten Sprachen”. Studia Philosophica 1: 261–405. Recuperate le 2013-06-26.
  • Alfred Tarski, tr. J. H. Woodger, 1983. «El concepte de veres en els llenguages formalisats». traducció a l'anglés de l'artícul de Tarski de 1936. En A. Tarski, ed. J. Corcoran, 1983, Llògica, Semàntica, Metamatemática, Hackett.