Gödelovy věty o neúplnosti

Z Wikipedie, otevřené encyklopedie

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.

Obsah 1 Klasické znění 1.1 První Gödelova věta o neúplnosti 1.1.1 Znění 1.1.2 Význam 1.2 Druhá Gödelova věta o neúplnosti 1.2.1 Znění 1.2.2 Význam 2 Zobecnění a zesílení Gödelových vět 2.1 Klasifikace složitosti Gödelovy formule 2.2 Rosserova věta 2.3 Zobecněná věta o neúplnosti 2.4 Nerozhodnutelnost bezesporných rozšíření Robinsonovy aritmetiky 3 Zajímavé příklady nezávislých tvrzení 3.1 V teorii množin 3.2 V Peanově aritmetice 4 Podívejte se také na 5 Reference 6 Externí odkazy

[editovat] 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.

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

[editovat] Znění

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

Formule ν z této věty má svůj vlastní název - Gödelova formule.

[editovat] 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 (včetně nesmyslů jako například ), 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 nevěděli ani 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ě axiomatizovatelná 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 apod.) 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.

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

[editovat] 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á.

[editovat] 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á."

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

[editovat] Klasifikace složitosti Gödelovy formule

První Gödelovu větu lze zesílit tvrzením, že tam definovaná Gödelova formule ν je Π₁ 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 ( je Π₁ a tedy je Σ₁). Každá Δ₁ 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.

[editovat] 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 rekurzivně axiomatizovatelná teorie v jazyce aritmetiky obsahující Robinsonovu aritemtiku. Pak existuje sentence ρ, která není v T dokazatelná ani vyvratitelná.

Formule ρ z této věty má svůj vlastní název - Rosserova formule.

[editovat] 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Σ₁ (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.

[editovat] 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.

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

[editovat] 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ů

[editovat] 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

[editovat] Podívejte se také na

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

[editovat] Reference

• 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

[editovat] 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)