Teorema d'incompletesa de Gödel

De Viquipèdia

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:

En qualsevol formalització consistent de les matemàtiques que sigui el bastant fort per definir el concepte de nombres naturals, es pot construir una afirmació que ni es pot demostrar ni es pot refutar dins d'aquest sistema.

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 malinterpretar-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 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:

Cap sistema consistent es pot usar per demostrar-se a sí mateix.

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.

Taula de continguts 1 Significat dels teoremes de Gödel 2 Exemples d'afirmacions indecidibles 3 Malentesos en torn als teoremes de Gödel 4 Discussió i implicacions 5 Esbós de demostració per al primer teorema 6 Esbós de demostració del segon teorema 7 Vegeu també 8 Enllaços externs i referències

[edita] 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 que 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).

Per a poder realitzar aquest procés es necessita saber quins són aquests axiomes. Es pot partir d'un conjunt finit d'axiomes, com en la geometria euclidiana, o més en general es pot permetre un nombre infinit d'axiomes que donada una afirmació es pugui verificar mecànicament si és un axioma. Encara que pugui semblar estrany l'ús d'un nombre infinit d'axiomes, això es fa habitualment amb els nombres naturals, els axiomes de Peano.

El primer teorema d'incompletesa de Gödel demostra que qualsevol sistema que permeti definir els nombres naturals és necessàriament incomplet: conté afirmacions que ni es poden demostrar ni refutar.

L'existència d'un sistema incomplet no és en sí particularment sorprenent. Per exemple, si s'elimina el postulat de paral·lelisme de la geometria euclidiana s'obté un sistema incomplet. Un sistema incomplet pot significar que simplement no s'han descobert tots els axiomes necessaris.

El que va mostrar Gödel és que en la majoria de casos, com en la teoria de nombres o en l'anàlisi real, mai es poden descobrir el conjunt complet d'axiomes. Cada cop que s'afegeixi un nou axioma sempre n'hi haurà un altre que quedi fora.

També es pot afegir un conjunt infinit d'axiomes. Per exemple, totes les afirmacions certes sobre els nombres naturals, però aquesta llista no serà un conjunt recursiu. Donada una afirmació qualsevol, no hi haurà forma de saber si és un axioma en el sistema o no. Donada una prova, no hi haurà una manera general de verificar que aquesta prova és vàlida.

El teorema de Gödel té una altre interpretació en el context de la informàtica. En lògica de primer ordre, els teoremes són recursivament enumerables: es pot construir un programa d'ordinador que acabarà per donar una demostració vàlida. Tot i això, no compleixen la propietat més forta de ser un conjunt recursiu: no es pot construir un programa que donada una afirmació qualsevol determini si aquesta és certa o no.

Molts lògics pensen que els teoremes d'incomplitud de Gödel van donar un cop fatal al programa de formalització de Hilbert que apuntava a un formalisme matemàtic universal. La postura acceptada generalment és que fou el segon teorema el que va donar aquest cop. Alguns, però, pensen que va ser el primer teorema, i inclús hi ha que pensa que cap d'ells ho va fer.

[edita] Exemples d'afirmacions indecidibles

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

El treball combinat de Gödel i Paul Cohen ha donat a conèixer exemples concrets d'afirmacions indecidibles: tant els axiomes d'elecció com la hipòtesis del continu són indecidibles en l'axiomatització estàndard de teoria de conjunts. Aquests resultats no requereixen del teorema d'incomplitud.

Al 1936, Alan Turing va demostrar que el problema de la parada (la qüestió de si una màquina de Turing s'aturarà al introduir unes dades) és indecidible. Més tard, aquest resultat es va generalitzar en el camp de les funcions recursives en el teorema de Rice que demostra que tots els problemes de decisió que no són trivials són indecidibles en un sistema que sigui Turing-complet.

Al 1973, es va demostrar que el problema de Whitehead en teoria de grups és indecidible en la teoria estàndard de grups. Al 1977, Kirby, Paris i Harrington demostraren que una afirmació en combinatòria, una versió del teorema de Ramsey, és indecidible en l'axiomatització de l'aritmètica donada pels axiomes de Peano, però es pot demostrar certa en el sistema més ampli que és la teoria de conjunts. L'algorisme de Kruskal, que té implicacions en informàtica, també és indecidible a partir dels axiomes de Peano però demostrable en teoria de conjunts. Així mateix, el teorema de Goodstein és una afirmació relativament simple sobre els nombres naturals que és indecidible en l'aritmètica de Peano.

Gregory Chaitin va produir afirmacions indecidibles en teoria algorísmica de la informació i de fet demostrar el seu propi teorema d'incomplitud dins aquest context.

Un dels primers problemes dels que es va sospitar que era indecidible fou el problema d'equivalència d'enunciats sobre grups, proposat inicialment per Max Dehn l'any 1911, el qual estableix que existeix un grup representat de forma finita per al qual no existeix algorisme que decideixi si dos formules que només parlen de propietats d'aquells grups són equivalents. El caràcter indecidible d'aquest enunciat no fou demostrat fins al 1952.

[edita] Malentesos en torn als teoremes de Gödel

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

1. El teorema no implica que tot sistema axiomàtic interessant sigui incomplet. Per exemple, la geometria euclidiana es pot axiomatitzar de forma que sigui un sistema complet. De fet, els axiomes originals d'Euclides són casi una axiomatització completa. Els axiomes que falten expressen propietats tant òbvies que va ser necessari l'aparició de la idea de prova formal per trobar-les a faltar. Tot i això, inclús en un sistema complet com el de la geometria euclidiana hi haurà construccions impossibles (triseció de l'angle, quadratura del cercle).
2. El teorema només s'aplica a sistemes que permetran definir els nombres naturals com un conjunt. No n'hi ha prou que el sistema contingui els nombres naturals. A més, ha de ser capaç d'expressar el concepte «x és un nombre natural» usant els axiomes i la lògica de primer ordre. Hi ha multitud de sistemes que contenen els nombres naturals i són complets. Per exemple, tant els nombres reals com els nombres complexos tenen axiomatitzacions completes.

[edita] Discussió i implicacions

Els resultats d'incompletesa afecten a la filosofia de les matemàtiques, particularment als punts de vista tals com el formalisme, que usa la lògica formal per definir els seus principis. Es pot parafrasejar el primer teorema dient “mai es podrà trobar un sistema axiomàtic que sigui capaç de demostrar totes les veritats matemàtiques i ninguna falsedat.”

Per altre banda, des de una perspectiva estrictament formalista aquesta paràfrasis es considera sense significat perquè pressuposa que la “veritat” i la “falsedat” matemàtiques estan ben definides en un sentit absolut, en lloc de ser relatives a cada sistema formal.

La següent reformulació del segon teorema és encara més inquietant pels fonaments de les matemàtiques:

si un sistema axiomàtic es pot demostrar que és consistent a partir de sí mateix, llavors és inconsistent.

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).

En principi, els teoremes de Gödel encara deixen alguna esperança: podria ser possible produir un algorisme general per una afirmació donada que determini si és decidible o no, permetent als matemàtics evitar completament els problemes indecidibles. Però la reposta negativa al Entscheidungsproblem demostra que no existeix tal algorisme.

És de notar que els teoremes de Gödel només són aplicables a sistemes axiomàtics suficientment forts. Aquest terme significa que la teoria conté la suficient aritmètica per portar a terme les instruccions de codificació requerides per la prova del primer teorema d'incompletesa. Esencialment, tot el que se li exigeix són alguns fets bàsics sobre l'addicció i la multiplicació tal com per exemple es formalitzen en l'aritmètica Q de Robinson. Hi ha sistemes axiomàtics inclús més dèbils que són consistents i complets, com per exemple l'aritmètica de Presburger que demostra totes les afirmacions de primer ordre certes aplicant només la suma.

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.

Un altre exemple d'una especificació d'una teoria en la que el primer teorema de Gödel no és aplicable es pot construir de la següent manera: ordenem totes les possibles declaracions sobre els nombres naturals, primer per la seva longitud i desprès en ordre lexicogràfic; comencem amb un sistema axiomàtic incialment igual als axiomes de Peano, repassem la llista de declaracions una a una, i, si la declaració actual no es pot demostrar ni refutar a partir de l'actual sistema d'axiomes, llavors l'afegim a la llista. Això crea un sistema que és complet, consistent i suficientment potent, però no és recursivament enumerable.

Gödel mateix només va demostrar una versió dels teoremes exposats a dalt, que és tècnimanet una mica més dèbil, la primera demostració de les versions descrites anteriorment fou donada per J. Barkley Rooser al 1936.

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:

p = «Aquesta declaració no es pot provar.»

Com a tal, es pot veure una versió moderna de la paradoxa del mentider. Al contrari de la declaració del mentider, p no es refereix directament a sí mateixa; la interpretació de dalt només es pot “veure” des de fora el sistema formal.

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.

Roger Penrose afirma que aquesta (presunta) diferencia entre el que es pot provar mecànicament i el que els humans poden veure com a cert demostra que la intel·ligència humana no és mecànica en la seva naturalesa. També J.R. Lucas ha atès aquestes reivindicacions.

Aquesta perspectiva no està àmpliament acceptada, perquè tal i 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 que 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 ninguna veritat que estigui fora del sistema. Tot el que sabem és el següent:

O p és indemostrable dins el sistema, o el sistema és incosistent.

Aquesta declaració és facilment demostrable dins el sistema.

Una altre implicació és que el treball de Gödel va motivar Alan Turing (1912-1594) 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.

[edita] Esbós de demostració per al primer teorema

El principal problema en ajuntar l'idea de demostració a dalt mencionada és el següent: per a construir una declaració p que sigui equivalent a “p no es pot demostrar”, p hauria de contenir d'alguna forma una referència a p que pogués donar lloc a una regressió infinita. Describirem a baix l'ingeniós truc de Gödel, que més tard seria usat per Alan Turing per resoldre l'Entscheidungsproblem.

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.

Una forma F(x) que conté exactament una variable lliure x s'anomena una forma declarativa. Tant bon punt com x es reemplaça per un nombre específic, la declaració es transforma en una declaració bona fide, i és o bé demostrable en el sistema o no. Les formes declaratives no són declaracions, i per tant no es poden provar o refutar. Tot i això, cada forma declarativa F(x) té un número de Gödel que denotarem com G(F). La selecció de la variable lliure triada en la fórmula F(x)no és relevant per l'assignació del nombre de Gödel G(F).

Mitjançant l'anàlisi dels axiomes i regles del sistema, es pot escriure una fórmula declarativa P(x) que encarna la idea de x és el nombre de Gödel d'una declaració que pot demostrar-se en el nostre sistema. Formalment, P(x) es pot provar si x és el nombre de Gödel d'una declaració demostrable, i la seva negació es pot provar si no ho és. (Encara que aquesta explicació és adequada per aquest esbós de prova, tècnicament no és completament exacte. Vegeu l'article de Gödel per aquest problema i l'article de Rosser per la resolució. La paraula clau és omega-consistència).

Ara ve el truc: una forma declarativa F(x) es denomina auto-indemostrable si la forma F, aplicada al seu propi nombre de Gödel, no és demostrable. Aquest concepte es pot definir formalment, i es pot construir una forma declarativa SU(z) la interpretació de la qual és que z és el nombre de Gödel d'una forma declarativa auto-indemostrable. Formalment, SU(z)es defineix com: z = G(F) per alguna forma particular F(x), i y és el nombre de Gödel de la declaració F(G(F)), i . Ara la declaració desitjada p, que fou mencionada abans, es pot definir com:

p = SU(G(SU)).

Intuïtivament, quan ens preguntem si p és cert, preguntem “És la propietat de ser auto-indemostrable ella mateixa auto-indesmotrable?”. Això és reminiscent de la paradoxa del barber sobre un barber que afaita a totes les persones del poble que no s'afaiten a sí mateixes: s'afaita a sí mateix?

Ara assumim que el nostre sistema axiomàtic és consistent.

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

Si la negació de p = SU(G(SU)) fos probable, llavors per definició de SU això significaria que z = G(SU) no és el nombre de Gödel d'una forma auto-indemostrable, el que implica que SU no és auto-indemostrable. Per definició d'auto-indemostrable, concluim que SU(G(SU)) és demostrable, i per tant p és demostrable. De nou una contradicció. Això deixa de manifesta que tampoc la negació de p pot ser demostrable.

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

[edita] Esbós de demostració del segon teorema

Sigui p 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 p no és demostrable. La prova d'aquesta implicació es pot formalitzar en el propi sistema, i per tant, l'afirmació “p no és demostrable”, o “no P(p)” es poden demostrar en el sistema.

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

[edita] Vegeu també

• Consistència lògica
• Auto referència
• Logicisme
• Ments, Màquines y Gödel
• Teorema de Löb

[edita] Enllaços externs i referències

• Kurt Gödel: «Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I.», Monatshefte für Mathematik und Physik, 38 (1931), pp. 173-198. (anglès)

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

• B. Rosser: «Extensions of some theorems of Gödel and Church», Journal of Symbolic Logic, 1 (1936), N1, pp. 87-91
• Kārlis Podnieks: Around Goedel's Theorem. Enllaç al text. (anglès)
• Hofstadter, Douglas R. 1979: 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 0814758169.
• Hilbert's second problem. (anglès)
• Norbert Domeisen: Logik der Antinomien, Berna: Peter Lang. 142 S. 1990. (ISBN 3-261-04214-1), Zentralblatt MATH (anglès)