Gödelovy věty o neúplnosti

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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

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

Znění[editovat | editovat zdroj]

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

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

Znění[editovat | editovat zdroj]

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

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

Klasifikace složitosti Gödelovy formule[editovat | editovat zdroj]

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

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

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

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

V teorii množin[editovat | editovat zdroj]

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

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:

Odkazy[editovat | editovat zdroj]

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

Literatura[editovat | editovat zdroj]