Godelova věta o neúplnosti a druhá Godelova věta [~ 1] jsou dvě věty matematické logiky o základních omezeních formální aritmetiky a v důsledku toho jakéhokoli formálního systému, ve kterém lze definovat základní aritmetické pojmy: přirozená čísla , 0 , 1 , sčítání a násobení .
První věta říká, že pokud je formální aritmetika konzistentní, pak obsahuje nevyvratitelný a nevyvratitelný vzorec.
Druhá věta tvrdí, že pokud je formální aritmetika konzistentní, pak v ní nelze odvodit nějaký vzorec, který smysluplně potvrzuje konzistenci této aritmetiky.
Obě tyto věty dokázal Kurt Gödel v roce 1930 (publikoval v roce 1931) a přímo souvisí s druhým problémem v Hilbertově slavném seznamu .
Na začátku 20. století prohlásil David Hilbert za cíl axiomatizovat celou matematiku a k dokončení tohoto úkolu zbývalo dokázat konzistenci a logickou úplnost aritmetiky přirozených čísel . 7. září 1930 se v Königsbergu konal vědecký kongres o základech matematiky a na tomto kongresu 24letý Kurt Gödel poprvé publikoval dvě zásadní věty o neúplnosti, které ukázaly, že Hilbertův program nelze realizovat: pro jakoukoli výběr axiomů aritmetiky, tam jsou teorémy, které nejsou možné ani dokázat, ani vyvrátit jednoduchými ( konečnými ) prostředky poskytnutými Hilbertem, a konečný důkaz konzistence aritmetiky je nemožný [6] .
Tato řeč nebyla předem oznámena a měla ohromující účinek, Gödel se okamžitě stal světovou celebritou a Hilbertův program formalizace základů matematiky vyžadoval naléhavou revizi. 23. října 1930 představil Gödelovy výsledky vídeňské Akademii věd Hans Hahn . Článek s oběma teorémy („ O zásadně nerozhodnutelných tezích v Principia Mathematica a souvisejících systémech “) byl publikován ve vědeckém měsíčníku Monatshefte für Mathematik und Physik v roce 1931. Přestože Gödel podal důkaz druhé věty pouze ve formě myšlenky, jeho výsledek byl tak jasný a nepopiratelný, že o něm nikdo nepochyboval. Hilbert okamžitě rozpoznal hodnotu Gödelových objevů; první úplné důkazy obou teorémů byly publikovány v Hilbert a Bernays ' Foundations of Mathematics (1938). V předmluvě k druhému dílu autoři uznali, že konečné metody k dosažení svého cíle nestačí, a přidali na seznam logických prostředků transfinitní indukci ; v roce 1936 se Gerhardu Gentzenovi podařilo prokázat konzistenci aritmetiky pomocí tohoto axiomu, ale logická úplnost zůstala nedosažitelná [6]
Ve své formulaci věty o neúplnosti Gödel použil pojem ω-konzistentní formální systém, silnější podmínka než pouhá konzistence. Formální systém se nazývá ω-konzistentní , pokud pro jakoukoli formuli A ( x ) tohoto systému nelze současně odvodit formule A ( 0 ), A ( 1 ), A ( 2 ), ... a ∃ x ¬ A ( x ) (jinými slovy, ze skutečnosti, že pro každé přirozené číslo n je vzorec A ( n ) odvoditelný, vyplývá, že vzorec ∃ x ¬ A ( x ) odvoditelný není). Je snadné ukázat, že ω-konzistence implikuje jednoduchou konzistenci (to znamená, že jakýkoli ω-konzistentní formální systém je konzistentní) [7] .
V procesu dokazování věty je sestrojen takový vzorec A aritmetického formálního systému S, že [7] :
Jestliže formální systém S je konzistentní, pak vzorec A není odvoditelný v S ; pokud je systém S ω-konzistentní, pak vzorec ¬A není v S odvoditelný . Pokud je tedy systém S ω-konzistentní, pak je neúplný [~ 2] a A je příkladem neřešitelné formule.Formuli A se někdy říká Gödelova neřešitelná formule [ 8] .
Výklad neřešitelné formuleVe standardní interpretaci [~ 3] formule A znamená "neexistuje žádná derivace formule A ", to znamená, že tvrdí svou vlastní nederivovatelnost v S. Proto podle Gödelova teorému, pokud je konzistentní pouze systém S, pak je tento vzorec skutečně v S neodvoditelný, a proto je ve standardní interpretaci pravdivý. Pro přirozená čísla je tedy vzorec A pravdivý, ale v S není odvoditelný [9] .
V procesu dokazování věty se sestrojí taková formule B aritmetického formálního systému S, že [10] :
Je-li formální systém S konzistentní, pak jsou v něm obě formule B i ¬B nederivovatelné; jinými slovy, pokud je systém S konzistentní, pak je neúplný [~ 2] a B je příkladem neřešitelné formule.Formuli B se někdy říká Rosserova neřešitelná formule [11] . Tento vzorec je o něco složitější než Gödelův.
Výklad neřešitelné formuleVe standardním výkladu [~3] vzorec B znamená „pokud existuje derivace vzorce B , pak existuje derivace vzorce ¬B “ . Ale podle Gödelovy věty ve formě Rossera, je-li formální systém S konzistentní, pak vzorec B v něm je neodvoditelný; pokud je tedy systém S konzistentní, pak je vzorec B ve standardní interpretaci správný [12] .
Důkaz Gödelovy věty se obvykle provádí pro konkrétní formální systém (ne nutně stejný), a proto se tvrzení věty ukazuje být dokázáno pouze pro tento systém. Studium dostatečných podmínek, které musí formální systém splňovat, aby mohl prokázat svou neúplnost, vede ke zobecnění věty na širokou třídu formálních systémů. Příklad zobecněné formulace [13] :
Jakákoli dostatečně silná rekurzivně axiomatizovatelná konzistentní teorie prvního řádu je neúplná.Gödelův teorém platí zejména pro každé konzistentní, konečně axiomatizovatelné rozšíření aritmetického formálního systému S.
Poté , co Yuri Matiyasevich dokázal , že jakákoli efektivně spočítatelná množina je diofantina a byly nalezeny příklady univerzálních diofantických rovnic , bylo možné formulovat větu o neúplnosti v polynomiální (nebo diofantické) formě [14] [15] [16] [17] :
Pro každou konzistentní teorii T lze specifikovat celočíselnou hodnotu parametru K tak, aby rovnice nemá řešení v nezáporných celých číslech, ale tuto skutečnost nelze v teorii T dokázat . Navíc pro každou konzistentní teorii je množina hodnot parametru K, které mají tuto vlastnost, nekonečná a algoritmicky nevyčíslitelná .Stupeň této rovnice lze snížit na 4 za cenu zvýšení počtu proměnných.
Gödel ve svém příspěvku podává nástin hlavních myšlenek důkazu [18] , který je s drobnými úpravami reprodukován níže.
Každý primitivní symbol, výraz a posloupnost výrazů nějakého formálního systému [~ 4] S bude spojena s určitým přirozeným číslem [~ 5] . Matematické pojmy a tvrzení se tak stávají pojmy a tvrzeními o přirozených číslech, a proto mohou být samy vyjádřeny v symbolice systému S. Zejména lze ukázat, že pojmy "vzorec", "derivace", "derivovatelný" vzorec“ jsou definovatelné v rámci systému S, to znamená, že je možné obnovit například vzorec F ( v ) v S s jednou volnou proměnnou přirozeného čísla v tak, že F ( v ) v intuitivní interpretaci znamená: v je odvoditelný vzorec. Nyní sestrojme nerozhodnutelnou větu systému S, tedy větu A , pro kterou není ani A ani ne-A neodvoditelné, a to následovně:
Vzorec v S s právě jednou volnou proměnnou přirozeného čísla se nazývá třídní výraz . Seřaďme třídní výrazy nějakým způsobem do posloupnosti, označme n-tou R ( n ) , a povšimněme si, že pojem „třídní výraz“, stejně jako relaci řazení R , lze definovat v systému S. Nechť α je libovolný výraz třídního výrazu; přes [a; n ] označují vzorec, který vznikne z třídního výrazu α nahrazením volné proměnné symbolem přirozeného čísla n . Ternární vztah x = [ y ; z ] se také ukázalo být definovatelné v S. Nyní definujeme třídu K přirozených čísel takto:
n ∈ K ≡ ¬Bew[ R ( n ); n ] (*)(kde Bew x znamená: x je odvozený vzorec [~ 6] ). Protože všechny definující pojmy z této definice mohou být vyjádřeny v S, platí totéž pro pojem K , který je z nich sestrojen, to znamená, že existuje takový třídní výraz C , že vzorec [ C ; n ], což je intuitivně interpretováno, znamená, že přirozené číslo n patří do K . Jako třídní výraz je C identický s některým konkrétním R ( q ) v našem výčtu, tzn.
C = R ( q )
platí pro nějaké určité přirozené číslo q . Ukažme nyní, že věta [ R ( q ); q ] je nerozhodnutelné v S. Pokud tedy věta [ R ( q ); q ] se předpokládá, že je odvoditelné, pak se ukáže jako pravdivé, to znamená, že podle výše uvedeného bude q patřit K , tedy podle (*), ¬Bew[ R ( q ); q ], což je v rozporu s naším předpokladem. Na druhou stranu, pokud předpokládáme odvoditelnou negaci [ R ( q ); q ], pak proběhne ¬ q ∈ K , tedy Bew[ R ( q ); q ] bude pravda. Proto [ R ( q ); q ] spolu s jeho negací bude odvoditelné, což opět není možné.
Ve standardním výkladu [~3] Gödelova nerozhodnutelná formule A znamená „neexistuje žádná derivace formule A “, to znamená, že prosazuje svou vlastní neodvoditelnost v systému S. A je tedy obdobou paradoxu lháře . Gödelova úvaha je v podstatě velmi podobná Richardovu paradoxu . K prokázání existence neodvoditelných tvrzení lze navíc použít jakýkoli sémantický paradox [19] .
Je třeba poznamenat, že tvrzení vyjádřené vzorcem A neobsahuje začarovaný kruh, protože zpočátku se pouze tvrdí, že nějaký konkrétní vzorec, jehož výslovné vyjádření je snadné (ač těžkopádné), je nedokazatelné. „Teprve později (a takříkajíc náhodou) se ukáže, že tato formule je přesně ta, která toto tvrzení sama vyjadřuje“ [19] .
Ve formální aritmetice S lze zkonstruovat vzorec, který je ve standardním výkladu [~ 3] pravdivý právě tehdy, když je teorie S konzistentní. Pro tento vzorec platí tvrzení druhé Gödelovy věty:
Pokud je formální aritmetika S konzistentní, pak v ní není žádný odvoditelný vzorec, který by smysluplně tvrdil konzistenci S .Jinými slovy, konzistenci formální aritmetiky nelze pomocí této teorie dokázat. Mohou však existovat důkazy konzistence formální aritmetiky pomocí prostředků, které jsou v ní nevyjádřitelné.
Nejprve se sestrojí formule Con , která smysluplně vyjadřuje nemožnost odvodit jakoukoli formuli v teorii S spolu s její negací. Pak je tvrzení první Gödelovy věty vyjádřeno vzorcem Con ⊃ G , kde G je Gödelova neřešitelná formule. Všechny argumenty pro důkaz první věty lze vyjádřit a provést pomocí S, to znamená, že vzorec Con ⊃ G je odvoditelný v S. Proto, jestliže Con je odvoditelný v S , pak G je také odvoditelný v něm . Podle první Gödelovy věty však platí, že pokud je S konzistentní, pak je v něm G nederivovatelné. Pokud je tedy S konzistentní, pak vzorec Con je v něm také neodvoditelný .
Odborníci podávají velmi různá, někdy dokonce polární hodnocení historického významu Gödelových teorémů. Někteří vědci se domnívají, že tyto teorémy „převrátily“ základy matematiky či dokonce celé teorie poznání a význam Gödelova geniálního objevu se bude postupně odhalovat ještě dlouho [20] . Jiní (například Bertrand Russell ) nabádají nepřehánět, protože teorémy jsou založeny na Hilbertově konečném formalismu [21] [22] .
Na rozdíl od populární mylné představy Gödelovy teorémy neúplnosti neznamenají, že některé pravdy nebudou nikdy známé navždy. Navíc z těchto teorémů nevyplývá, že by lidská schopnost poznání byla nějak omezená. Ne, teorémy pouze ukazují slabiny a nedostatky formálních systémů [23] .
Uvažujme například následující důkaz konzistence aritmetiky [24] .
Předpokládejme, že Peanova axiomatika pro aritmetiku je nekonzistentní. Pak z toho lze odvodit jakékoli tvrzení, včetně nepravdivého. Všechny Peanovy axiomy jsou však zjevně pravdivé a z pravdivých tvrzení nemůže vyplynout nepravdivý závěr – dostáváme rozpor. Proto je aritmetika konzistentní.
Z hlediska každodenní lidské logiky je tento důkaz přijatelný a přesvědčivý. Nelze ji však napsat podle pravidel Hilbertovy teorie důkazů, protože v těchto pravidlech je sémantika nahrazena syntaxí a pravda je nahrazena „odvoditelností“ [24] . V každém případě Gödelovy teorémy pozvedly filozofii matematiky na novou úroveň.