Teorema d'incompletesa de Gödel: diferència entre les revisions

En [[lògica matemàtica]], els '''teoremes d'incompletesa de Gödel''' són dos cèlebres teoremes demostrats per [[Kurt Gödel]] l'any [[1930]]. Simplificant, el primer teorema afirma:

 

 

Aquest teorema és un dels més famosos fora de les matemàtiques i un dels pitjor compresos. És un teorema de ''lògica formal'', i com a tal és fàcil mal interpretar-lo. N'hi ha molts que semblen similars a aquest primer teorema d'incompletesa de Gödel, però que en realitat no són certs (''vegeu la secció «[[#Malentesos entorn als teoremes de Gödel|Malentesos en torn als teoremes de Gödel]]»'').

El segon teorema, que es demostra formalitzant part de la demostració del primer teorema dins el propi sistema, afirma:

 

 

Aquest resultat fou devastador per a l'aproximació filosòfica a les matemàtiques conegudes com el [[programa de formalització de Hilbert]]. [[David Hilbert]] proposà que la consistència dels sistemes més complexos, tals com l'[[anàlisi real]], es podien demostrar en termes de sistemes més senzills. Finalment, la consistència de totes les matemàtiques es podria reduir a l'aritmètica bàsica. El segon teorema d'incompletesa de Gödel demostra que l'aritmètica bàsica no es pot usar per demostrar la seva pròpia consistència i, per tant, tampoc pot demostrar la consistència de cap altre sistema més fort.

 

== Significat dels teoremes de Gödel ==

Els teoremes de Gödel son teoremes en [[lògica de primer ordre]] i s'han d'entendre en aquest context. En lògica formal, tant les afirmacions matemàtiques com les demostracions s'escriuen en un llenguatge simbòlic en el que es pot comprovar mecànicament la validesa de les proves. D'aquesta forma no pot haver-hi cap dubte de què un teorema es dedueix d'una llista inicial d'axiomes. En teoria, aquest tipus de proves es poden verificar amb un ordinador, i de fet hi ha programes que ho fan (s'anomena [[raonament automatitzat]]).

 

 

== Exemples d'afirmacions indecidibles ==

L'existència d'una afirmació indecidible dins d'un sistema formal no és en si mateixa un fenomen sorprenent.

 

 

== Malentesos entorn als teoremes de Gödel ==

Donat que el primer teorema de Gödel és tan famós, ha donat origen a multitud de malentesos. Aquí en resumim alguns:

 

Per tant, per establir la consistència d'un sistema ''S'' cal utilitzar un altre sistema ''T'', però una prova en ''T'' no és totalment convincent a menys que la consistència de ''T'' ja hagi estat provada sense emprar ''S''. La consistència dels [[axiomes de Peano]] per als [[nombres naturals]] per exemple, es pot demostrar en la [[teoria de conjunts]], però no en la teoria dels nombres naturals per sí sola. Això proporciona una resposta negativa al problema número dos de la famosa llista de qüestions obertes importants en matemàtiques de [[David Hilbert]] (anomenada [[problemes de Hilbert]]).

 

 

 

Els sistemes axiomàtics poden consistir en un nombre infinit d'axiomes (tal i com fa l'aritmètica de primer ordre de Peano), però per a poder aplicar-se el teorema de Gödel ha d'haver-hi un algorisme efectiu que sigui capaç de verificar la correcció de les proves. Per exemple, el conjunt de totes les declaracions de primer ordre que són certes en el model estàndard dels [[nombres naturals]] és complet. El teorema de Gödel no es pot aplicar perquè no hi ha cap procediment efectiu que decideixi si una certa declaració és un axioma. De fet, que això sigui així és conseqüència del primer teorema d'incompletesa de Gödel.

 

 

 

En essència, la prova del primer teorema consistent a construir una declaració ''p'' dintre un sistema formal axiomàtic al que se li pot donar la següent interpretació meta-matemàtica:

Si el sistema aixomàtic és consistent, la prova de Gödel mostra que ''p'' (i la seva negació) no es poden demostrar en el sistema. Per tant, ''p'' és cert (''p'' afirma no ser demostrable i no ho es), però no es pot provar formalment en el sistema. Cal fer veure que afegir ''p'' als axiomes del sistema no resoldria el problema: hi hauria una altre sentència de Gödel per a la teoria ampliada.

 

 

Aquesta perspectiva no està àmpliament acceptada, perquè tal com la planteja [[Marvin Minsky]], la intel·ligència humana és capaç d'errar i de ''comprendre'' declaracions que són en realitat inconsistents o falses. Tot i això, Minsky ha informat que Gödel li va a dir a ell en persona que ell creia que els éssers humans tenen una forma intuïtiva, no solament computacional, d'arribar a la veritat i per tant el seu teorema no limita el que pot arribar a ser sabut com a cert pels humans.

 

La posició de què el teorema mostra que els humans tenen una habilitat que transcendeix la lògica formal també es pot criticar de la següent manera: No sabem si la sentència ''p'' és certa o no, perquè no sabem (ni podem saber) si el sistema és consistent. De manera que en realitat, no sabem cap veritat que estigui fora del sistema. Tot el que sabem és el següent:

 

 

'''Una altre implicació''' és que el treball de Gödel va motivar [[Alan Turing]] (1912-1954) a estudiar quines funcions eren susceptibles de poder ser calculades i quines no. Per a això es va servir de la seva [[màquina de Turing]], una màquina de propòsit general mitjançant la qual va formalitzar les funcions i els procediments de càlcul. Demostrant que existien funcions que no són possibles de calcular mitjançant una Màquina de Turing. El [[paradigma]] d'aquest conjunt de funcions el representa la funció que estableix "si donada una Màquina de Turing, aquesta produeix un resultat o, pel contrari, roman calculant indefinidament". Aquesta funció, coneguda amb el nom de [[Problema de la parada]] (Halting Problem), serà una peça fonamental per demostrar la incomputabilitat de certes funcions.

 

== Esbós de demostració per al primer teorema ==

 

Per començar, tota fórmula o declaració que es pugui formular en el nostra sistema obté un identificador únic, anomenat el [[nombre de Gödel]]. Això es fa d'una manera tal que sigui fàcil convertir mecànicament entre fórmules i nombres de Gödel. Donat que el nostre sistema és el bastant fort per raonar sobre ''nombres'', ara també es possible raonar sobre ''fórmules''.

Si <math>p</math> fos demostrable, llavors <math>SU(G(SU))</math> seria cert, i per la definició de <math>SU, z = G(SU)</math> seria el nombre de Gödel d'una forma declarativa auto-indemostrable. Per tant, <math>SU</math> seria auto-indemostrable, el que per la definició d'aquest terme implica que <math>SU(G(SU))</math> no és demostrable, però aquest era el nostre <math>p</math>: <math>p</math> no és demostrable. Aquesta contradicció mostra que <math>p</math> no pot ser demostrable.

 

 

De manera que l'afirmació <math>p</math> ni es pot provar ni refutar en el nostre sistema.

 

== Esbós de demostració del segon teorema ==

Sigui <math>p</math> la sentència indecidible construïda prèviament, i assumim que la consistència del sistema es pot provar dins el propi sistema. Hem vist a dalt que si el sistema és consistent, llavors <math>p</math> no és demostrable. La prova d'aquesta implicació es pot formalitzar en el propi sistema, i per tant, l'afirmació "<math>p</math> no és demostrable", o "no <math>P(p)</math>" es poden demostrar en el sistema.

 

Però aquesta última declaració és equivalent a <math>p</math> mateix (i aquesta equivalència es pot demostrar en el sistema), de forma que <math>p</math> es pot demostrar en el sistema. Aquesta contradicció posa de manifest que el sistema ha de ser inconsistent.

 

== Vegeu també ==

* [[Consistència lògica]]

* [[Autoreferència]]

* [[Teorema de Löb]]

 

* Kurt Gödel: «[http://home.ddc.net/ygg/etext/godel/ Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I.]», ''Monatshefte für Mathematik und Physik'', '''38''' (1931), pp. 173-198. {{en}}

:Traduït al castellà a: Kurt Gödel: ''Obras completas''. Jesús Mosterín y otros (Trad.) Alianza Editorial, Madrid (1981). ISBN 84-206-2286-9

* Hofstadter, Douglas R. 1979: ''[[Gödel, Escher, Bach|Gödel, Escher, Bach: un Eterno y Grácil Bucle]]''. TusQuets editores, tercera edició (1989), Barcelona. ISBN 84-7223-459-2

* Ernest Nagel, James Roy Newman, Douglas R. Hofstadter: ''Gödel's Proof'', edició revisada (2002). ISBN 0-8147-5816-9.

 

{{1000 Ciència}}

 

{{ORDENA:Teorema D'Incompletesa De Godel}}

[[Categoria:Teoremes matemàtics|Incompletesa de Godel]]

[[Categoria:Lògica]]