miniatura|Kurt Gödel a 19 anys, cinc anys abans de la demostració dels teoremes. 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 prou forta 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, més enllà de les matemàtiques, però és un dels pitjor compresos. És un teorema de lògica formal; i, com aital, es pot malinterpretar molt fàcilment. 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 dels teoremes de Gödel»).
El segon teorema, que es demostra formalitzant part de la demostració del primer teorema dins el mateix sistema, afirma:
Cap sistema consistent es pot usar per demostrar-se a si 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.
Significat dels teoremes de Gödel Els teoremes de Gödel són 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 qual 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).
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 o no é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 si 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 altra 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'incompletesa 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 qui pensa que cap d'ells ho va fer.
Exemples d'afirmacions indecidibles L'existència d'una afirmació indecidible dins d'un sistema formal no és en si 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òtesi del continu són indecidibles en l'axiomatització estàndard de teoria de conjunts. Aquests resultats no requereixen el teorema d'incompletesa.
El 1936, Alan Turing va demostrar que el problema de la parada (la qüestió de si una màquina de Turing s'aturarà en introduir-hi 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.
El 1973, es va demostrar que el problema de Whitehead en teoria de grups és indecidible en la teoria estàndard de grups. El 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'incompletesa dins aquest context.
Un dels primers problemes dels quals 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 dues fórmules 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.
Malentesos entorn dels 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:
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 gairebé una axiomatització completa. Els axiomes que falten expressen propietats tan òbvies que va ser necessària 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 (trisecció de l'angle, quadratura del cercle, etc.). 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.
Discussió i implicacions Els resultats d'incompletesa afecten 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 cap falsedat.»
Per altra banda, des d'una perspectiva estrictament formalista, aquesta paràfrasi 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 si 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 si 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: seria 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 resposta 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. Essencialment, tot el que se li exigeix són alguns fets bàsics sobre l'addició 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 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 qual 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 inicialment igual als axiomes de Peano, repassem la llista de declaracions d'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ècnicament una mica més dèbil, la primera demostració de les versions descrites anteriorment fou donada per J. Barkley Rooser el 1936.
En essència, la prova del primer teorema consistent a construir una declaració p dintre un sistema formal axiomàtic al qual se li pot donar la següent interpretació meta-matemàtica:
«Aquesta declaració no es pot provar.»