Teoremes de incompletitud de Gödel

Archiu:1925 kurt gödel.png

Kurt Gödel als 19 anys d'edat, cinc anys abans de la demostració de les teoremes.

Les teoremes de incompletitud de Gödel són dos célebres teoremes de llògica matemàtica demostrats per Kurt Gödel en 1931. Abdós estan relacionats en l'existència de proposicions indecidibles en certes teories aritmèticas.

Síntesis

La primera teorema de incompletitud afirma que, baixe certes condicions, cap teoria matemàtica formal capaç de descriure els número natural i l'aritmètica en suficient expressivitat és al mateix temps consistent i completa. És dir, si els axiomas de dita teoria no es contradiuen entre sí, llavors existixen enunciats que no es poden provar ni refutar a partir d'ells. En particular, la conclusió de la teorema s'aplica sempre que la teoria aritmètica en qüestió siga recursiva, açò és, una teoria en la que el procés de deducció es puga portar a terme per mig d'un algoritme.^{cita requerida}

La prova de la teorema és totalment explícita i en ella es construïx una fòrmula, denotada habitualment G en honor a Gödel, per a la que donada una demostració de la mateixa, es pot construir una refutació, i viceversa. No obstant, l'interpretació natural de dita sentència en térmens d'número natural és verdadera.

Archiu:Gödel második nemteljességi tétele.png

Segona teorema de incompletitud de Gödel

La segona teorema de incompletitud és un cas particular del primer: afirma que una de les sentències indecidibles de dita teoria és aquella que «afirma» la consistència de la mateixa. És dir, que si el sistema de axioma en qüestió és consistent, no és possible demostrar-ho per mig de dits axioma.

Les teoremes de incompletitud de Gödel són un dels grans alvanços de la llògica matemàtica, i varen supondre —segons la majoria de la comunitat matemàtica— una resposta negativa al segon problema de Hilbert. Les teoremes impliquen que els sistemes axiomàtics de primer orde tenen severes llimitacions per a fonamentar les matemàtiques, i varen supondre un dur colp per al cridat programa de Hilbert per a la fundamentación de les matemàtiques. Per una atra part, durant algun temps ni Hilbert ni uns atres dels seus colaboradors varen ser conscients de l'importància del treball de Gödel per al seu programa.

Context

Les teoremes de incompletitud de Gödel establixen certes llimitacions sobre lo que és possible demostrar per mig d'un raonament matemàtic. Per a parlar en precisió sobre qué «pot demostrar-se» o no, s'estudia un model matemàtic denominat teoria formal. Una teoria formal consta d'una série de signes i un conjunt de regles per a manipular-los i combinar-los. Per mig d'estes regles es poden distinguir certes coleccions de signes com fòrmules, i certes successions de fòrmules com a demostracions. Les teoremes d'una certa teoria són llavors totes les fòrmules que puguen demostrar-se a partir d'una certa colecció inicial de fòrmules que s'assumixquen com axioma.

A una teoria formal se li poden adjudicar certes propietats en funció de lo que siga capaç de demostrar.

• Una teoria consistent no conté contradiccions, és dir, no és possible demostrar al mateix temps una fòrmula i la seua contrària. Una teoria que no siga consistent no té utilitat: pel principi d'explosió, a partir d'una contradicció poden demostrar-se totes les seues fòrmules, i no servix per a modelizar raonaments matemàtics.

Una teoria completa «respon qualsevol pregunta», en el sentit de que para cada una de les seues fòrmules o be és demostradora, o be existix una demostració de la seua contrària (és refutable). Una teoria completa és òptima, i es correspon en l'intuïció sobre la veritat llògica: de la mateixa manera que tota sentència deu ser verdadera o falsa, en una teoria completa tota fòrmula és demostradora o refutable.

No obstant, la primera teorema de incompletitud establix que, baixe certes hipòtesis, una teoria formal no pot tindre abdós propietats al mateix temps. La primera d'elles és que siga una teoria aritmètica, és dir, que els seus símbols servixquen per a descriure els número natural i les seues operacions i relacions; i que siga capaç de demostrar algunes propietats bàsiques sobre ells. La segona hipòtesis és que siga una teoria recursiva, la qual cosa significa que les regles per a manipular els seus signes i fòrmules en les demostracions han de poder eixecutar-se per mig d'un algoritme: una série precisa de passos sense ambigüitat que puga portar-se a terme en un temps finito, i inclús implementar-se per mig d'un programa informàtic.

Vore també

• Sobre proposicions formalment indecidibles de Principia Mathematica i sistemes relacionats
• Filosofia de les matemàtiques
• Consistència llògica
• Autorreferencia
• Argument de Penrose-Lucas
• Logicismo
• Platonisme matemàtic
• Teorema de completitud de Gödel
• Teorema de Löb

Bibliografia

• Barwise, Jon (1989). Handbook of mathematical logic (en anglés), Elsevier. ISBN 9780444863881.
• Boolos, George; Burgess, John P.; Jeffrey, {{{nom3}}} (2007). Computability and logic (en anglés), Cambridge University Press. ISBN 9780521701464..
• ^{[enllaç trencat]}
• (1931).Monatshefte für Mathematik und Physik.38

173-198.doi:10.1007/BF01700692.

Traduït al castellà en:

• Gödel, Kurt (1981). Jesús Mosterín (ed.). Obres completes, Aliança Editorial. ISBN 84-206-2286-9.
• Gödel, Kurt (2006). Sobre proposicions formalment indecidibles dels Principia Mathematica i sistemes afins, KRK Edicions. ISBN 978-84-96476-95-0.
• Hofstadter, Douglas R. (1989). Gödel, Escher, Bach, Tusquets editors. ISBN 84-7223-459-2.
• Hofstadter; Nagel, Ernest; Newman, {{{nom3}}} (2002). Gödel's Proof (en anglés), NYU Press. ISBN 0-8147-5816-9.
• .
• Martínez, Guillermo (2009). Gödel per a tots, Seix Barral. ISBN 978-950-731-605-0.
• (1936).Journal of Symbolic Logic.1(3)

87-91.

• Smullyan, Raymond (1992). Gödel's Incompleteness Theorems (en anglés), Oxford University Press. ISBN 0-19-504672-2.