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 (respektive teorii čísel) 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íž:

není možné dokázat cokoli (např. nesmysly jako $(\exists x)(x\neq x)$ ), a zároveň takovou, že
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í:

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

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.

Související články

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. Archivováno 16. 9. 2004 na Wayback Machine., 2000. (ke stažení anglický překlad originálního Gödelova článku)