Godelovy věty o neúplnosti

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 .

Historie

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]

Godelova věta o neúplnosti

V původní podobě

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é formule

Ve 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 uniformě Rosser

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é formule

Ve 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] .

Zobecněné formulace

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.

Polynomický tvar

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.

Náčrt důkazu

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é.

Souvislost s paradoxy

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

Druhá Gödelova věta

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é.

Náčrt důkazu

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ý .

Historický vliv

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ň.

Viz také

Poznámky

Komentáře
  1. ↑ Někdy označovaná jako druhá Gödelova věta „o důkazech konzistence“ [1] , „o neúplnosti“ [2] [3] [4] , „o neúplnosti aritmetiky“ [5] .
  2. ↑ 1 2 Formální systém obsahující nerozhodnutelný, tedy neodvoditelný a nevyvratitelný vzorec, se nazývá neúplný.
  3. ↑ 1 2 3 4 Interpretace formulí teorie S se nazývá standardní, pokud je jejím definičním oborem množina nezáporných celých čísel, symbol 0 je interpretován číslem 0, písmena funkcí ', +, • jsou interpretována jako sčítání jedničky, sčítání a násobení, písmeno predikátu = je interpretováno vztahem identity.
  4. ↑ Gödel použil Whiteheadovu a Russellovu Principia Mathematica s tím, že zdůvodnění platí pro širokou třídu formálních systémů.
  5. ↑ Takové srovnání vzorců a přirozených čísel se nazývá aritmetizace matematiky a poprvé je provedl Gödel. Tato myšlenka se následně stala klíčem k řešení mnoha důležitých problémů matematické logiky. Viz Gödelovo číslování
  6. ↑ "Bew" zkr. od něho. "Beweisbar" - prokazatelné , odvoditelné
Prameny
  1. ↑ Kleene 1957 str. 513
  2. ↑ odpovídající člen RAS Lev Dmitrievich Beklemishev v "Úvodu do matematické logiky" . Datum přístupu: 7. ledna 2010. Archivováno z originálu 21. března 2009.
  3. ↑ Vysvětlující slovník výpočetních systémů - Strana 205
  4. ↑ Zprávy Akademie věd SSSR, svazek 262 - strana 799 (1982)
  5. ↑ Sborník Akademie věd SSSR, svazek 50 - strana 1140 (1986)
  6. ↑ 1 2 Pinheiro, 2015 , str. 13, 48-49, 66, 89-90.
  7. ↑ 1 2 Kleene 1957 str. 187
  8. ↑ Mendelssohn 1971 s.165
  9. ↑ Tato úvaha je převzata z Mendelssohn 1971 s. 160
  10. ↑ Viz například Kleene 1957 s. 188
  11. ↑ Mendelssohn 1971 s.162
  12. ↑ Mendelssohn 1971 s.162-163
  13. ↑ Mendelssohn 1971 s.176
  14. ↑ Jones JP, Nerozhodnutelné diofantické rovnice
  15. ↑ Martin Davis, Diophantine Equations & Computation (odkaz není k dispozici) . Získáno 17. listopadu 2009. Archivováno z originálu 24. května 2010. 
  16. ↑ Martin Davis, The Incompleteness Theorem . Získáno 30. listopadu 2011. Archivováno z originálu 4. března 2016.
  17. ↑ K. Podnieks, Gödelova věta v diofantické formě . Získáno 17. listopadu 2009. Archivováno z originálu 10. září 2017.
  18. ↑ Godel, Kurt. O formálně nerozhodnutelných tvrzeních Principia Mathematica a příbuzných systémů. I. - 1931. in Davis, Martin (ed.). Nerozhodnutelné: Základní články o nerozhodnutelných návrzích, neřešitelných problémech a vyčíslitelných funkcích . - New York: Raven Press, 1965. - S.  6 -8.
  19. ↑ 1 2 Gödel 1931
  20. ↑ Stephen Hawking . Godel a konec vesmíru (nedostupný odkaz) . Získáno 8. dubna 2018. Archivováno z originálu dne 29. května 2020. 
  21. ↑ Mikhailova N.V. Problém zdůvodnění moderní matematiky v kontextu nových filozofických a metodologických krizí // Filosofie matematiky: Aktuální problémy. Matematika a realita. Abstrakty 3. všeruské vědecké konference; 27. – 28. září 2013 . - M . : Centrum pro strategickou konjunkturu, 2013. - S. 187. - 270 s. - ISBN 978-5-906233-39-4 . Archivováno 16. prosince 2017 na Wayback Machine
  22. ↑ Hudebník A. .
  23. ↑ Livio, Mario. Byl Bůh matematik? Kapitola "Pravda v neúplnosti". - M. : AST, 2016. - 384 s. — (Zlatý fond vědy). - ISBN 978-5-17-095136-9 .
  24. ↑ 1 2 Pinheiro, 2015 , str. 155-162.

Literatura

Odkazy

Bibliografie - články Gödela

  • 1931, Über formální unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik 38 : 173-198.
  • 1931, Über formální unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. a O formálně nerozhodnutelných tezích Principia Mathematica a příbuzných systémů I v Solomon Feferman , ed., 1986. Kurt Gödel Collected works, Vol. I. _ Oxford University Press: 144-195. - Původní německý text s paralelním anglickým překladem, se základním úvodem napsaným Stephenem Kleene .
  • Hirzel, Martin, 2000, K formálně nerozhodnutelným tvrzením Principia Mathematica a příbuzných systémů I. . - Moderní překlad Marina Herzel.
  • 1951, Některé základní teorémy o základech matematiky a jejich důsledky v Solomon Feferman , ed., 1995. Kurt Gödel Collected works, Vol. III . Oxford University Press: 304-323.