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é. +more 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á. +more“.

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). +more 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. +more 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. +more (původní Gödelův článek) * Vítězslav Švejdar, Logika - neúplnost, složitost a nutnost, Academia, Praha, 2002, * K. Devlin, Jazyk Matematiky, Argo, Praha 2003.

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

[url=http://www. apronus. +morecom/math/goedel. htm]Náčrt důkazu Gödelových vět[/url] - obsahuje všechny hlavní myšlenky, nikoli však technické detaily (anglicky) * Martin Hirzel, [url=http://www. research. ibm. com/people/h/hirzel/papers/canon00-goedel. pdf]On formally undecidable propositions of Principia Mathematica and related systems I. [/url] , 2000. (ke stažení anglický překlad originálního Gödelova článku).

Kategorie:Matematická logika Kategorie:Matematické věty a důkazy Kategorie:Hilbertovy problémy