Gödelovy věty o neúplnosti

Gödelovy věty o neúplnosti jsou dvě důležité matematické věty, které mají zcela výsadní postavení v celé moderní matematické logice. Důležitou roli však hrají v celé matematice, zejména pak v teorii modelů, aritmetice a v teorii množin. Dokázal je roku 1931 rakouský logik Kurt Gödel.

Gödelovy věty jsou velmi významné i z hlediska filosofie matematiky, stanovují totiž hranice axiomatické metody v matematice. Plyne z nich například neproveditelnost takzvaného Hilbertova programu, který si kladl za cíl vytvořit bezespornou, úplnou teorii, s efektivně zadatelnou množinou axiomů, v níž by bylo možné interpretovat aritmetiku přirozených čísel.

Klasické znění

Následující věty jsou formulovány velmi podobně tomu, jak je původně dokázal Kurt Gödel. Originální Gödelova terminologie i notace jsou ovšem v důsledku bouřlivého rozvoje matematické logiky následujícím po jeho objevu pro současného čtenáře téměř neproniknutelné. Proto jsou zde uvedené věty přeloženy do srozumitelnějšího jazyka moderní matematiky. Tímto překladem došlo sice k mírnému zesílení těchto vět, ne však k zesílení podstatnému. Pozdější zobecnění Gödelových vět jsou uvedena v dalších odstavcích.

První Gödelova věta o neúplnosti

Znění

Nechť T je rekurzivně axiomatizovaná teorie v jazyce aritmetiky obsahující Robinsonovu aritmetiku, taková, že struktura přirozených čísel je jejím modelem. Pak existuje sentence $\nu$, která není v T dokazatelná ani vyvratitelná.

Formule $\nu$ z této věty má svůj vlastní název – Gödelova formule.

Význam

Označme na chvíli za rozumnou takovou axiomatickou teorii schopnou hovořit o přirozených číslech, jejich sčítání a násobení, v níž:

1. není možné dokázat cokoli (např. nesmysly jako $(\exists x) (x\neq x)$), a zároveň takovou, že
2. jsme schopni o každém tvrzení rozhodnout (v konečném čase), zda je či není axiomem této teorie.

Každý jistě uzná, že oba tyto požadavky jsou skutečně „rozumné“ – jinak bychom totiž buďto mohli dokázat jakékoli nesmysly nebo bychom naopak ani nevěděli, jaké předpoklady můžeme v důkazech využít.

To, co jsme právě nazvali rozumná teorie, je jen poněkud méně přesně přeříkaný matematický termín bezesporná rekurzivně axiomatizovaná teorie v jazyce aritmetiky. Pokud navíc v takové rozumné teorii budou dokazatelné základní vlastnosti přirozených čísel (jako například $x+0=x$) znamená to, že tato teorie obsahuje Robinsonovu aritmetiku.

To, že struktura přirozených čísel je modelem této teorie, znamená, že nic z toho, co v naší teorii můžeme dokázat o přirozených číslech, neodporuje tomu „jak to skutečně je“.

Tedy tvrzení „teorie obsahuje Robinsonovu aritmetiku a přirozená čísla jsou jejím modelem“ znamená, že tato teorie skutečně hovoří o těch přirozených číslech, které známe, a ne o nějakých podivných jiných.

První Gödelova věta pak říká, že kdykoli máme rozumnou teorii hovořící o našich přirozených číslech, pak tato teorie není dostatečně silná, aby byla schopná dokázat o přirozených číslech vše. Tedy ideální teorie požadovaná v Hilbertově programu neexistuje.

Druhá Gödelova věta o neúplnosti

Znění

V Peanově aritmetice není dokazatelná ani vyvratitelná sentence $Con_{PA}$, kde $Con_{PA}$ je formule, která ve struktuře přirozených čísel vyjadřuje skutečnost, že Peanova aritmetika je bezesporná.

Význam

První Gödelova věta říká, že v žádné rozumné teorii hovořící o přirozených číslech není dokazatelné vše. Druhá Gödelova věta dává konkrétní příklad takového nedokazatelného tvrzení pro Peanovu aritmetiku – je jím věta „Peanova aritmetika je bezesporná.“

Zobecnění a zesílení Gödelových vět

Klasifikace složitosti Gödelovy formule

První Gödelovu větu lze zesílit tvrzením, že tam definovaná Gödelova formule $\nu$ je $\Pi_1$ formule (viz Aritmetická hierarchie). Z tohoto zesílení tedy plyne, že v teorii T splňující předpoklady první Gödelovy věty existuje nezávislá formule nejnižší možné složitosti ($\nu$ je $\Pi_1$ a tedy $\neg\nu$ je $\Sigma_1$). Každá $\Delta_1$ formule je totiž v takové teorii již dokazatelná nebo vyvratitelná (podle toho, zda ona nebo její negace platí v přirozených číslech – to plyne z věty o sigma úplnosti Robinsonovy aritmetiky).

Navíc lze dokázat, že Gödelova formule platí ve struktuře přirozených čísel.

Rosserova věta

Předpoklad o tom, že struktura přirozených čísel je modelem T je možné v První Gödelově větě vynechat. To říká Rosserova věta:

Nechť T je bezesporná rekurzivně axiomatizovatelná teorie v jazyce aritmetiky obsahující Robinsonovu aritmetiku. Pak existuje sentence $\rho$, která není v T dokazatelná ani vyvratitelná.

Formule $\rho$ z této věty má svůj vlastní název – Rosserova formule.

Zobecněná věta o neúplnosti

Druhou Gödelovu větu lze zobecnit následujícím způsobem:

Nechť T je bezesporná rekurzivně axiomatizovatelná teorie a existuje interpretace teorie $I\Sigma_1$ (viz teorie IΣ1) v T (k tomu stačí existence interpretace Peanovy aritmetiky v T). Pak v teorii T je nezávislá formule $Con_T$ vyjadřující (formální) bezespornost teorie T.

Z takto zobecněné věty plyne například neúplnost libovolného rekurzivního rozšíření Zermelo-Fraenkelovy (a tedy též Gödel-Bernaysovy) teorie množin. Všechny konečné ordinály totiž tvoří obor interpretace Peanovy aritmetiky v teorii množin.

Nerozhodnutelnost bezesporných rozšíření Robinsonovy aritmetiky

Pomocí metod teorie vyčíslitelnosti lze dokázat tvrzení, jehož snadným důsledkem je první Gödelova věta. Toto tvrzení zní následovně:

Každé bezesporné rozšíření Robinsonovy aritmetiky je nerozhodnutelné (dokonce rekurzivně neoddělitelné). Je-li tedy rekurzivně axiomatizovatelné, je neúplné.

Toto tvrzení má svůj vlastní význam a neslouží pouze k pohodlnému důkazu první Gödelovy věty. Plyne z něj totiž například nerozhodnutelnost teorií okruhů, komutativních okruhů, oborů integrity, těles a těles charakteristiky nula.

Zajímavé příklady nezávislých tvrzení

V teorii množin

V teorii množin existuje velmi mnoho nezávislých tvrzení. Konkrétně v Zermelo-Fraenkelově axiomatizaci to jsou například následující:

• Axiom výběru
• Hypotéza kontinua
• Hypotéza singulárních kardinálů
• Martinův axiom
• Zobecněná hypotéza kontinua
• Diamantový princip
• Axiomy existence velkých kardinálů

V Peanově aritmetice

Po důkazu Gödelových vět se matematici snažili nalézt příklady konkrétních zajímavých matematických tvrzení, která jsou nedokazatelná v Peanově aritmetice. Ukázalo se, že jde o velmi obtížný problém. Díky práci L. Kirbiho a J. Parise je známo několik málo takových tvrzení. Jsou to:

• Různé silnější varianty Ramseyovy věty
• Goodsteinova věta

Odkazy

Související články

• Löbova věta
• Diagonální lemma
• Hilbertův program
• Kurt Gödel
• Gödelova věta o úplnosti predikátové logiky

Externí odkazy

• Náčrt důkazu Gödelových vět – obsahuje všechny hlavní myšlenky, nikoli však technické detaily (anglicky)
• Martin Hirzel, On formally undecidable propositions of Principia Mathematica and related systems I., 2000. (ke stažení anglický překlad originálního Gödelova článku)

Literatura

• Kurt Gödel, Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I., Monatshefte für Mathematik und Physik 38: 173–98, 1931. (původní Gödelův článek)
• Vítězslav Švejdar, Logika – neúplnost, složitost a nutnost, Academia, Praha, 2002, ISBN 80-200-1005-X
• K. Devlin, Jazyk Matematiky, Argo, Praha 2003
• SMULLYAN, Raymond M.. Navěky nerozhodnuto : úvod do logiky a zábavný průvodce ke Gödelovým objevům. Praha : Academia, 2003. 308 s. ISBN 80-200-1068-8.