Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Prvá Gödelova veta o neúplnosti

3.7.2012 PVC
by

Anna Horska

on 5 September 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Prvá Gödelova veta o neúplnosti

Čo budeme a čo nebudeme dokazovať Nebudeme dokazovať vetu o silnej úplnosti a korektnosti predikátovej logiky voči Hilbertovskému kalkulu: T T Formula platí v každom modeli teórie T práve vtedy, keď je dokazateľná z axiómov teórie T. V tomto zmysle sú úplné všetky prvorádové teórie. Ide o vzťah SYNTAXE a SÉMANTIKY. Definícia: Úplná teória Teória T je úplná, ak je bezesporná a pre každú sentenciu platí: T alebo T ~ To, že v tomto zmysle nie sú úplné všetky teórie, hovorí prvá Gödelova veta o neúplnosti. Ak T je neúplná (a bezesporná), tak existuje sentencia , že z teórie T ani nedokážeme, ani nevyvrátime. Takáto sa nazýva NEZÁVISLÁ SENTENCIA. Prvá Gödelova veta o neúplnosti Nech teória T má aspoň aritmetický jazyk, je rekurzívne axiomatizovateľná a -korektná. Potom je T neúplná. Dokonca existujú nezávislé -sentencie. 1 1 {S, 0, +, , =} Aritmetický jazyk S je unárny funkčný symbol a jeho realizácia v štruktúre bude funkcia, ktorá pre prvok n vydá jeho následníka n+1. +, , sú binárne funkčné symboly. 0 je konštantný symbol. = je binárny relačný symbol. Teória s aspoň aritmetickým jazykom má v jazyku všetky tieto symboly a možno aj nejaké ďalšie. Rekurzívne axiomatizovateľná teória Množiny (čísel) tvoria hierarchiu podľa toho, aké je ťažké určiť, či do nich prvok patrí alebo nepatrí. REKURZÍVNE MNOŽINY sú také, že na otázku, či do nich x patrí alebo nie, vždy dostaneme odpoveď: Mám x, o ktorého náležaní chcem rozhodnúť. Pre danú množinu existuje algoritmus, ktorý vezme x ako vstup a odpovie, či x do nej patrí alebo nie. Túto tiedu značíme OR (ako obecne rekurzívne). Rekurzívne množiny Rekurzívne spočetné množiny REKURZÍVNE SPOČETNÉ MNOŽINY sú také, ktorých prvky sa dajú generovať. Ak mám x a chcem rozhodnúť o jeho náležaní do RS množiny, spustím program, ktorý mi bude generovať jej prvky. Ak x do nej patrí a mám dosť trpezlivosti, tak sa to raz dozviem, pretože program moje x vygeneruje. Ak x do nej nepatrí, nikdy sa to nedozviem. Budem čakať, kedy sa x vygeneruje, ale to sa samozrejme nikdy nestane. Blbé je, že ja si môžem myslieť (oprávnene), že som zatiaľ čakala príliš krátko a môj prvok sa ešte vygenerovať nestihol... Otázka: Aké sú konečné množiny? Teória T je rekurzívne axiomatizovateľná, ak je ekvivalentná teórii, ktorá má OR množinu axiómov. Môžme si teda predstavovať, že množina axiómov rekurzívne axiomatizovateľnej teórie je OR. Keď dostanem sentenciu, viem isto rozhodnúť, či je to jej axióm alebo nie. Hierarchia formulí Kvantifikátory poznáme: (x)
x (x) x Obmedzené kvantifikátory:
x<z (x) x(x<z (x))
x<z (x) x(x<z & (x)) -formule o Tieto formule neobsahujú iné kvantifikátory než obmedzené. Nemusia mať žiadne, ale ak nejaké majú, tak sú obmedzené. Príklad: Hovorí, že číslo 4 sa dá deliť dvojkou bez zvyšku, ale nie je . o Hovorí to isté, ale je . Využili sme vedomosť, že výsledok delenia musí byť aj tak menší ako delenec. V PA sa dá dokázať, že tieto dve formule sú ekvivalentné. o -formule a -formule n n -formula má začiatočný prefix zložený z n striedajúcich sa kvantifikátorov, prvý je a za týmto prefixom je -formula. n o n -formula má prvý kvantifikátor , inak to isté. Otázka: Čo je to -formula a -formula? o o Finta: Ak si vezmem -formulu , tak ju môžem pokladať za -formulu ako aj za -formulu. Spravím to tak, že do doplním "zbytočné" kvantifikátory. Na vhodné miesto proste pridám kvantifikovanú premennú, ktorá sa vo nenachádza, takže význam formule nemení. n n+1 n+1 Podobne, -formulu môžem pokladať za aj za -formulu. n n+1 n+1 Príklad: je -formula: o -korektnosť teórie 1 Definícia: Nech teória T má aspoň aritmetický jazyk. T je -korektná, ak každá -sentencia dokazateľná v T platí v štruktúre N 1 1 : T N Cvičenie: -korektnosť implikuje -korektnosť. 1 2 (Kto uhádne, čo je -korektnosť?) 2 Dôkaz: Vezmem si teóriu T, ktorá je -korektná. Chcem ukázať, že je aj -korektná. Takže si vezmem ľubovoľnú sentenciu (kde je -formula), že . Chcem, že platí v N . 1 2 2 1 axióm špecifikácie Ak všetky objekty majú danú vlastnosť, tak i objekt, ktorý je reprezentovaný termom n je prirodzené číslo, lebo termy
robíme len konečné. Pomocou pravidla
modus ponens: Ďalej získame toto, pretože term bol volený ľubovoľne: Zo -korektnosti: 1 Z Tarského definície pravdy: Intuitívne: Máme tvrdenie, že všetky prirodzené čísla majú v štruktúre vlastnosť . Ale v sú len prirodzené čísla, preto všetky prvky z majú . N N N Definovateľnosť v štruktúre N Definícia: Množina A obsahujúca prirodzené čísla je definovateľná v štruktúre , ak existuje formula (x) s voľnou premennou x, že platí: N Za voľnú premennú x sme substituovali term , ktorý v štruktúre reprezentuje prirodzené číslo n. N Výsledok našej teoretickej prípravy Príklady: Čo je A? Dá sa ukázať, že RS množiny sú v štruktúre definovateľné -formulami :) N 1 Kto si myslí, že už ideme dokazovať Gödelovu vetu, tak nie, ešte nejdeme... Ak sú množiny A a A rekurzívne spočetné, tak sú obe už rekurzívne. Postova veta _ Dôkaz: Vieme, že A i A sa dajú generovať. Chceme algoritmus, ktorý rozhoduje o náležaní napr. do A. Je jasné, že potom budeme vedieť rozhodovať aj o náležaní do komplementu. _ Zvoľme si teda prvok x, o ktorom sa chceme dozvedieť, či patrí do A alebo nie. Súčasne spustime algoritmy na generovanie množín A a A. Keďže A U A= N, tak x do jednej z nich patrí a jeden zo spustených algoritmov a isto zastaví. _ _ Tým sa dozvieme, kam x náleží a druhý generovací algoritmus (ktorý cyklí) môžeme zastaviť. Nech teória T s aspoň aritmetickým jazykom je rekurzívne axiomatizovateľná, -korektná. Potom je T neúplná. Dokonca existujú nezávislé -sentencie. Prvá Gödelova veta o neúplnosti Vezmime si množinu A RS-OR. (Takéto množiny existujú.) Vezmime si formulu ktorá je a definuje množinu A v štruktúre , : N Položme ďalej: "Tie prvky, o ktorých T tvrdí, že sú v A." "Prvky, o ktorých si T myslí, že nie sú v A." T je z predpokladu -korektná, preto platí: tj. Ďalej máme: tj. -korektnosť implikuje -korektnosť 2 pretože a -formula je i 1 2 Teória T je rekurzívne axiomatizovateľná, preto sú množiny X, Y rekurzívne spočetné: Vieme, rozhodnúť, či istá sentencia je alebo nie je axiómom teórie T. Preto môžeme generovať dokazateľné aj vyvratiteľné formule a testovať, či majú tvar, aký požadujú množiny X, Y. Tým budeme generovať prvky z X, Y. Dôkaz: Vieme, že . Preskúmajme, či Y=A ? _ n X n Y Množiny A a Y sú RS, disjunktné. Keby Y=A, tak A i Y by podľa Postovej vety mali byť OR, čo je spor, pretože A bolo volené ako RS, nerekurzívna množina. Z toho plynie . Vezmime _ : . Keďže tak máme: Ďalej , takže: je nezávislá -sentencia. 1. Gödelova veta o neúplnosti N
Full transcript