Kurt Gödel: život, výsledky a jejich význam

Libor Běhounek

Abstrakt. Kurt Gödel bývá považován za nejvýznamnějšího logika 20. století, zejména díky svým větám o neúplnosti. Vedle základních biografických a bibliografických údajů článek podává přehled Gödelových nejdůležitějších výsledků, jimiž zasáhl do matematické logiky, teorie množin, filozofie matematiky a fyziky. Zvláštní pozornost je věnována výkladu vět o neúplnosti, jejich demytizaci a důsledkům pro informatiku, umělou inteligenci a filozofii mysli.

1	Život Kurta Gödela
Kurt Gödel se narodil 28. dubna 1906 v Brně jako syn spolumajitele prosperující textilní továrny..V Brně žil až do roku 1923, kdy úspěšně maturoval na zdejším německém gymnáziu. V následujícím roce se přestěhoval do Vídně a nastoupil ke studiu na Vídeňské univerzitě. Zpočátku nebyl rozhodnut mezi matematikou a teoretickou fyzikou, postupně však převážil jeho zájem o matematiku a logiku. Od roku 1926 byl jako Hahnův velmi nadaný student zván na pravidelné schůzky prestižního Vídeňského kruhu – vedoucí skupiny logického pozitivizmu. Přestože filozoficky byl v té době již vyhraněným platonistou, do debat Kruhu nevstupoval a své filozofické přesvědčení, ostře kontrastující s názory Kruhu, si nechával pro sebe.
V roce 1929 studium dokončil odevzdáním dizertace, již tvořil důkaz úplnosti predikátové logiky prvního řádu (publikována byla v [Gö1]). Tento výsledek prezentoval v krátkém referátu na významné konferenci o základech matematiky v Královci v říjnu 1930. Protože byl výsledek o úplnosti v tehdejším vědeckém kontextu očekávaný, nevzbudil referát mezi přítomnými větší rozruch. V plenární diskuzi poslední den konference Gödel krátce zmínil, že lze udat příklady pravdivých nedokazatelných vět aritmetiky. Jediný z účastníků, kdo toto oznámení neignoroval, byl John von Neumann: v kuloárech si nechal od Gödela vysvětlit základní myšlenku věty a jejího důkazu, který měl Kurt Gödel zřejmě již několik měsíců hotov, a v Princetonu o ní zpravil své kolegy. Gödel první větu o neúplnosti publikoval následujícího roku 1931 [Gö2] a podal ji jako svou habilitační práci, na jejímž základě se v roce 1933 stal na Vídeňské univerzitě soukromým docentem.
V akademickém roce 1933–34 byl pozván do Princetonu, kde o svých výsledcích přednášel na nově otevřeném Ústavu pro pokročilá studia; zde se také seznámil s Albertem Einsteinem, který sem krátce předtím utekl před nacizmem. Po návratu do Vídně se roku 1938 oženil a vzápětí odjel (bez manželky) znovu do Ameriky, kde přednášel o svých výsledcích v teorii množin.
V létě 1939 se vrátil do Vídně, aby zde obhajoval svůj nárok na docenturu, podléhající nyní novým pravidlům nacistického Německa. Na podzim se chtěl vrátit do Princetonu, vyřízení jeho žádosti o docenturu se však pro jeho naprostou apolitičnost a předchozí styky s židovskými kolegy protahovalo. Po začátku války se Gödel začal obávat odvedení do armády (jednou byl navíc napaden skupinou nacistických výtržníků, kteří si jej spletli se Židem); koncem roku se proto raději rozhodl pro emigraci. Po intervenci amerických kolegů mu bylo na přelomu roku povoleno vycestovat, a to přes Rusko a Japonsko: do Princetonu tak s manželkou dorazil až na jaře 1940. V Princetonu se potom zdržoval až do konce života, nejprve jako dočasný člen Ústavu pro pokročilá studia (s prodlužovanou roční smlouvou), od roku 1946 pak jako jeho stálý člen a od roku 1953 konečně jako profesor. Evropu již nikdy nenavštívil; roku 1948 získal americké občanství a v průběhu dalších let čestné doktoráty prestižních amerických univerzit (Harvardovy, Yalovy ad.) a různá jiná ocenění (Einsteinovu cenu, členství v národních akademiích a společnostech aj.).
Gödel žil vždy velmi uzavřeným životem. Společnosti se převážně vyhýbal a byl spíše plachý, v některých směrech však dosti umanutý. Od dětství trpěl neurotickými obtížemi, hypochondrií (po přestálé revmatické horečce ve věku šesti let se po celý život mylně domníval, že má poškozené srdce) a dalšími psychickými poruchami, jež různé okolnosti jeho života postupně prohlubovaly. Mezi prvními dvěma pobyty v Americe prodělal dvojí nervové zhroucení a musel nějaký čas pobývat v sanatoriu. S věkem se jeho uzavřenost zvětšovala a v Princetonu se mimopracovně stýkal jen s několika přáteli – zejména s Einsteinem, po jeho smrti roku 1955 pak hlavně s logiky Hao Wangem a G. Kreiselem, vídeňským ekonomem Morgensternem a nemnoha dalšími; děti neměl. Po roce 1958 přestal své výsledky publikovat, přestože stále pracoval; nevedl ani žádné studenty. Paranoidní strach z otravy jídlem vedl k jeho dlouhodobé podvýživě; během několikaměsíčního pobytu jeho ženy v nemocnici na podzim 1977 pak vyhladověl k naprosté vyčerpanosti, a ani pobyt v nemocnici, kam jej nechala po svém návratu odvézt, jej již nezachránil; zemřel 14. ledna 1978.

2	Gödelovy výsledky a přínos
V této a následující části podáme základní přehled Gödelových výsledků a jejich stručné zhodnocení. Vzhledem k obsáhlosti tématu a stavu jeho prozkoumání může jít pochopitelně pouze o shrnující a přehledový popis; podrobnosti a další informace lze najít v odkazované literatuře. Její výběr se částečně řídil snadnou dostupností pro české a slovenské čtenáře: z velkého množství relevantní literatury proto byly přednostně použity práce vydané česky nebo slovensky a zdroje přístupné na internetu.
2.1	Logika
Nejznámějším Gödelovým výsledkem v logice jsou bezesporu jeho věty o neúplnosti, vnímané často jako ničím nepřekonatelný výkon. I podle Gödelova osobního názoru (citovaného v [Kr]) však bylo v letech 1930–31 otázkou měsíců, kdy by na tyto věty narazil někdo jiný. Jeho výsledky proto není třeba titanizovat; přišel však s nimi jako první a ve velmi propracované a čisté formě. Vedle vět o neúplnosti aritmetiky podal i první důkaz úplnosti prvořádové logiky a významně přispěl k teorii i metateorii intuicionistické logiky a matematiky.
2.1.1	Věta o úplnosti prvořádové logiky
Věta o úplnosti nějakého formálního systému říká, že všechny jeho sémanticky platné formule v něm lze syntakticky odvodit. Pro formální systém logiky prvního řádu jde tedy o větu, že všechny logicky platné formule jazyka prvního řádu jsou dokazatelné (v dané axiomatice této logiky). Dnešní axiomatika prvořádové logiky byla navržena v roce 1928 v Hilbertově a Ackermannově knize Grundzügen der theoretischen Logik. V následujícím roce Gödel kladně vyřešil (v ní formulovaný) problém její úplnosti, neboli dokázal následující větu:
Věta (o úplnosti): Každá tautologie klasické prvořádové logiky je dokazatelná v Hilbertově–Ackermannově systému axiomů.
Spolu se (snadnou) větou o korektnosti této axiomatiky (jež říká, že dokazatelné jsou v ní pouze tautologie prvořádové logiky) Gödelův výsledek znamená, že pojem logické pravdivosti v jazyce prvního řádu přesně odpovídá jednoduchému pojmu formální („mechanické“) dokazatelnosti v určitém formálním axiomatickém systému. 
Význam tohoto výsledku je značný: ukazuje, že pro prvořádová tvrzení lze pojem logické pravdivosti – tedy pravdivosti ve všech (čili nekonečně mnoha) strukturách (i nekonečných) – redukovat na dokazatelnost pomocí konečné mechanické procedury ve finitně zadaném axiomatickém systému. Tato věta se zdála podporovat formalistickou doktrínu Hilbertovy školy, požadující redukovat veškerou matematiku, zabývající se i nekonečnými strukturami, na jednoduché manipulace s konečně zadanými objekty. (Její neproveditelnost ukázaly až věty o neúplnosti.)
Z hlediska obecného dosahu této věty je třeba mít na paměti, že se týká pouze logiky prvního řádu a platí vlastně právě díky omezenosti jejích výrazových prostředků. Jazyk prvořádové logiky obsahuje vedle výrokových spojek (konjunkce, disjunkce, negace, implikace, ekvivalence) pouze proměnné pro individua nějakého daného univerza, jména pro predikáty nějakého daného jazyka a možnost kvantifikace přes individuové proměnné. Na rozdíl od logiky druhého a vyšších řádů neobsahuje proměnné (nýbrž jen jména) pro predikáty a funktory, a neumožňuje tedy přes ně ani kvantifikovat.
Unární predikáty označují vlastnosti individuí, reprezentované podmnožinami univerza; binární a více-ární predikáty vyjadřují vztahy mezi těmito individui a jsou reprezentovány relacemi příslušné arity na univerzu. V logice prvního řádu tedy můžeme mluvit o jednotlivých predikátech, pro něž máme v daném jazyce jména – např. v jazyce aritmetiky o predikátu „být menší“ <. Nemůžeme však přes predikáty (neboli podmnožiny a relace) kvantifikovat. V prvořádovém jazyce tedy nelze vyjádřit ani tak důležité věty jako Každá množina přirozených čísel má nejmenší prvek či Každá omezená množina reálných čísel má supremum. Tyto věty obsahují kvantifikaci přes podmnožiny, jsou tedy druhořádové.
Úplnost prvořádové logiky tedy neznamená redukci matematické pravdivosti na dokazatelnost, neboť mnoho důležitých matematických vět je druhořádových. Gödelovy věty o neúplnosti ukazují, že tato redukce obecně skutečně není možná.
2.1.2	Věty o neúplnosti
Tzv. první Gödelova věta o neúplnosti konstatuje neúplnost určitého druhu formálních teorií. V jedné z nejstručnějších verzí může být formulována takto: 
Věta (první o neúplnosti): Každá bezesporná rekurzívně axiomatizovaná teorie obsahující Peanovu aritmetiku je neúplná.
Peanova aritmetika PA je prvořádovou teorií obsahující tři axiomy pro funkci následníka neboli přičtení jedničky (nula není následníkem žádného čísla, každé nenulové číslo je následníkem nějakého čísla, a čísla si jsou rovna, jsou-li si rovni jejich následníci); rekurzívní definice sčítání pomocí následníka (x+0 = x, x+násl(y) = násl(x+y)) a násobení pomocí sčítání (x×0 = 0, x×násl(y) = x×y+x); a axiom indukce pro každou prvořádovou aritmetickou vlastnost j (tedy tvrzení, že má-li vlastnost j nula a s každým číslem i jeho následník, pak ji už mají všechna čísla).
Vlastnost rekurzívnosti lze považovat za ekvivalentní algoritmizovatelnosti pomocí Turingova stroje (v praxi tedy počítače). Teorie je rekurzívně axiomatizovaná, má‑li rekurzívní sadu axiomů a odvozovacích pravidel. Pouze takové teorie lze rozumně chápat jako „finitně“ zadané, neboť pouze u nich máme konečný algoritmus, jak poznat jejich axiomy. 
Neúplnost teorie znamená, že existuje tvrzení, které v ní nelze ani dokázat ani vyvrátit. Je-li daná teorie navíc korektní (tj. jsou-li v ní dokazatelné pouze pravdivé věty aritmetiky), pak existují pravdivá aritmetická tvrzení, která v ní nejsou dokazatelná. V obou případech Gödelův důkaz umožňuje tato tvrzení přímo sestrojit, tj. ukázat konkrétní takovou formuli (nazývanou Gödelova sentence).
Myšlenka důkazu spočívá v zakódování syntaxe formální teorie pomocí čísel. Každé formuli je tak algoritmicky přiřazen její číselný kód, tzv. Gödelovo číslo. Tím jsou syntaktické vlastnosti vyjádřeny v jazyce aritmetiky a lze o nich v aritmetice dokazovat potřebná tvrzení. Předpoklad úplnosti teorie lze pak obratem podobným Cantorově diagonální metodě přivést ke sporu. Přes jasnou základní myšlenku je provedení všech detailů důkazu poměrně pracné a vyžaduje značné množství definovaných pojmů a předběžných lemmat.
V důsledku Gödelovy věty je značná část zajímavých dostatečně silných matematických teorií principiálně neúplná. Věta navíc tvrdí, že teorie zůstane neúplnou, ať ji rozšíříme jakýmkoli rozumným způsobem – tj. tak, aby zůstala bezesporná (spor by teorii zcela znehodnocoval, neboť lze přes něj odvodit cokoliv) a rekurzívně axiomatizovaná (abychom byli schopni algoritmicky poznat její axiomy).
Důsledkem vhodného tvaru první Gödelovy věty je tzv. druhá věta o neúplnosti, formulovatelná např. takto:
Věta (druhá o neúplnosti): Žádná bezesporná rekurzívně axiomatizovaná teorie T obsahující Peanovu aritmetiku nedokazuje formuli Con(T) vyjadřující její formální bezespornost.
Rigorózní výklad formule Con(T) a přesná formulace její souvislosti s bezesporností teorie T přesahuje rámec tohoto článku. Lze ji však v určitém smyslu chápat jako formální protějšek bezespornosti teorie T a větu interpretovat tak, že v dostatečně silné bezesporné rekurzívní teorii nelze dokázat její vlastní bezespornost. Výkladu důsledků a významu obou vět o neúplnosti věnujeme samostatný oddíl 3.
2.1.3	Nekonečněhodnotovost intuicionistické logiky
Na počátku dvacátého století matematik L. E. J. Brouwer vystoupil s požadavkem konstruktivního vedení důkazů v matematice. Jeho přístup, nazvaný intuicionizmus, získal v první polovině dvacátého století (jakožto jedna z reakcí na krizi v základech matematiky způsobenou paradoxy teorie množin a infinitní matematiky) poměrně velký ohlas. Intuicionistická matematika nepřipouští důkazy sporem, neuznává zákon dvojité negace A«ØØA ani zákon vyloučení třetího AÚØA apod. Logiku používanou v intuicionistické matematice axiomatizoval koncem dvacátých let A. Heyting. Klasická výroková logika je dvouhodnotová – lze ji zavést pomocí pravdivostních tabulek se dvěma hodnotami 0 a 1. Několik let nebylo jasné, zda nelze podobně chápat intuicionistickou logiku jako troj‑ či vícehodnotovou. Bylo nalezeno několik sad vícehodnotových pravdivostních tabulek, vůči nimž je intuicionistická logika korektní (tj. při počítání podle těchto tabulek vycházejí intuicionisticky platné formule jako pravdivé). Vždy se však ukázalo, že není vůči nim úplná (tabulky „přegenerovávaly“ – byly podle nich pravdivé i některé intuicionisticky neplatné formule). Ve svém dvoustránkovém článku [Gö3] Gödel demonstroval marnost těchto snah – pomocí vtipného obratu dokázal, že intuicionistická logika nemůže být zadána pomocí žádné pravdivostní tabulky s konečně mnoha hodnotami.
Pro účely důkazu tohoto tvrzení Gödel přidal k intuicionistické logice axiom (A®B)Ú(B®A). Přestože Gödel výslednou logiku ani nepojmenoval a nijak ji dále nepoužil, byla to první zmínka o důležitém logickém systému, který později důkladně prozkoumal M. Dummett. Po vzniku fuzzy logiky se ukázalo, že toto rozšíření intuicionistické logiky je zároveň jednou z nejdůležitějších fuzzy logik, v níž je konjunkce realizována jako minimum pravdivostních hodnot obou argumentů v intervalu [0, 1]. Vedle důkazu nekonečněhodnotovosti intuicionistické logiky se tak Gödel stal maně objevitelem jedné z nejdůležitějších fuzzy logik, dnes zvané Gödelova či Gödelova–Dummettova.
2.2	Teorie množin
Teorie množin je spolu s logikou součástí „základů matematiky“ a zejména v první polovině dvacátého století ji bylo možno považovat za obor „sousedící“ s logikou. Je proto přirozené, že Gödel byl aktivní i v něm.
2.2.1	Nevyvratitelnost hypotézy kontinua a axiomu výběru
V roce 1938 Gödel jedním tahem z poloviny vyřešil dva dlouho otevřené významné problémy v teorii množin:
Koncem 19. století zakladatel teorie množin Georg Cantor vyslovil hypotézu, že každá podmnožina reálných čísel je buďto spočetná (tj. existuje její očíslování přirozenými čísly), nebo má mohutnost kontinua (tj. existuje její vzájemně jednoznačné zobrazení na množinu R všech reálných čísel); jiné podmnožiny R totiž nemohl nalézt. Přes několik částečných výsledků potvrzujících, že podmnožiny R nejrůznějších vlastností jeho hypotézu splňují, obecný důkaz Cantor ani nikdo jiný nebyl schopen podat. Tato hypotéza kontinua, v kardinální aritmetice zapsatelná jako 2À0 = À1, byla zobecněna na ještě silnější hypotézu stanovující 2Àa = Àa+1 pro každé ordinální číslo a – tedy tvrzení, že mezi mohutností žádné nekonečné množiny a její potence (množiny všech jejích podmnožin) již nejsou žádné další mohutnosti. Ani tuto silnější hypotézu (GCH) se nikomu nepodařilo vyvrátit ani dokázat.
V souvislosti s axiomatizací teorie množin (v reakci na nalezené paradoxy) na počátku dvacátého století se ukázalo, že mnoho důkazů v matematice používá obrat, kdy se současně vybere nekonečně mnoho nespecifikovaných prvků. Předpoklad, že to lze, precizovaný a formulovaný jako axiom výběru (AC), zní v jedné ze svých mnoha ekvivalentních podob takto: ke každé množině A neprázdných množin existuje množina, která má s každou množinou z A právě jednoprvkový průnik. Bez axiomu výběru nebylo možno dokázat mnoho důležitých výsledků, mimo jiné i tak „očividná“ tvrzení, jako že kartézský součin systému neprázdných množin je neprázdný; jeho nekonstruktivní povaha – nedává totiž žádný předpis, jak výběrovou množinu sestrojit – jej však činila pochybným nejen v očích intuicionistů. Velkou snahou matematiků po více než tři desítky let proto bylo buď tento axiom dokázat z ostatních axiomů teorie množin (čímž by byl ospravedlněn), nebo ukázat jeho nezávislost na ostatních axiomech teorie množin (čímž by byl alespoň vyjasněn jeho status, podobně jako u pátého Eukleidova postulátu).
Gödelův výsledek oznámený v [Gö4] používá konstrukci popisující tzv. konstruovatelné množiny. Gödel ukázal, že univerzum všech konstruovatelných množin (označované L) splňuje všechny axiomy teorie množin, a navíc v něm platí jak axiom výběru, tak i zobecněná Cantorova hypotéza kontinua. Ukázal tedy, že AC i GCH jsou s obvyklými Zermelovými–Fraenkelovými axiomy teorie množin konzistentní, nedají se tedy pomocí nich vyvrátit. Druhou polovinu důkazu jejich nezávislosti, tj. jejich nedokazatelnost, ukázal v šedesátých letech P. Cohen.
Konstrukce univerza L hrála pak důležitou roli i v dalším vývoji teorie množin. Toto univerzum je prototypem jejích tzv. vnitřních modelů (vnitřních proto, že L je poduniverzem univerza všech množin, označovaného V; navíc obsahuje všechna ordinální čísla). Pomocí konstrukcí vnitřních modelů lze ukázat řadu dalších výsledků o nedokazatelnosti či nevyvratitelnosti některých principů teorie množin. Velmi podrobný popis Gödelovy konstrukce včetně všech důkazů a aplikací těchto metod lze najít v [So2]; dobrý celkový obrázek lze získat i z přehledu v [BŠ], [Kr] či [Kl].
Přijetí předpokladu, že každá množina je konstruovatelná (tedy axiomu V=L), řeší nejenom problém platnosti AC a GCH, ale i mnoho dalších problémů teorie množin. Gödel sám ihned ukázal, že z něj plynou odpovědi na některé tehdy otevřené problémy deskriptivní teorie množin (zda existují množiny reálných čísel s jistými vlastnostmi). Protože je však univerzum L na množiny velice „chudé“ (v jistém smyslu nejchudší možné), není axiom V=L v teorii množin běžně přijímán a L je obvykle chápáno jen jako velmi důležitý vnitřní model. Takto L chápal i sám Gödel; přes svůj výsledek o její nevyvratitelnosti byl totiž přesvědčen, že Cantorova hypotéza ve skutečnosti neplatí.
2.2.2	Gödelova–Bernaysova–von Neumannova axiomatizace teorie tříd
Vedle tohoto významného příspěvku žije Gödelovo jméno v každodenním hovoru množinových teoretiků i v názvu jedné z nejvýznamnějších axiomatik teorie množin, označované jako Gödelova–Bernaysova, GB (též NBG, von Neumann–Bernays–Gödel). Na rozdíl od staršího Zermelova–Fraenkelova systému ZF jsou jeho objekty nikoli množiny, nýbrž tzv. třídy. Množiny jsou definovány jako ty třídy, které jsou prvky jiných tříd. Množinami v zásadě mohou být jen „malé“ třídy; tím jsou ošetřeny paradoxy teorie množin propukající jinak u „nadměrně velkých“ tříd, jako je třída všech množin V. Díky opatrné formulaci schématu axiomů definování tříd, požadující kvantifikaci pouze přes množiny (nikoli třídy), je tato teorie stejně silná jako ZF a lze ji chápat jako její notační variantu (třídy lze zavést v ZF jako zkratky za formule, viz [So2] či [BŠ]); jejich rozdíly však hrají roli v metamatematických zkoumáních: GB je např., narozdíl od ZF, konečně axiomatizovatelná. Podrobný popis teorie GB a jejích vlastností je uveden v [So2] (pro stručný přehled viz např. [Wi1], heslo „NBG“).
2.3	Fyzika a filozofie
Dalším oborem, do nějž Gödel – sice jen jednou, zato však významně – zasáhl, byla obecná teorie relativity. Celý život se rovněž zabýval problémy filozofie matematiky; jeho eseje o ní však byly publikovány až z jeho pozůstalosti. Vedle toho se široké publicitě teší jeho spíše kuriózní verze důkazu boží existence. Těmito tématy proto přehled jeho hlavních výsledků uzavřeme.
2.3.1	Filozofie matematiky: Gödelův program
Gödel byl od svých studií přesvědčeným platónským realistou. Ve filozofii matematiky tento názor znamená přesvědčení, že matematické objekty existují nezávisle na našich axiomech a metodách: ty je nevytvářejí, jen popisují. I když tedy podle Gödelových vět existují tvrzení, která daným formálním aparátem nelze rozhodnout, z objektivní existence matematické reality pro platonistu vyplývá, že tato nezávislá tvrzení jsou přesto buď pravdivá, nebo nepravdivá. (V tom se liší např. od intuicionisty, podle nějž tvrzení nemají pravdivostní hodnotu, dokud je nedokážeme nebo nevyvrátíme.) U složitějších nezávislých tvrzení však nemá platonista žádné vodítko, zda jsou (přes svoji nedokazatelnost a nevyvratitelnost) pravdivá či nikoli – kromě matematické intuice.
Gödel (svoji) matematickou intuici jako takové vodítko bral velmi vážně. Kupříkladu Cantorovu hypotézu, jejíž nevyvratitelnost sám dokázal, považoval za nepravdivou. Jako obecný princip, který by podle něj měl rozhodnout „skutečnou pravdivost“ všech podobných nezávislých tvrzení, navrhoval postulování stále větších a větších kardinálních čísel.
Jak ukázal již Cantor, existuje nekonečné množství různých mohutností nekonečných množin. Tyto mohutnosti, označované kardinálními čísly, jsou (za předpokladu axiomu výběru) lineárně uspořádány a k větším kardinalitám lze přejít operacemi potence či sjednocení. Tzv. nedosažitelné kardinály jsou (volně řečeno) ta kardinální čísla, k nimž se od menších nelze pomocí potence a sjednocení dostat. Jejich existence není z axiomů teorie množin dokazatelná a lze ji jedině postulovat. Postulátem tohoto druhu je již sám axiom nekonečna, zaručující existenci nekonečné spočetné množiny: ke spočetnému nekonečnu se rovněž operacemi sjednocení a potence nelze dostat od menších – konečných – množin. Konečné množiny tvoří soběstačné univerzum teorie množin bez axiomu nekonečna; ten teprve zaručuje, že toto uzavřené univerzum konečných množin „překročíme“. Podobný postulát lze přijmout i pro překročení uzavřeného univerza množin menších než nedosažitelný kardinál. Matematici tyto postuláty obvykle považují za přijatelné: rozšiřují totiž univerzum množin přirozeným způsobem směrem k větším velikostem. Předpoklad existence vhodného velkého kardinálu pak často řeší jinak nerozhodnutelné problémy teorie množin.
Gödel rovněž považoval toto rozšiřování za přirozené: „skutečné“ univerzum množin totiž podle jeho představ není nijak omezeno – ani kardinálem, jehož existenci naším (pouhým) formalizmem nelze dokázat. Byl tedy pro zesilování teorie množin jakýmkoliv prodlužováním hierarchie kardinálů. Takovýmto prodlužováním kardinalit nade všechny meze měla být podle něj nakonec rozhodnuta všechna důležitá nerozhodnutelná tvrzení teorie množin.
Tato strategie rozhodování nezávislých tvrzení je známa jako Gödelův program. Přestože se s jeho pomocí skutečně dá mnoho nezávislých tvrzení rozhodnout, jsou indicie, že u některých tvrzení postulování sebevětšího kardinálu nepomůže (jedním z nich je právě Cantorova hypotéza kontinua). V současné době se tedy Gödelův program považuje pro rozhodnutí všech nezávislých tvrzení za nedostatečný.
2.3.2	Rekonstrukce ontologického důkazu boží existence
Gödel se vždy snažil pracovat na takových problémech, které mají filozofický přesah. V době kolem roku 1970 jeho kolegové věděli, že pracuje na formálním důkazu existence boží. V jeho pozůstalosti se skutečně list papíru s takovým důkazem našel. Jedná se o formalizaci Leibnizovy varianty Anselmova ontologického důkazu v modální logice S5 druhého řádu.
Ve velmi stručné formulaci zní Anselmův argument takto: bůh, jakožto nejdokonalejší bytost, má z definice všechny přednosti; pro takovou bytost je existence jistě předností – musí ji tedy mít. Gödel analyzoval tento důkaz prostředky moderní logiky, aby nalezl jeho přesnou strukturu a odhalil potřebné předpoklady.
Formální důkaz nalezený v pozůstalosti je velmi stručný, nekomentovaný, a má některé nežádoucí důsledky. Od jeho publikace v r. 1987 byl proto řadou autorů znovu studován, rekonstruován a opravován – ze slovenských a českých zejména P. Zlatošem [Zl2] a P. Hájkem [Há].
Na rozdíl od populárních představ, Gödelův důkaz pochopitelně není žádným nepochybným důkazem boží existence. Je pouze formální rekonstrukcí a analýzou po staletí známého ontologického důkazu, vůči němuž lze vznášet celou řadu námitek. Gödelem izolované a explicitně uvedené formální předpoklady navíc ukazují, že jejich přijetí je značně problematické, a odhalují tak de facto především slabiny „důkazu“.
2.3.3	Gödelův model vesmíru
Známým Gödelovým výsledkem je rovněž jeho překvapivé řešení Einsteinových rovnic pole dávající kosmologický model, jenž umožňuje fyzickou cestou v prostoru dosáhnout libovolných časoprostorových souřadnic – tedy i cestovat v čase do minulosti. Gödel teoretické fyzice dobře rozuměl (začal ji původně studovat společně s matematikou); jeho přátelství s Einsteinem v Princetonu a jeho snaha pracovat na filozoficky relevantních matematických problémech zřejmě přispěly k hledání takto neobvyklého řešení rovnic obecné teorie relativity.
Gödelovo řešení se týká vesmíru s pečlivě zvolenou nenulovou kosmologickou konstantou, v němž jsou částice „prachu“ (což mohou být například galaxie) v určitém rotačním pohybu. Následkem toho je jeho geometrie uzavřena do sebe takovým způsobem, že obsahuje uzavřené časupodobné křivky; to vede k popsaným efektům.
Článek [Gö5] s tímto kosmologickým modelem Gödel napsal k Einsteinovým sedmdesátinám v roce 1949. Einsteina existence takových modelů jeho vlastní teorie znepokojila a soudil, že nebudou fyzikálně možné. Gödel byl však svým řešením natolik zaujat, že se zajímal o to, zda v reálném vesmíru existuje preferovaný smysl pohybu galaxií. Gödelovo řešení bylo prvním z širší třídy později nalezených řešení s uzavřenými časupodobnými křivkami; všechna jsou však neslučitelná s pozorovanými vlastnostmi vesmíru (Gödelův vesmír například nemá Hubblovu expanzi).

3	K významu vět o neúplnosti 
Stručné zhodnocení většiny Gödelových nejdůležitějších a nejznámějších výsledků jsme provedli přímo u jejich popisu v předchozí kapitole. Zde se budeme podrobněji zabývat významem jeho vět o neúplnosti, zejména z hlediska jejich filozofických interpretací. Zvláště přihlédneme k jejich případným důsledkům v informatice a umělé inteligenci.
3.1	Důsledky vět o neúplnosti v metamatematice a informatice
Principiální neúplnost dostatečně silných teorií u laiků obvykle vyvolává údiv. Z určitého podstatného hlediska však věty o neúplnosti příliš překvapivé nejsou; překvapivá je z tohoto hlediska naopak věta o úplnosti. Ta říká, že logickou platnost prvořádových formulí lze popsat konečnou mechanickou aplikací konečných pravidel; tedy že naše omezené konečné prostředky kupodivu plně popisují celou nekonečnou třídu i nekonečných matematických struktur z hlediska prvořádové platnosti. Naopak věty o neúplnosti říkají, že určitou konkrétní nekonečnou matematickou strukturu – přirozená čísla – našimi konečnými prostředky rekurzívních teorií nepopíšeme. Právě proto, že je tato struktura nekonečná, nedá se ani příliš očekávat, že to půjde – bylo by překvapivé, kdyby to bylo možné.
Proč tedy věty o neúplnosti (a nikoli věta o úplnosti) vzbudily takový ohlas, jemuž se u laické veřejnosti těší dodnes? – Bylo to dáno zejména historickými okolnostmi. Snaha o zabezpečení matematiky pracující s nekonečnem (zejména matematické analýzy a teorie množin) proti paradoxům a mylným intuicím vedla na počátku dvacátého století k programu její formalizace – podložení „podezřelých“ tvrzení o nekonečných strukturách „solidními“ finitními metodami axiomatických systémů v rámci nedávno vzniklé formální logiky. Hlavním proponentem tohoto přístupu byl Hilbert, který sám takto formalizoval geometrii. Jedním z hlavních cílů Hilbertova programu bylo ukázat, že infinitní metody jsou redukovatelné na finitní – zejména že jejich (nejistou) bezespornost lze prokázat ryze finitními metodami. Za finitní oblast par excellence a jednu z nejjednodušších matematických disciplin se považovala (peanovská) aritmetika; jedním z hlavních cílů se tedy stalo ukázat bezespornost teorie množin (a díky ní i dalších oborů infinitní matematiky) právě pomocí aritmetiky. Gödelovy věty o neúplnosti však možnost dosažení tohoto cíle vyvrátily.
Překvapení z Gödelových vět bylo o to větší, že předchozí vývoj (kupodivu) nasvědčoval proveditelnosti Hilbertova plánu: vedle geometrie bylo krátce předtím formalizováno i několik dalších teorií (např. teorie reálných čísel) a ukázána úplnost těchto formalizací. Sama Gödelova věta o úplnosti do tohoto programu zcela zapadala (proto ani nevzbudila velkou pozornost). I v případě aritmetiky samotné již existovaly indicie pro její úplnost – byla dokázána úplnost peanovské aritmetiky bez operace násobení (tzv. Presburgerova aritmetika) a jen se čekalo, kdy někdo vyřeší problém úplnosti aritmetiky i s násobením. V této celkem oprávněně optimistické atmosféře pak Gödel vyvrátil jak úplnou axiomatizovatelnost aritmetiky, tak možnost prokázání bezespornosti infinitní matematiky finitními prostředky (neboť podle jeho druhé věty nelze v „bezpečně bezesporné“ Peanově aritmetice prokázat ani bezespornost jí samotné, natož silnější teorie množin).
Hlavním důsledkem Gödelových vět tedy bylo vyvrácení původní verze Hilbertova programu, jež se díky nim ukázala přece jen jako příliš naivní. Proveditelné jsou tak jen značně oslabené verze tohoto programu (např. dokazovat lze pouze relativní bezespornost teorií vůči sobě navzájem apod.). Vedle opravy základního obrazu filozofie matematiky mají však Gödelovy věty v metamatematice i technický význam: využívá je např. demonstrace nedokazatelnosti existence nedosažitelných kardinálů v ZF (viz pozn. 15) či důkaz nemožnosti teorii ZF konečně axiomatizovat; podobně se jejich prostřednictvím dá ukázat prvořádová nedefinovatelnost některých struktur v určitých teoriích.
Pojem rekurzívní funkce, který Gödel pro účely svého důkazu v aritmetice přesně definoval (intuitivně byl používán již dříve), formálně zachycuje její principiální algoritmickou počitatelnost. Metody použité v důkazu našly proto později značné uplatnění v teorii algoritmů a informatice. Z hlediska algoritmizovatelnosti rozpracoval gödelovské metody koncem 30. let Alan Turing (viz zvl. [Tu]). Pomocí výpočetního modelu Turingova stroje bylo možno dát pojmu rekurzívní funkce ryze algoritmický charakter a ukázat výpočetní ekvivalenty Gödelových vět. Vedle neúplnosti matematických teorií tak byla (Turingem, Churchem a dalšími) ukázána algoritmická nerozhodnutelnost některých úloh – neexistence algoritmu řešícího takovou úlohu obecně, pro každý vstup. V oblasti metamatematiky jde zejména o nerozhodnutelnost aritmetiky a dalších formálních teorií (např. teorie grup, okruhů ad.), včetně samotné prvořádové logiky. Rozpracování gödelovských metod vedlo i např. k negativnímu řešení desátého Hilbertova problému, v němž Hilbert žádal mechanickou metodu rozpoznání řešitelnosti diofantických rovnic. Nejznámější aplikací v informatice je věta (dokázaná již v [Tu]) o algoritmické neřešitelnosti problému zastavení, tedy neexistence programu, který by pro každý program a jeho vstupní data rozpoznal, zda se na nich zastaví, nebo zacyklí. Podobnými obraty je možno ukázat algoritmickou neřešitelnost řady dalších úloh.
Věty o neúplnosti a nerozhodnutelnosti jsou ve všech těchto oblastech bezesporu významnými výsledky; za ještě důležitější je ale možno považovat metody, které do metamatematiky, teorie modelů i teorie rekurze přinesly.
3.2 Chybné interpretace Gödelových vět
Gödelovy věty bývají velmi často chybně vykládány, obvykle v důsledku neporozumění či přehlédnutí role jejich premis; jejich význam mimo metamatematiku tak bývá značně přeceňován. Naznačíme zde důvody, proč jsou zejména jejich interpretace pro přírodní vědy a pro filozofii mysli ve většině případů zcela nepřiměřené a uvedeme na pravou míru několik nejčastějších konkrétních nesprávných interpretací Gödelových vět.
Obvyklou chybou laických interpretací obou vět je jejich aplikace na situace, kterých se netýkají. Jedním z nejvulgárnějších příkladů jsou tvrzení typu: Jak rigorózně ukázal Gödel, Bible je buďto neúplná, nebo sporná. Protože Bible je jen sotva rekurzívní teorií obsahující Peanovu aritmetiku, věta o neúplnosti o jejích formálních vlastnostech nemluví. Jistěže Bible je v běžném slova smyslu neúplná a snadno najdeme libovolné množství tvrzení takových, že z Bible nevyplývá ani jejich pravdivost ani nepravdivost; zjevně to však není v důsledku Gödelových vět.
Pochybenost tohoto argumentu je sice zjevná, jeho sofistikovanější podoby však lze často potkat v oblasti metodologie přírodních věd: jejich argumentace obvykle směřuje k nutné neúplnosti přírodovědných teorií v důsledku Gödelových vět. Význam případné formální neúplnosti jejich matematické stránky je však zcela marginální ve srovnání s principiální nejistotou jejich správnosti danou induktivní metodou jejich ověřování. Neúplnost jejich matematické stránky se týká pouze jejich idealizované extrapolace do nekonečna, zatímco reálně jsou tyto teorie založeny jen na omezeném počtu pozorování a omezených výsecích reality.
Proponenti těchto interpretací rovněž často přehlížejí fakt, že ne každá teorie, která pracuje s čísly, je neúplná. Mnoho fyzikálních teorií ve skutečnosti vystačí s elementární teorií reálných či komplexních čísel, které jsou úplné. A i v těch fyzikálních teoriích, které potřebují definovat aritmetiku právě všech přirozených čísel, mají obvykle jakýkoli fyzikální význam přirozená čísla pouze po nějakou, třeba nepředstavitelně velkou, přesto však konečnou mez; a aritmetika omezená libovolně velkým, ale konečným přirozeným číslem je (triviálně) rozhodnutelná a úplná.
Právě fakt, že neúplnost se týká pouze ideálních, nekonečných matematických struktur, její aplikovatelnost v situacích týkajících se reálného světa prakticky vylučuje. Gödelovy věty tak ukazují pouze principiální nemožnost některých idealizovaných konstrukcí, jako byl Hilbertův program (týkající se ideální formalizace ideální matematiky) či existence nějakých idealizovaných počítačových programů. Turingovská řešitelnost je pouze velmi hrubým idealizovaným modelem reálné vyčíslitelnosti. Realitě o něco bližším modelem je zde nikoli teorie rekurze, nýbrž výpočetní složitosti, která má podstatně jemnější měřítko „praktické vyčíslitelnosti“, dané např. polynomiální složitostí. I rekurzívní, tj. principiálně algoritmicky řešitelné úlohy jsou totiž často (mají-li například exponenciální složitost) prakticky neřešitelné již pro velmi malou velikost vstupu. I tento jemnější pojem polynomiální složitosti je však jen matematická idealizace neodpovídající přesně praktické proveditelnosti (srv. například vypočítatelnost v čase omezeném polynomem stupně a pro a z pozn. 31). Praktická proveditelnost jakéhokoli výpočtu či simulace tedy záleží na mnohem přízemnějších věcech než Gödelových větách týkajících se všech přirozených čísel.
Z přesvědčení, že v důsledku Gödelových vět lidská mysl přesahuje možnosti formálních systémů (a tudíž klasických výpočetních modelů) vyvozují mnozí autoři dalekosáhlé závěry. Umělá inteligence pomocí klasických počítačů je podle nich nemožná, nebo aspoň vyžaduje použití zařízení přesahujících turingovskou výpočetní sílu (např. kvantových). Činnost lidského mozku vysvětlují pomocí kvantových efektů (tak zejména Penrose, viz [Pe]) a často hovoří o absolutní převaze lidské mysli nad neživou přírodou (např. [Lu]), s nejrůznějšími světonázorovými důsledky. Toto jejich přesvědčení se zakládá na následujícím chybném argumentu:
„Gödelův důkaz ukazuje, že Gödelova sentence pro daný formální systém je v tomto systému formálně nedokazatelná, nicméně pravdivá. Avšak tím, že Gödelův důkaz chápeme, nahlížíme (my lidé) i pravdivost příslušné Gödelovy sentence – vlastně jsme ji tak dokázali mimo rámec formalizmu. Naše schopnosti (například nahlédnout pravdivost Gödelovy sentence) tak přesahují možnosti kteréhokoli formálního systému – a tedy i kteréhokoli počítače, neboť jeho činnost lze formálním systémem popsat, byť by byl sebesložitější.“ 
Abychom nahlédli chybnost této argumentace, stačí si uvědomit, že samu Gödelovu větu dokazujeme pomocí metod, které jsou plně formalizovatelné v teorii množin. Pravdivost Gödelovy sentence pro Peanovu aritmetiku (označme ji GPA) tedy nahlížíme nikoli proto, že bychom nějak záhadně přesahovali možnosti počítače, nýbrž jen proto, že ji dokazujeme v silnější teorii – nikoli v PA, nýbrž v teorii množin (například ZF); tam ji však dokáže i náš počítač.
Pochopitelně v ZF zase nelze formálně dokázat Gödelovu sentenci pro ZF (GZF) – zatímco my její pravdivost (prý) dokážeme pomocí Gödelova důkazu nahlédnout. Avšak podle Gödelova důkazu je GZF pravdivá pouze za předpokladu, že je teorie ZF bezesporná. Pravdivost GZF tedy nahlížíme jen na základě víry, že ZF je bezesporná; na základě této „víry“ (tedy s přidáním axiomu Con(ZF)) však dokáže důkaz GZF zreprodukovat i náš počítač (GZF je v teorii ZF+Con(ZF) dokazatelná).
Můžeme sice tento argument iterovat, nikam se tím však nedostaneme. Počítač totiž v ZF umí dokázat samotnou Gödelovu větu, tedy i on „ví“, že Gödelova sentence libovolného rekurzívního formálního systému za předpokladu jeho konzistence platí. Jistotu této konzistence však v případě tak silných teorií, jako je ZF, nemá ani on, ani my. Při jejím postulování nemáme v případě dostatečně silné teorie o nic větší jistotu než počítač, který ji přijme mechanicky; naše „neformální nahlédnutí“ pravdivosti Gödelovy sentence GT není tedy o nic lepší, než její formální důkaz v T+Con(T).
Je tedy sice možné (byť sotva pravděpodobné), že schopnosti lidské mysli jsou dány kvantovými efekty v mikrotubulech neuronů (jak tvrdí Penrose); rozhodně to však nijak nevyplývá z Gödelových vět a ani to jimi nemůže být heuristicky podloženo. Ze všech těchto důvodů lze konstatovat, že Gödelovy věty nedávají žádnou indicii, že by projekt umělé inteligence byl nemožný, a to ani v rámci stávajících (turingovských) výpočetních modelů (na „klasickém“ počítači).

Poznámka: Práce na článku byla částečně podpořena grantem č. GD 401/03/H047 Grantové agentury České republiky.

Literatura
Reference na online zdroje se vztahují k lednu 2007. Některé z těchto zdrojů vyžadují předplatné (prola.aps.org, jstor.org, springerlink.com).

[BŠ]	Balcar, B., Štěpánek, P.: Teorie množin. Academia, Praha 2001 (1. vydání 1986).
[Fe]	Feferman, S.: Gödel’s program for new axioms: Why, where, how and what? In P. Hájek (ed.): Gödel ’96. Springer, New York, etc. 1996: 3–22. (Preprint na math.stanford.edu/~feferman)
[Go]	Goldsteinová, R.: Neúplnost. Důkaz a paradox Kurta Gödela. Dokořán, Praha 2006.
[Gö1]	Gödel, K.: Die Vollständigkeit der Axiome des logischen Funktionenkalküls. Mh. Math. Phys. 37 (1930) 349–360.
[Gö2]	Gödel, K.: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Mh. Math. Phys. 38 (1931) 173–198. (Částečný anglický překlad na www.research.ibm.com/people/h/hirzel)
[Gö3]	Gödel, K.: Zum intuitionistischen Aussagenkalkül. Anz. Akad. Wiss. Wien 69 (1932) 65–66.
[Gö4]	Gödel, K.: The consistency of the axiom of choice and of the generalized continuum-hypothesis. Proc. Nat. Acad. Sci. USA 24 (1938) 556–557. (Online na www.pubmedcentral.gov)
[Gö5]	Gödel, K.: An example of a new type of cosmological solutions of Einstein’s field equations of gravitation. Rev. Mod. Phys. 21 (1949) 447–450. (Online na prola.aps.org)
[Gö6]	Gödel K.: Filozofické eseje. Oikoumenh, Praha 1999.
[Há]	Hájek, P.: A new small emendation of Gödel’s ontological proof. Studia Logica 71 (2002) 149–164. (Online na www.springerlink.com)
[Ho]	Hofstadter, D. R.: Gödel, Escher, Bach: An Eternal Golden Braid. Basic Books, New York 1979.
[Ja]	Jaki, S. L.: A late awakening to Gödel in physics. Sensus Communis 5 (2004) No. 2–3. (Online na pirate.shu.edu/~jakistan)
[Kl]	Kleene, S. C.: The work of Kurt Gödel. J. Symb. Log. 41 (1976) 761–778. (Online na www.jstor.org)
[Kr]	Kreisel, G.: Kurt Gödel. 28 April 1906 – 14 January 1978. Biographical Memoirs of Fellows of the Royal Society. The Royal Society 1980. (Online na www.jstor.org)
[Lu]	Lucas, J. R.: Minds, machines and Gödel. Philosophy 36 (1961) 112–127. (Online na users.ox.ac.uk/~jrlucas)
[NN]	Nagel E., Newman, J. R.: Gödelův důkaz. Vutium, Brno 2003.
[Pe]	Penrose, R.: Makrosvět, mikrosvět a lidská mysl. Mladá fronta, Praha 1999.
[Po]	Podnieks, K.: Вокруг теоремы Геделя. Zinatne, Riga 1992. (Ruský originál a anglický překlad What Is Mathematics: Gödel’s Theorem and Around na www.ltn.lv/~podnieks)
[Sm1]	Smullyan, R.: Jak se jmenuje tahle knížka? Mladá fronta, Praha 1986.
[Sm2]	Smullyan, R.: Navěky nerozhodnuto. Academia, Praha 2003.
[So1]	Sochor, A.: Klasická matematická logika. Karolinum, Praha 2001.
[So2]	Sochor, A.: Metamatematika teorií množin. Karolinum, Praha 2005.
[Šv]	Švejdar, V.: Logika. Neúplnost, složitost a nutnost. Academia, Praha 2002.
[Tu]	Turing, A. M.: On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society 2/42 (1936) 230–265. (Online na www.turingarchive.org)
[Wi1]	Wikipedia, en.wikipedia.org, heslo „Kurt Gödel“ a hesla jím odkazovaná.
[Wi2]	Willard, D. E.: Self-verifying axiom systems, the incompleteness theorem and related reflection principles. J. Symb. Log. 66 (2001) 536–596. (Online na www.jstor.org)
[Zl1]	Zlatoš, P.: Ani matematika si nemôže byť istá sama sebou. Iris, Bratislava 1995 (Online verze na thales.doa.fmph.uniba.sk/zlatos)
[Zl2]	Zlatoš, P.: Gödelov ontologický dôkaz existencie Boha. Organon F 3 (1996) 211–238.