Teorema d'incompletesa de Gödel

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.

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.

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.

Donat que el primer teorema de Gödel és tan famós, ha donat origen a multitud de malentesos. Aquí en 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 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.).
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.

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:

${\displaystyle 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 si 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 és), 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 altra sentència de Gödel per a la teoria ampliada.

Roger Penrose afirma que aquesta (presumpta) 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 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:

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

Aquesta declaració és fàcilment demostrable dins el sistema.

Una altra 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, al 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.

El principal problema en ajuntar la 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. Descriurem a baix l'enginyó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 nostre 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é és possible raonar sobre fórmules.

Una forma ${\displaystyle F(x)}$ que conté exactament una variable lliure ${\displaystyle x}$ s'anomena una forma declarativa. Tan bon punt com ${\displaystyle 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 ${\displaystyle F(x)}$ té un nombre de Gödel que denotarem com ${\displaystyle G(F)}$. La selecció de la variable lliure triada en la fórmula ${\displaystyle F(x)}$no és relevant per l'assignació del nombre de Gödel ${\displaystyle G(F)}$.

Mitjançant l'anàlisi dels axiomes i regles del sistema, es pot escriure una fórmula declarativa ${\displaystyle P(x)}$ que encarna la idea de ${\displaystyle x}$ és el nombre de Gödel d'una declaració que pot demostrar-se en el nostre sistema. Formalment, ${\displaystyle P(x)}$ es pot provar si ${\displaystyle x}$ és el nombre de Gödel d'una declaració demostrable, i la seva negació ${\displaystyle {\bar {P}}(x)}$ 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 ${\displaystyle F(x)}$ es denomina auto-indemostrable si la forma ${\displaystyle 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 ${\displaystyle SU(z)}$ la interpretació de la qual és que ${\displaystyle z}$ és el nombre de Gödel d'una forma declarativa auto-indemostrable. Formalment, ${\displaystyle SU(z)}$es defineix com: ${\displaystyle z=G(F)}$ per alguna forma particular ${\displaystyle F(x)}$, i ${\displaystyle y}$ és el nombre de Gödel de la declaració ${\displaystyle F(G(F))}$, i ${\displaystyle {\bar {P}}(y)}$. Ara la declaració desitjada ${\displaystyle p}$, que fou mencionada abans, es pot definir com:

${\displaystyle p=SU(G(SU)).}$

Intuïtivament, quan ens preguntem si ${\displaystyle 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 si mateixes: s'afaita a si mateix?

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

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

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

De manera que l'afirmació ${\displaystyle p}$ ni es pot provar ni refutar en el nostre sistema.

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

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

Les conclusions dels teoremes de Gödel només estan demostrades per aquelles teories formals que satisfan les hipòtesis necessàries. No tots els sistemes axiomàtics satisfan aquestes hipòtesis, encara que incloguin els nombres naturals com a subconjunt. Per exemple, existeixen axiomatitzacions de la geometria euclidiana, dels cossos tancats reals, o de l'aritmètica en què la multiplicació no és demostrable que sigui total; cap d'aquests exemples satisfà les hipòtesis dels teoremes de Gödel. El fet clau és que aquestes axiomatitzacions no són prou expressives per definir el conjunt dels nombres naturals o per desenvolupar les propietats bàsiques dels nombres naturals. Pel que fa al tercer exemple, Dan Willard^[1] ha estudiat molts sistemes febles de l'aritmètica que no satisfan les hipòtesis del segon teorema d'incompletesa, i que són consistents i capaços de demostrar la seva pròpia consistència.

Els teoremes de Gödel només es poden aplicar a teories generades efectivament (és a dir, enumerables recursivament). Si tots els enunciats vertaders sobre nombres naturals es prenen com a axiomes, llavors aquesta teoria és una extensió consistent i completa de l'aritmètica de Peano per la qual no es pot aplicar cap dels teoremes de Gödel, perquè aquesta teoria no és enumerable recursivament.

El segon teorema d'incompletesa només demostra que la consistència de certes teories no es pot demostrar a partir dels axiomes d'aquestes pròpies teories. No demostra que la consistència no pugui ser demostrada a partir d'un altre conjunt (consistent) d'axiomes. Per exemple, la consistència de l'aritmètica de Peano es pot demostrar dins la teoria de conjunts de Zermelo-Fraenkel amb l'axioma de l'elecció (ZFC), o també dins teories de l'aritmètica augmentades amb la inducció transfinita, com en la demostració de consistència de Gentzen.

El teorema d'incompletesa està íntimament lligat a diversos resultats sobre conjunts indecidibles en teoria de la computabilitat.

Stephen Cole Kleene^[2] va presentar una demostració del teorema d'incompletesa de Gödel que emprava alguns resultats bàsics de teoria de la computabilitat. Un d'aquests resultats diu que el problema de la parada és indecidible: no existeix cap programa d'ordinador que pugui determinar correctament, donat un programa P com a entrada, si P s'aturarà quan rebi una determinada entrada. Kleene va demostrar que l'existència d'una teoria de l'aritmètica efectiva i completa, dotada de certes propietats de consistència, faria que el problema de la parada fos decidible, la qual cosa porta a una contradicció. Aquest mètode de demostració també ha estat presentat per Shoenfield,^[3] Charlesworth^[4] i Hopcroft i Ullman.^[5]

Franzén explica com es pot aplicar la solució de Matiyasevich al desè Problema de Hilbert per tal d'obtenir una demostració del primer teorema de Gödel.^[6] Matiyasevich demostrà que no hi ha cap algorisme que, donat un polinomi multivariant ${\displaystyle p(x_{1},x_{2},\ldots ,x_{k})}$ a coeficients enters, determini si existeix una solució entera per l'equació ${\displaystyle p=0}$. Com que els polinomis a coeficients enters, i els mateixos nombres enters, es poden expressar directament en el llenguatge de l'aritmètica, si una equació polinòmica entera ${\displaystyle p=0}$ té solució entera, llavors qualsevol teoria de l'aritmètica T suficientment forta pot demostrar-ho. És més, si la teoria T és ω-consistent, llavors mai no podrà demostrar que l'equació té solució si de fet no en té. Així, si T fos completa i ω-consistent, seria possible determinar de forma algorísmica si una equació polinòmica té alguna solució, només enumerant demostracions de T fins que es trobés "p té una solució" o bé "p no té cap solució", la qual cosa contradiu el teorema de Matiyasevich. Addicionalment, per a qualsevol teoria consistent T generada efectivament, és possible generar efectivament un polinomi multivariant p sobre els enters tal que l'equació ${\displaystyle p=0}$ no tingui solucions enteres, però no es pot demostrar dins T la falta de solucions.^[7][8]

Smoryński^[9] demostrà com es pot emprar l'existència de conjunts recursivament separables per demostrar el primer teorema d'incompletesa. Sovint aquesta demostració s'amplia per mostrar que els sistemes com l'aritmètica de Peano són essencialment indecidibles.^[2]

El teorema d'incompletesa de Chaitin proporciona un mètode diferent per generar enunciats independents, basat en la complexitat de Kolmogórov. De la mateixa manera que la demostració de Kleene que hem vist abans, el teorema de Chaitin només aplica per teories que tenen la propietat addicional de què tots els seus axiomes són certs en el model estàndard dels nombres naturals. El teorema d'incompletesa de Gödel es diferencia perquè es pot aplicar a teories consistents en les quals existeixen enunciats que són falsos en el model estàndard; aquestes teories es coneixen amb el nom de ω-inconsistents.

Després que Gödel va publicar la seva demostració del teorema de completesa en la seva tesi doctoral el 1929, va canviar els seus esforços cap a un segon problema, a fi d'aconseguir la seva habilitació. El seu objectiu inicial era obtenir una solució afirmativa pel segon Problema de Hilbert.^[10] En aquella època, les teories dels nombres naturals i reals semblants a una aritmètica de segon ordre eren conegudes com a "anàlisi", mentre que les teories que només tractaven els nombres naturals eren conegudes com a "aritmètica".

Gödel no era la primera persona que treballava en el problema de consistència. Wilhelm Ackermann ja va publicar una demostració (errònia) de la consistència de l'anàlisi en 1925, en la qual intentava emprar el mètode d'ε-substitució, desenvolupat originàriament per Hilbert. Aquell mateix any, John von Neumann va aconseguir corregir la demostració per a una teoria de l'aritmètica sense axiomes d'inducció. El 1928, Ackermann comunicà a Bernays una demostració modificada; aquesta nova versió va portar Hilbert a anunciar que creia que el 1929 s'hauria demostrat la consistència de l'aritmètica, i que li seguiria una demostració de la consistència de l'anàlisi. Després que la publicació dels teoremes d'incompletesa van mostrar que la demostració modificada d'Ackermann havia de ser errònia, von Neumann va crear un exemple concret que mostrava que la seva tècnica principal no era robusta.^[11][12]

En el decurs de la seva recerca, Gödel va descobrir que, encara que un enunciat que afirma la seva falsedat porta a una contradicció, un enunciat que afirma la seva pròpia indemostrabilitat no ho fa. En particular, Gödel era conscient del resultat actualment conegut com a teorema d'indefinibilitat de Tarski, encara que mai no el va publicar. Gödel anuncià el seu primer teorema d'incompletesa a Carnap, Feigel i Waismann el 26 d'agost de 1930. Tots quatre van assistir a una conferència a Königsberg la setmana següent.

La conferència de Königsberg de 1930 va ser una trobada de tres societats acadèmiques, a la qual van assistir molts dels lògics capdavanters de l'època. Carnap, Heyting i von Neumann van dissertar sobre la filosofia matemàtica de la lògica, l'intuïcionisme i el formalisme, respectivament.^[13] La conferència també incloïa una intervenció de Hilbert, en la que anunciava la seva retirada a la Universitat de Göttingen. Hilbert va incloure en el seu discurs la seva creença que qualsevol problema matemàtic pot ser resolt. Va finalitzar el seu discurs dient:

Ràpidament, aquest discurs esdevingué un resum del pensament de Hilbert sobre les matemàtiques (les seves sis paraules finals, "Wir müssen wissen. Wir werden wissen!", foren usades com a epitafi de Hilbert el 1943). Encara que es creu que Gödel assistí al discurs de Hilbert, mai no es van trobar cara a cara.^[13]

Gödel va anunciar el seu primer teorema d'incompletesa en una discussió durant una taula rodona en el tercer dia de la conferència. L'anunci va tenir poca repercussió, tret de von Neumann, que va portar Gödel a part per xerrar en privat. Aquell mateix any, i amb independència de Gödel, von Neumann va obtenir una demostració del segon teorema d'incompletesa, cosa que va comunicar a Gödel en una carta datada el 20 de novembre de 1930.^[13] Gödel va demostrar independentment el segon teorema d'incompletesa i el va remetre manuscrit al Monatshefte für Mathematik el 17 de novembre de 1930.

L'article de Gödel fou publicat en el Monatshefte el 1931 amb el títol Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I (en alemany, «Sobre proposicions formalment indecidibles en els Principia Mathematica i sistemes relacionats I»). Com suggereix el títol, Gödel va planejar originalment la publicació d'una segona part de l'article, però mai no el va arribar a escriure.

Gödel va oferir una sèrie de conferències sobre els seus teoremes a Princeton en 1933-1934 a una audiència que incloïa Church, Kleene i Rosser. En aquesta època, Gödel va copsar que la propietat clau que requerien els seus teoremes és que la teoria ha de ser efectiva (en aquell temps, hom usaba el terme "recursiva general"). Rosser demostrà el 1936 que la hipòtesi de ω-consistència, que era una part integral de la demostració original de Gödel, es podia substituir per la de consistència simple, sempre que l'afirmació de Gödel es canviés d'una forma adient. Aquests desenvolupaments van donar lloc a la forma actual dels teoremes d'incompletesa.

Gentzen va publicar la seva demostració de consistència per l'aritmètica de primer ordre el 1936.^[14] Hilbert va acceptar aquesta demostració com a "finita", encara que (com ja havia demostrat el teorema de Gödel) no es pot formalitzar en el marc del mateix sistema aritmètic que s'està demostrant que sigui consistent.

Aviat es va fer palès l'impacte dels teoremes d'incompletesa en el programa de Hilbert. Bernays va incloure una demostració completa dels teoremes d'incompletesa en el segon volum dels Grundlagen der Mathematik,^[15] juntament amb resultats addicionals d'Ackermann sobre el mètode d'ε-substitució i amb la demostració de consistència de Gentzen de l'aritmètica. Aquesta fou la primera publicació completa del segon teorema d'incompletesa.

Paul Finsler (1926) emprà una versió de la paradoxa de Richard per construir una expressió que resultava ser falsa però indemostrable en un cert marc informal de la seva creació.^[16] Gödel no coneixia aquest article en el moment que va demostrar els teoremes d'incompletesa. Finsler va escriure a Gödel el 1931 per informar-li d'aquest article, ja que creia que tenia prou rellevància per constituir un teorema d'incompletesa. Els mètodes de Finsler no tenien una base de demostrabilitat formalitzada, i només tenien una similitud superficial amb l'obra de Gödel.^[17] Gödel va llegir l'article, però va trobar que tenia deficiències profundes, i en la seva resposta a Finsler va fer constar la seva preocupació per la falta de rigor.^[18]

El setembre del 1931, Ernst Zermelo va escriure a Gödel per anunciar-li el que considerava una "errada essencial" en l'argument de Gödel.^[13] Al mes d'octubre, Gödel va contestar amb una carta de 10 pàgines.^[13][19] No obstant això, Zermelo no va desistir, i va publicar les seves crítiques com "un paràgraf força mordaç sobre el seu jove competidor".^[20] Gödel va decidir que no valia la pena continuar amb la discussió, i Carnap hi va estar d'acord.^[21] Gran part de l'obra posterior de Zermelo va estar relacionada amb lògiques més fortes que les de primer ordre, amb les quals esperava mostrar la consistència i la categoricitat de les teories matemàtiques.

Ludwig Wittgenstein va escriure diversos passatges sobre els teoremes d'incompletesa que foren publicats de manera pòstuma en la seva obra de 1953 Bemerkungen über die Grundlagen der Mathematik^[22] (en català, «Observacions sobre els fonaments de la matemàtica»; en anglès, «Remarks on the Foundations of Mathematics»). Gödel fou membre del Cercle de Viena durant el període en el qual la filosofia lingüística i el Tractatus Logico-Philosophicus de Wittgenstein dominaven el pensament del cercle. Els escrits continguts al Nachlass (en català, «el llegat») de Gödel posen de manifest la creença que Wittgenstein va malinterpretar intencionadament les seves idees.

Diversos comentaristes interpreten que, efectivament, Wittgenstein va malinterpretar Gödel,^[23] encara que Juliet Floyd i Hilary Putnam,^[24] així com Graham Priest,^[25] han aportat lectures que argumenten que la majoria de comentaris malinterpreten Wittgenstein. En el moment de la publicació, Bernays, Dummett i Kreisel van escriure articles per separat sobre les observacions de Wittgenstein, que eren totes extremadament negatives.^[26] La unanimitat d'aquestes crítiques va fer que les observacions de Wittgenstein sobre els teoremes d'incompletesa tinguessin poc impacte en la comunitat dels lògics. El 1972, Gödel va afirmar: "Has Wittgenstein lost his mind? Does he mean it seriously?"^[27] (en anglès, «És que Wittgenstein ha perdut el cap? De debò vol dir això?») Posteriorment va escriure a Karl Menger que els comentaris de Wittgenstein demostraven una mala interpretació intencionada dels teoremes d'incompletesa:

D'ençà de la publicació del Nachlass de Wittgenstein el 2000, han aparegut diversos articles sobre filosofia que avaluen si les crítiques originals de les observacions de Wittgenstein estaven justificades. Floyd i Putnam^[24] asseguren que Wittgenstein tenia un coneixement més complet del teorema d'incompletesa del que es cregué amb anterioritat. Estan particularment preocupats amb la interpretació d'un enunciat de Gödel per una teoria ω-inconsistent, afirmant de fet "No sóc demostrable", ja que la teoria no té models en els quals la demostració de predicats correspongui de fet a la demostració real. Rodych^[23] afirma que la seva interpretació de Wittgenstein no està justificada històricament, mentre Berto^[26] explora la relació entre l'obra de Wittgenstein i les teories de lògica paraconsistent.

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

• Kurt Gödel: «Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Arxivat 2006-07-05 a Wayback Machine.», 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 84-206-2286-9

• 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 0-8147-5816-9.
• Domeisen, Norbert. Logik der Antinomien (en alemany). Berna: Peter Lang, 1990, p. 142 S.. ISBN 3-261-04214-1 [Consulta: 4 febrer 2007].  Arxivat 2004-04-12 a Wayback Machine.

• David Hilbert. «Hilbert's second problem» (en anglès). Clark University. [Consulta: 26 agost 2013].