Hver var Kurt Gödel og hvert var framlag hans til stærðfræðinnar?

Nafn þitt

Netfang þitt

Netfang móttakanda

Ruslpóstvörn =

Svar

Hver var Kurt Gödel og hvert var framlag hans til stærðfræðinnar?
Kurt Gödel hefur verið kallaður mesti rökfræðingur síðan á dögum Aristótelesar. Gödel-setningin svonefnda, sem hann sannaði á tuttugasta og fimmta aldursári, er ein frægasta niðurstaða stærðfræðinnar: Hún er þekkt langt út fyrir raðir stærðfræðinga, og það er sárasjaldgæft. Hún er kannski líka sú stærðfræðiniðurstaða sem hefur verið misskilin hvað oftast og misnotuð í vafasömum röksemdafærslum um hluti sem hún hefur ekkert um að segja.

Kurt Friedrich Gödel fæddist 28. apríl 1906 í Brünn, sem nú heitir Brno, í Móravíu, sem þá var hluti af austurrísk-ungverska keisaradæminu en nú er hluti af Tékklandi. Frá fjögurra ára aldri var hann kallaður der Herr Warum (herra Hversvegna) í fjölskyldu sinni vegna þrálátra spurninga hans um allt milli himins og jarðar. Átján ára hóf Gödel nám við háskólann í Vínarborg. Fyrstu eitt eða tvö árin lagði hann stund á eðlisfræði, en söðlaði um og nam stærðfræði fyrir áhrif frá talnafræðingnum Philipp Furtwängler (1869-1940), sem hann sagði seinna að hefði haldið frábærustu fyrirlestra sem hann hefði heyrt.

Fullkomleikasetningin og ófullkomleikasetningarnar

Leiðbeinandi Gödels í doktorsnámi var Hans Hahn (1879-1934), sem var mikill áhugamaður um rökfræði án þess að stunda hana beinlínis (nú á dögum er hans oftast minnst fyrir svokallaða Hahn-Banach-setningu). Í doktorsritgerð sinni (1929) sannaði Gödel merka niðurstöðu, sem er kölluð fullkomleikasetning Gödels. Árið 1931 birti Gödel síðan ófullkomleikasetningar sínar tvær, en frá þeirri fyrri hafði hann skýrt á alþjóðlegri ráðstefnu árið áður. Með „Gödel-setningunni“ er oftast átt við fyrri ófullkomleikasetninguna, en stundum er báðum ófullkomleikasetningunum slengt saman í eina.

Í stærðfræði er orðið „setning“ notað í tæknilegri merkingu og merkir ávallt sannaða niðurstöðu. Setningar Gödels eru niðurstöður í stærðfræðilegri rökfræði, fræðigrein sem fjallar um stærðfræðilegar röksemdafærslur og notar til þess stærðfræðilegar aðferðir. Allar eru setningarnar um formlegar kenningar (sem eru líka stundum kallaðar formleg kerfi). Formleg kenning er lauslega orðað nákvæm stærðfræðileg útgáfa af því hvernig röksemdafærslur eru notaðar í einhverri tiltekinni grein stærðfræðinnar. Nánar tiltekið er formleg kenning búin til úr þrennu:

1. Formlegu máli, sem hefur nákvæmlega tiltekið strafróf (búið til úr bókstöfum og sérstökum táknum) og nákvæmlega tilteknar myndunarreglur sem segja hvernig búa má til fullyrðingar kenningarinnar, kallaðar yrðingar til styttingar;
2. rökreglum, sem leyfa okkur að segja að yrðing af einhverri tiltekinni gerð sé afleiðing af öðrum yrðingum af einhverjum tilteknum gerðum;
3. tilteknum frumforsendum, sem kallast frumsendur til styttingar; það eru yrðingar á formlega málinu sem eru þannig tilgreindar að við getum í endanlega mörgum skrefum gengið úr skugga um hvort einhver tiltekin yrðing formlega málsins sé frumsenda eða ekki.

Sönnun í formlegu kenningunni er listi af yrðingum á formlega málinu þannig að hver yrðing á listanum sé annaðhvort frumsenda eða afleiðing af yrðingum framar á listanum samkvæmt einhverri rökreglu. Yrðing er sannanleg (og kölluð setning kenningarinnar) ef hún er síðasta yrðingin á slíkum lista; hún er afsannanleg ef neitun hennar er sannanleg. Kenning fyrstu stéttar er (í grófum dráttum sagt) formleg kenning þannig að rökreglur hennar séu „allar venjulegar rökreglur“.

Yrðingar í kenningu fyrstu stéttar eru fullyrðingar um einhverja ótiltekna hluti; segjum til dæmis yrðingin „a + b = c“. Nú getum við prófað hvort slík yrðing er sönn um einhverja tiltekna hluti eða ekki; til dæmis er þessi tiltekna yrðing sönn ef a, b, c eru tölurnar 1, 2, 3, því að 1 + 2 = 3, en ósönn ef a, b, c eru tölurnar 2, 3, 4, því að 2 + 3 er ekki talan 4. Ef við höfum mengi af tilteknum hlutum með tilteknum venslum sín á milli sem samsvara táknunum í kenningunni (eins og táknunum „+“ og „=“ í dæminu) og allar frumsendur kenningarinnar segja satt um þessa hluti, þá segjum við að mengið ásamt venslunum sé líkan fyrir kenninguna. Þá segja líka allar setningar kenningarinnar satt um hlutina í líkaninu, því að afleiðing af sönnum yrðingum samkvæmt venjulegum rökreglum er aftur sönn yrðing. Á hinn bóginn geta verið til yrðingar sem eru sannar fyrir hlutina í líkaninu, en eru þó ekki setningar í kenningunni. Fullkomleikasetning Gödels segir hins vegar þetta:

Yrðing sem er sönn fyrir hlutina í sérhverju líkani formlegrar kenningar fyrstu stéttar er sannanleg og þar með setning kenningarinnar.

Þetta má túlka þannig að venjulegu rökreglurnar myndi „fullkomið“ kerfi af reglum: Þær nægja til að sanna allt það sem er satt í sérhverju líkani, og við þurfum því ekki á fleiri reglum að halda.

Orðið „fullkominn“ er notað í allt annarri merkingu þegar kemur að ófullkomleikasetningunum. Við segjum að kenning fyrstu stéttar sé fullkomin ef við getum annaðhvort sannað eða afsannað sérhverja yrðingu á máli kenningarinnar. Við segjum líka að kenning fyrstu stéttar sé samkvæm ef hún leiðir ekki til mótsagnar; með öðrum orðum ef ekki er bæði unnt að sanna einhverja tiltekna yrðingu og neitun hennar í kenningunni. Fyrri ófullkomleikasetning Gödels segir þetta:

Kenning fyrstu stéttar sem er samkvæm og getur lýst einföldum reikningi með náttúrlegum tölum getur ekki verið fullkomin: Ávallt er til yrðing á máli kenningarinnar sem hvorki er unnt að sanna né afsanna innan kenningarinnar.

Krafan um að kenningin geti lýst einföldum reikningi með náttúrlegum tölum þýðir meðal annars að til sé á málinu sérstakt tákn fyrir sérhverja gefna náttúrlega tölu (til dæmis gæti „1 + 1 + 1 + 1“ verið sérstakt tákn fyrir töluna 4) og að við getum í kenningunni sett fram yrðingar á borð við þessar:

• 2 + 2 = 4;
• sérhver náttúrleg tala er annaðhvort jöfn tala eða oddatala;
• talan x er margfeldi tölunnar 2 og oddatölu;
• náttúrlega talan x gengur upp í náttúrlegu tölunni y.

Seinni ófullkomleikasetning Gödels segir þetta:

Ef kenning fyrstu stéttar er samkvæm og getur lýst einföldum reikningi með náttúrlegum tölum, þá er ekki unnt að sanna innan kenningarinnar sjálfrar að hún sé samkvæm.

Við höfum lýst þessum þremur setningum Gödels eins og þær eru venjulega settar fram nú til dags, en þær hafa verið straumlínulagaðar nokkuð frá upphaflegri gerð. Allar setningarnar þrjár hafa haft gífurleg áhrif á stærðfræðilega rökfræði og raunar gjörbylt þeirri grein stærðfræðinnar. Þær hafa líka breytt heimspekilegum skoðunum manna á eðli stærðfræðinnar, en óhætt er að fullyrða að ekki séu allir á eitt sáttir um hvaða heimspekilegar ályktanir má af þeim draga. Á hinn bóginn hafa þessar setningar Gödels lítil áhrif haft á aðrar greinar stærðfræðinnar.

Sönnun fyrri ófullkomleikasetningarinnar

Í mörgum bókum er reynt að gera fyrri ófullkomleikasetningu Gödels og jafnvel sönnun hennar skiljanlega almennum lesendum. Fáar slíkar skýringar slá þó við innganginum að grein Gödels sjálfs, þar sem hann skýrir meginhugmynd sönnunarinnar á innan við tveimur blaðsíðum. Nú verður gerð tilraun til að lýsa meginhugmyndinni, að mestu í samræmi við formála Gödels, en lesandinn getur hlaupið yfir í næsta hluta svarsins ef honum finnst textinn of tæknilegur.

Fyrir gefna formlega kenningu getum við tölusett (1) öll táknin í stafrófi hennar, (2) allar yrðingar hennar, og (3) alla endanlega lista af yrðingum, með náttúrlegum tölum, svokölluðum Gödel-tölum, þannig að fyrir hverja náttúrlega tölu getum við gengið úr skugga um hvort hún sé slík Gödel-tala, og ef svo er getum við lesið af tölunni hvert af tilvikunum (1), (2) eða (3) sé fyrir hendi og fundið táknið, yrðinguna eða yrðingalistann sem samsvarar tölunni. Hvernig þessi Gödel-tölusetning fer fram skiptir litlu máli; hana má búa til á ýmsa vegu, og til þess þarf aðeins frumatriði úr einfaldri talnafræði. En með tölusetningunni má þýða rökreglur kenningarinnar yfir í reiknireglur fyrir Gödel-tölur yrðinganna sem rökreglurnar fjalla um. Þar sem setja má einfalda reikninga með náttúrlegum tölum fram í kenningunni má búa til yrðingu F(n) sem segir að talan n sé Gödel-tala sannanlegrar yrðingar í kenningunni.

Athugum nú allar þær yrðingar í kenningunni sem eru fullyrðingar um nákvæmlega einn ótiltekinn hlut sem við köllum x; Gödel kallar slíka yrðingu flokkstákn. Fyrir flokkstákn a og náttúrlega tölu n látum við [a;n] vera yrðinguna sem fæst með því að setja sérstaka táknið fyrir náttúrlegu töluna n inn fyrir x í yrðingunni a. Ef til dæmis a er yrðingin „x = x“ og sérstaka táknið fyrir töluna 4 er eins og lýst var hér á undan, þá er [a;4] yrðingin „1 + 1 + 1 + 1 = 1 + 1 + 1 + 1“.

Röðum nú flokkstáknunum í einhverja sérstaka röð, til dæmis stafrófsröð, og tölusetjum þau með náttúrlegum tölum; látum R(n) vera n-ta flokkstáknið. Skilgreinum mengi K af náttúrlegum tölum þannig að talan n sé í menginu K þá og því aðeins að yrðingin [R(n);n] sé ekki sannanleg í kenningunni. Af því sem áður hefur komið fram leiðir að til er flokkstákn S þannig að yrðingin [S;n] segi að talan n sé í menginu K; flokkstáknið S má til dæmis vera yrðingin ¬F(g(x)), þar sem g(x) er Gödel-tala yrðingarinnar [R(x);x], F er yrðingin sem áður var sagt frá og „¬“ táknar neitunina „ekki“. Flokkstáknið S hlýtur að vera eitt af flokkstáknunum í raðaða listanum yfir öll flokkstákn, svo að til er ákveðin tala q þannig að S sé flokkstáknið R(q).

Nú má sjá að yrðingin [R(q);q] er hvorki sannanleg né afsannanleg í kenningunni. Gerum fyrst ráð fyrir að hún sé sannanleg. Þar sem R(q) er yrðingin S er [R(q);q] yrðingin [S;q], svo að þetta þýðir að q er stak í menginu K, og það þýðir aftur að yrðingin [R(q);q] er ekki sannanleg. Ef hins vegar yrðingin [R(q);q] er afsannanleg, með öðrum orðum neitunin ¬[S;q] er sannanleg, þá getur yrðingin [S;q] ekki verið sannanleg (af því að formlega kenningin er samkvæm), og því er q ekki stak í menginu K; en það þýðir að fullyrðingin [R(q);q] er sannanleg. Við fáum því mótsögn í báðum tilvikum. Þar með væri Gödel-setningin sönnuð, að því gefnu að búið væri að fylla upp í öll smáatriðin um hvernig yrðingarnar F(n) og S eru búnar til.

Eins og Gödel benti sjálfur á er þessi röksemdafærsla á yfirborðinu lík svokallaðri þverstæðu lygarans.

Önnur verk Gödels

Sönnun fyrri ófullkomleikasetningarinnar byggist á tölusetningu. Það þarf að vera tryggt að út frá tilteknum tölum megi reikna margvíslega hluti. Til að sýna fram á það fann Gödel upp nýja tegund af föllum, svokölluð rakin föll; gildi þeirra má ávallt reikna út í endanlega mörgum skrefum, og þau eru því reiknanleg. Ýmsir stærðfræðingar, svo sem E. L. Post, A. Church, S. Kleene, J. B. Rosser og A. Turing, settu síðar fram skilgreiningar á því sem þeir vildu kalla reiknanleg föll. Í ljós hefur komið að allar þessar skilgreiningar, þótt ólíkar séu í upphafi, ákvarða sömu föllin, nefnilega rakin föll. Þessi flokkur falla er skiljanlega mikilvægur í tölvunarfræðum.

Gödel ritaði ýmislegt fleira um stærðfræðilega rökfræði, til dæmis um lengd sannana og athyglisverða grein um svonefnda innsæishyggju, en það verður ekki frekar rakið hér. Næst sneri hann sér að mengjafræði. Á 19. öld hafði þýski stærðfræðingurinn Georg Cantor sýnt fram á að óendanleg mengi geta verið misstór, skilgreint fjöldatölur óendanlegra mengja og sýnt að mengi náttúrlegu talnanna hefur lægri fjöldatölu en mengi rauntalnanna. Svokölluð samfellutilgáta Cantors, sem Cantor reyndi árum saman árangurslaust að sanna, segir að engin fjöldatala liggi á milli þessara tveggja. Árið 1938 tókst Gödel að sanna að samfellutilgátan er ekki afsannanleg (út frá venjulegum frumsendum mengjafræðinnar). Árið 1963 sannaði Paul J. Cohen (1934-2007) síðan að samfellutilgátan er ekki heldur sannanleg.

Gödel og Einstein í Princeton árið 1950.

Árið 1940 fluttist Gödel til Bandaríkjanna og fékk stöðu við Institute for Advanced Study í Princeton. Þar dvaldist hann til æviloka. Gödel var einrænn og eignaðist tiltölulega fáa nána vini. Einn af þeim helstu var Albert Einstein. Um árabil sáust þeir ganga saman og ræða sín á milli svo að segja daglega; hélst sú vinátta meðan Einstein lifði. Þrátt fyrir það voru þeir afar ólíkir, bæði að skapgerð og smekk: Einstein tókst ekki að vekja áhuga Gödels á uppáhaldstónskáldum sínum, Beethoven og Mozart (Gödel hlustaði frekar á óperettur og létt lög), og Gödel tókst víst ekki að vekja áhuga Einsteins á uppáhaldskvikmynd sinni, sem hann sá oft, en það var Mjallhvít og dvergarnir sjö. Gödel uppgötvaði lausn á sviðsjöfnum Einsteins (í raun heimslíkan í samræmi við almennu afstæðiskenninguna) sem inniheldur lokaða tímalæga ferla. Í slíkum heimi geta menn hugsanlega ferðast aftur til fortíðar í þeim skilningi að þeir komast aftur á sama stað og tíma og þeir eitt sinn voru.

Eftir að Gödel fluttist til Bandaríkjanna sneri hann sér meir og meir að heimspeki. Hann las mikið um heimspekileg efni — einkum sökkti hann sér niður í rit Leibniz — en hann birti sáralítið á Ameríkuárum sínum. Athygli hefur vakið að meðal handrita sem fundust í fórum Gödels að honum látnum var verufræðileg sönnun á tilvist Guðs í anda Anselms og Leibniz, en skrifuð á formlegu máli háttarökfræðinnar. Gödel mun hafa haft á orði (árið 1970) við hagfræðinginn Oskar Morgenstern (1902-1977) að hann hikaði við að birta sönnunina, því að hann óttaðist að verða bendlaður við guðstrú, en sönnunin hafi verið hrein rökfræðileg athugun til að sýna að slíka sönnun mætti leiða til lykta með viðurkenndum reglum formlegrar rökfræði. En á spurningalista sem Gödel fyllti út árið 1975 (en sendi ekki til baka) svarar hann spurningu um trú sína þannig að hann sé „guðstrúar frekar en algyðistrúar, fylgjandi Leibniz frekar en Spinoza“.

Þegar Gödel var átta ára gamall fékk hann gigtarsótt, sem hann læknaðist af án sýnilegra eftirkasta. Alla tíð síðan hafði hann sífelldar áhyggjur af heilsufari sínu og var á fullorðinsárum illa haldinn af ímyndunarveiki. Hann fékk nokkrum sinnum alvarleg þunglyndisköst. Síðustu árin var Gödel altekinn af hræðslu um að reynt væri að eitra fyrir sér og neytti engrar annarrar fæðu en þeirrar sem eiginkona hans útbjó. Þegar hún þurfti að leggjast inn á sjúkrahús síðla ársins 1977 hætti hann að matast og svelti sig þannig til bana. Hann dó 14. janúar 1978 af vannæringu.

Verk Gödels hafa verið gefin út í fimm bindum. Í tveimur fyrstu eru þau verk sem birtust að honum lifandi, í því þriðja eru handrit sem hann skildi eftir sig, og í tveimur síðustu eru bréfaskipti hans við ýmsa fræðimenn.

Heimildir og frekara lesefni:

• Baaz, M., Papadimitriou, C. H., Putnam, H. W., Scott, D. S., Harper, Jr., C. L. [ritstj.] (2011): Kurt Gödel and the Foundations of Mathematics. Horizons of Truth. Cambridge. Cambridge University Press.
• Dawson, J. W. (1997). Logical Dilemmas. The Life and Work of Kurt Gödel. Wellesley, Mass. A K Peters.

• Fefferman, S., Parsons, C., Simpson, S. G. [ritstj.] (2010): Kurt Gödel. Essays for His Centennial. Cambridge. Association of Symbolic Logic og Cambridge University Press.
• Franzén, T. (2005). Gödel’s Theorem. An Incomplete Guide to Its Use and Abuse. Wellesley, Mass. A K Peters.
• Goldstein, R. (2005). Incompleteness: the proof and paradox of Kurt Godel. New York. W. W. Norton & Company.
• Gödel, K. (1986). Collected Works. Volume I. Publications 1929–1936. New York-Oxford. Oxford University Press.
• Gödel, K. (1995). Collected Works. Volume II. Publications 1938–1974. New York-Oxford. Oxford University Press.
• Gödel, K. (1990). Collected Works. Volume III. Unpublished essays and lectures. New York-Oxford. Oxford University Press.
• Hintikka, J. (2000) On Gödel. Belmont, CA. Wadsworth/Thomson Learning.
• Hofstadter, D. R. (1979). Gödel, Escher, Bach: an eternal golden braid. New York. Basic Books.
• Nagel, E., Newman, J. R. (1958). Gödel's Proof. New York. New York University Press. (Revised Edition 2001).
• Sigmund, K., Dawson, J., Mühlberger, K. (2006). Kurt Gödel. Das Album. The Album. Wiesbaden. Vieweg.
• Smith, P. (2007). An Introduction to Gödel’s Theorems. Cambridge. Cambridge University Press.
• Smullyan, R. M. (1992). Gödel’s Incompleteness Theorems. New York-Oxford. Oxford University Press.
• Wang, H. (1987). Reflections on Kurt Gödel. Cambridge, Mass. MIT Press.
• Wang, H. (1996). A Logical Journey. From Gödel to Philosophy. Cambridge, Mass. MIT Press.
• Yasugi, M., Passell, N. (2003). Memoirs of a Proof Theorist. Gödel and other Logicians. New Jersey-London-Singapore-Hong Kong. World Scientific.
• Yourgrau, P. (1999). Gödel Meets Einstein. Time Travel in the Gödel Universe. Chicago. Open Court.

Myndir:

• Gödel: Wikipedia: Kurt Gödel. Sótt 11. ágúst 2011.
• Cantor: Wikipedia: Georg Cantor. Sótt 11. ágúst 2011 (texti settur inn af ritstjórn).
• Gödel og Einstein: Vefur St. Andrews háskóla um sögu stærðfræðinnar. Sótt 18. ágúst 2011.
• Leibniz: Wikipedia: Gottfried Wilhelm Leibniz. Sótt 11. ágúst 2011 (texti settur inn af ritstjórn).

...