Akýkoľvek systém matematických axióm, počnúc od určitej úrovne zložitosti, je buď vnútorne protirečivý alebo neúplný.
V roku 1900 sa v Paríži konala Svetová konferencia matematikov, na ktorej David Gilbert(David Hilbert, 1862–1943) predstavil formou téz 23 najdôležitejších, podľa neho, úloh, ktoré museli riešiť teoretici nadchádzajúceho dvadsiateho storočia. Číslo dva na jeho zozname bolo jedným z nich jednoduché úlohy, odpoveď na ktorú sa zdá byť zrejmá, kým sa nezahrabete trochu hlbšie. Rozprávanie moderný jazyk, bola to otázka: je matematika sebestačná? Druhá Hilbertova úloha sa zúžila na potrebu striktne dokázať, že systém axióm – základných tvrdení akceptovaných v matematike ako základ bez dôkazu – je dokonalý a úplný, to znamená, že umožňuje matematicky opísať všetko, čo existuje. Bolo potrebné dokázať, že je možné definovať taký systém axióm, aby boli po prvé vzájomne konzistentné a po druhé, aby sa z nich dal vyvodiť záver o pravdivosti či nepravdivosti akéhokoľvek tvrdenia.
Vezmime si príklad zo školskej geometrie. V štandardnej euklidovskej planimetrii (geometria v rovine) možno bezpochyby dokázať, že výrok „súčet uhlov trojuholníka je 180°“ je pravdivý a výrok „súčet uhlov trojuholníka je 137“. °“ je nepravda. V podstate povedané, v euklidovskej geometrii je akékoľvek tvrdenie buď nepravdivé alebo pravdivé, a neexistuje žiadna tretia možnosť. A na začiatku dvadsiateho storočia matematici naivne verili, že rovnaká situácia by mala byť pozorovaná v akomkoľvek logicky konzistentnom systéme.
A potom v roku 1931 nejaký okuliarnatý viedenský matematik Kurt Gödel- vzal a zverejnil krátky článok, ktorý jednoducho rozrušil celý svet takzvanej „matematickej logiky“. Po dlhých a zložitých matematických a teoretických preambulách stanovil doslova nasledovné. Vezmime si akýkoľvek výrok ako: „Predpoklad č. 247 v tomto systéme axióm je logicky nepreukázateľný“ a nazvime ho „výrok A“. Gödel teda jednoducho dokázal nasledujúcu úžasnú vlastnosť akéhokoľvek systému axióm:
"Ak sa dá dokázať tvrdenie A, dá sa dokázať aj tvrdenie nie-A."
Inými slovami, ak sa dá dokázať pravdivosť tvrdenia „predpoklad 247 je nepreukázateľný“, potom sa dá dokázať aj pravdivosť tvrdenia „predpoklad 247 je dokázateľný“. To znamená, že ak sa vrátime k formulácii druhého Hilbertovho problému, ak je systém axióm úplný (to znamená, že akékoľvek tvrdenie v ňom môže byť dokázané), potom je to protirečivé.
Jediným východiskom z tejto situácie je prijať neúplný systém axióm. To znamená, že sa musíme zmieriť s tým, že v kontexte akéhokoľvek logického systému budeme mať stále výroky „typu A“, ktoré sú zjavne pravdivé alebo nepravdivé – a ich pravdivosť môžeme posudzovať len mimo rámca axiomatiky, ktorú máme. prijaté. Ak takéto tvrdenia neexistujú, potom je naša axiomatika protirečivá a v jej rámci budú nevyhnutne existovať formulácie, ktoré možno dokázať aj vyvrátiť.
Takže formulácia prvej alebo slabej Gödelovej vety o neúplnosti: „Akýkoľvek formálny systém axióm obsahuje nevyriešené predpoklady“. Gödel sa však nezastavil pri formulovaní a dokazovaní druhej Gödelovej, silnej vety o neúplnosti: „Logickú úplnosť (alebo neúplnosť) akéhokoľvek systému axióm nemožno dokázať v rámci tohto systému. Na jeho dokázanie alebo vyvrátenie sú potrebné ďalšie axiómy (posilnenie systému).
Bolo by bezpečnejšie myslieť si, že Gödelove vety majú abstraktný charakter a netýkajú sa nás, ale iba oblastí vznešenej matematickej logiky, ale v skutočnosti sa ukázalo, že priamo súvisia so štruktúrou ľudského mozgu. Ukázal to anglický matematik a fyzik Roger Penrose (nar. 1931). Gödelove vety možno použiť na dôkaz, že medzi ľudským mozgom a počítačom existujú zásadné rozdiely. Význam jeho úvah je jednoduchý. Počítač sa správa striktne logicky a nie je schopný určiť, či je výrok A pravdivý alebo nepravdivý, ak presahuje rámec axiomatiky, a takéto výroky podľa Gödelovej vety nevyhnutne existujú. Človek, konfrontovaný s takýmto logicky nepreukázateľným a nevyvrátiteľným tvrdením A, je vždy schopný určiť jeho pravdivosť či nepravdivosť – na základe každodennej skúsenosti. Aspoň v tomto ohľade je ľudský mozog lepší ako počítač obmedzený čistými logickými obvodmi. Ľudský mozog je schopný pochopiť celú hĺbku pravdy obsiahnutej v Gödelových teorémoch, ale počítačový mozog to nikdy nedokáže. Preto je ľudský mozog všetko, len nie počítač. Je schopný robiť rozhodnutia a prejde Turingovým testom.
na tému: „GODELOVA TEORÉMA“
Kurt Gödel
Kurt Gödel, významný špecialista na matematickú logiku, sa narodil 28. apríla 1906 v Brunne (dnes Brno, Česká republika). Absolvoval Viedenskú univerzitu, kde obhájil dizertačnú prácu, v rokoch 1933–1938 bol odborným asistentom. Po anšluse emigroval do USA. V rokoch 1940 až 1963 pracoval Gödel na Princetonskom inštitúte pokročilých štúdií. Gödel je čestným doktorátom univerzít Yale a Harvard, členom Národnej akadémie vied USA a Americkej filozofickej spoločnosti.
V roku 1951 získal Kurt Gödel najvyššie vedecké ocenenie v USA – Einsteinovu cenu. V článku venovanom tejto udalosti ďalší významný matematik našej doby John von Neumann napísal: „Príspevok Kurta Gödela k modernej logike je skutočne monumentálny. Toto je viac ako len pamiatka. Toto je míľnik, ktorý oddeľuje dve epochy... Bez akéhokoľvek preháňania možno povedať, že Gödelovo dielo radikálne zmenilo samotný predmet logiky ako vedy.“
Dokonca aj suchý zoznam Gödelových úspechov v matematickej logike ukazuje, že ich autor v podstate položil základy pre celé sekcie tejto vedy: teóriu modelov (1930; tzv. teorém o úplnosti úzkeho predikátového počtu, ukazujúci, zhruba povedané, dostatok prostriedkov „formálnej logiky“ „na dôkaz všetkých pravdivých viet vyjadrených v jej jazyku), konštruktívnej logiky (1932–1933; vyplýva z možnosti zredukovať niektoré triedy viet klasickej logiky na ich intuicionistické analógy, ktoré položili tzv. základ pre systematické používanie „operácií vkladania“, ktoré umožňujú takúto redukciu rôznych logických systémov na seba), formálna aritmetika (1932–1933; výsledkom je možnosť redukcie klasickej aritmetiky na intuicionistickú aritmetiku, čo v istom zmysle ukazuje konzistentnosť prvý vzhľadom na druhý), teória algoritmov a rekurzívnych funkcií (1934; definícia pojmu všeobecnej rekurzívnej funkcie, ktorá zohrala rozhodujúcu úlohu pri stanovení algoritmickej nerozhodnuteľnosti mnohých najdôležitejších problémov matematiky , na jednej strane. A pri implementácii logických a matematických úloh na elektronických počítačoch - na druhej strane, axiomatická teória množín (1938; dôkaz relatívnej konzistentnosti axiómy výberu a Cantorovej hypotézy kontinua z axióm teórie množín, ktorá položila základ za sériu dôležitých výsledkov o relatívnej konzistentnosti a nezávislosti princípov teórie množín).
Gödelova veta o neúplnosti
Úvod
V roku 1931 sa v jednom z nemeckých vedeckých časopisov objavil relatívne malý článok s dosť zastrašujúcim názvom „O formálne nerozhodnuteľných tvrdeniach Principia Mathematica a súvisiacich systémov“. Jej autorom bol dvadsaťpäťročný matematik z Viedenskej univerzity Kurt Gödel, ktorý neskôr pôsobil v Princetonskom inštitúte pre pokročilé štúdium. Táto práca zohrala rozhodujúcu úlohu v dejinách logiky a matematiky. Rozhodnutie Harvardskej univerzity udeliť Gödelovej čestný doktorát (1952) ju označilo za jednu z najväčšie úspechy moderná logika.
V čase vydania však ani názov Gödelovho diela. Ani jeho obsah väčšine matematikov nič nehovoril. Principia Mathematica, spomenutá v názve, je monumentálne trojzväzkové pojednanie Alfreda North Whiteheada a Bertranda Russella o matematickej logike a základoch matematiky; oboznámenie sa s traktátom v žiadnom prípade nebolo nevyhnutnou podmienkou Pre úspešná práca vo väčšine odvetví matematiky. Záujem o problematiku riešenú v Gödelovej práci bol vždy výhradou veľmi úzkej skupiny vedcov. Zdôvodnenie, ktoré uviedol Gödel vo svojich dôkazoch, bolo zároveň na svoju dobu také neobvyklé. Ich úplné pochopenie si vyžadovalo mimoriadne zvládnutie predmetu a znalosť literatúry venovanej týmto veľmi špecifickým problémom.
Prvá veta o neúplnosti
Prvá Gödelova veta o neúplnosti, je zjavne najvýznamnejším výsledkom v matematickej logike. Znie to takto:
Pre ľubovoľnú konzistentnú formálnu a vypočítateľnú teóriu, v ktorej sa dajú dokázať základné aritmetické výroky, možno skonštruovať pravdivý aritmetický výrok, ktorého pravdivosť nemožno v rámci teórie dokázať. Inými slovami, žiadna úplne užitočná teória dostatočná na reprezentáciu aritmetiky nemôže byť konzistentná a úplná.
Slovo „teória“ tu znamená „nekonečný počet“ tvrdení, z ktorých niektoré sa považujú za pravdivé bez dôkazu (takéto tvrdenia sa nazývajú axiómy), zatiaľ čo iné (teorémy) možno z axióm odvodiť, a preto sa im verí (dokázané ), aby to bola pravda. Výraz „teoreticky dokázateľný“ znamená „odvoditeľný z axióm a primitív teórie (konštantných symbolov abecedy) pomocou štandardnej (prvého rádu) logiky“. Teória je konzistentná (konzistentná), ak v nej nie je možné dokázať protichodné tvrdenie. Fráza „dá sa skonštruovať“ znamená, že existuje nejaký mechanický postup (algoritmus), ktorý dokáže zostaviť výrok založený na axiómach, primitívoch a logike prvého rádu. „Elementárna aritmetika“ pozostáva z operácií sčítania a násobenia na prirodzených číslach. Výsledné pravdivé, ale nedokázateľné tvrdenie sa pre danú teóriu často označuje ako „Gödelova postupnosť“, no v teórii existuje nekonečné množstvo iných tvrdení, ktoré majú rovnakú vlastnosť: v rámci teórie pravdy nedokázateľné.
Predpoklad, že teória je vyčísliteľná, znamená, že je v princípe možné implementovať počítačový algoritmus (počítačový program), ktorý (ak je dovolené počítať počas ľubovoľne dlhého času, až do nekonečna) vypočíta zoznam všetkých teorémov teórie. . V skutočnosti stačí vypočítať iba zoznam axióm a z takého zoznamu sa dajú efektívne získať všetky vety.
Prvá veta o neúplnosti bola nazvaná „Veta VI“ v Gödelovom článku z roku 1931. O formálne nerozhodnuteľných tvrdeniach v Principia Mathematica a príbuzných systémoch I. V pôvodnej Gödelovej nahrávke to znelo takto:
„Všeobecný záver o existencii nerozhodnuteľných návrhov je tento:
Veta VI .
Pre každú ω-konzistentnú rekurzívnu triedu k FORMULA existujú rekurzívne ZNAKY r také, že ani jedno (v Gen r), ani nie ¬( v Gen r)nepatria do Flg (k)(kde je v VOĽNÁ PREMENNÁ r ) ».
Označenie Flg pochádza od neho. Folgerungsmenge- veľa sekvencií, Gen pochádza od neho. Zovšeobecnenie– zovšeobecňovanie.
Zhruba povedané, Gödelov výrok G uvádza: „pravda G sa nedá dokázať." Ak G by sa dalo dokázať v rámci teórie, potom by v tomto prípade teória obsahovala vetu, ktorá si protirečí, a preto by bola teória protirečivá. Ale keby G nedokázateľné, potom je to pravda, a preto je teória neúplná (tvrdenie G nemožno z neho odvodiť).
Toto vysvetlenie je v bežnom prirodzenom jazyku, a preto nie je úplne matematicky presné. Aby Gödel poskytol presný dôkaz, očísloval výroky pomocou prirodzených čísel. V tomto prípade do množiny výrokov patrí aj teória popisujúca čísla. Otázky o preukázateľnosti tvrdení možno v tomto prípade reprezentovať vo forme otázok o vlastnostiach prirodzených čísel, ktoré musia byť vyčísliteľné, ak je teória úplná. V tomto zmysle Gödelov výrok hovorí, že neexistuje číslo s nejakou špecifickou vlastnosťou. Číslo s touto vlastnosťou bude dôkazom nekonzistentnosti teórie. Ak takéto číslo existuje, teória je v rozpore s pôvodným predpokladom nekonzistentná. Takže za predpokladu, že teória je konzistentná (ako sa predpokladá v premise vety), ukáže sa, že takéto číslo neexistuje a Gödelovo tvrdenie je pravdivé, ale v rámci teórie to nie je možné dokázať ( preto je teória neúplná). Dôležitým koncepčným bodom je, že na vyhlásenie Gödelovho tvrdenia za pravdivé je potrebné predpokladať, že teória je konzistentná.
Druhá Gödelova veta o neúplnosti
Druhá Gödelova veta o neúplnosti znie takto:
Pre akúkoľvek formálne rekurzívne spočítateľnú (t. j. efektívne vygenerovanú) teóriu T, vrátane základných aritmetických pravdivostných tvrdení a určitých formálnych tvrdení o dokázateľnosti, daná teória T obsahuje vyhlásenie o jej konzistencii vtedy a len vtedy, ak je teória T nekonzistentná.
Inými slovami, konzistentnosť dostatočne bohatej teórie nie je možné dokázať pomocou tejto teórie. Môže sa však ukázať, že konzistentnosť jednej konkrétnej teórie možno stanoviť pomocou inej, silnejšej formálnej teórie. Potom však vyvstáva otázka o konzistencii tejto druhej teórie atď.
Mnohí sa pokúšali použiť túto vetu, aby dokázali, že inteligentnú činnosť nemožno redukovať na výpočty. Napríklad už v roku 1961 prišiel s podobným programom slávny logik John Lucas. Jeho úvahy sa ukázali ako dosť zraniteľné – úlohu však nastavil širšie. Roger Penrose má trochu iný prístup, ktorý je v knihe úplne načrtnutý, „od nuly“.
Diskusie
Dôsledky teorémov ovplyvňujú filozofiu matematiky, najmä tie formalizmy, ktoré používajú formálnu logiku na definovanie svojich princípov. Prvú vetu o neúplnosti môžeme preformulovať takto: „ je nemožné nájsť všeobjímajúci systém axióm, ktorý by bol schopný dokázať Všetky matematické pravdy a ani jedna lož" Na druhej strane z hľadiska prísnej formálnosti toto preformulovanie nedáva veľký zmysel, pretože predpokladá, že pojmy „pravda“ a „nepravda“ sú definované v absolútnom, a nie v relatívnom zmysle pre každý konkrétny prípad. systém.
Uspensky V.A.
Gödelova veta o neúplnosti.1994.
Teoretická informatika 130, 1994, s.273-238.
Možno je Gödelova veta o neúplnosti skutočne jedinečná. Je jedinečný v tom, že sa o ňom hovorí, keď chcú dokázať „všetko na svete“ – od prítomnosti bohov až po absenciu inteligencie. Vždy ma zaujímala skôr „primárna otázka“ – kto z tých, ktorí sa odvolávajú na vetu o neúplnosti, ju dokáže nielen sformulovať, ale aj dokázať? Tento článok publikujem z toho dôvodu, že uvádza úplne dostupnú formuláciu Gödelovej vety. Odporúčam vám, aby ste si najskôr prečítali článok Tullio Regge Kurt Gödel a jeho slávnu vetu
Záver o nemožnosti univerzálneho kritéria pravdy je
priamy dôsledok výsledku, ktorý Tarski získal kombináciou
Gödelova veta o nerozhodnuteľnosti s vlastnou teóriou pravdy podľa
pre ktoré nemôže existovať univerzálne kritérium pravdy ani pre relatívne
úzke pole teórie čísel, a teda pre akúkoľvek vedu, ktorá používa
aritmetika. Prirodzene, tento výsledok platí a fortiori pre pojem pravdy
v akejkoľvek nematematickej oblasti poznania, v ktorej je široko
používa sa aritmetika.
Karl Popper
Uspenskij Vladimir Andrejevič sa narodil 27. novembra 1930 v Moskve. Vyštudoval Fakultu mechaniky a matematiky Moskovskej štátnej univerzity (1952). Doktor fyzikálnych a matematických vied (1964). Profesor, vedúci katedry matematickej logiky a teórie algoritmov Fakulty mechaniky a matematiky (1966). Vedie kurzy prednášok "Úvod do matematickej logiky", "Vyčísliteľné funkcie", "Gödelova veta o úplnosti". Pripravených 25 kandidátov a 2 doktori vied
1. Vyjadrenie problému
Veta o neúplnosti, ktorej presnú formuláciu uvedieme na konci tejto kapitoly a možno neskôr (ak to čitateľa zaujíma) a dôkaz, uvádza približne toto: za určitých podmienok v akomkoľvek jazyku existujú pravdivé, ale nepreukázateľné tvrdenia.
Keď formulujeme vetu týmto spôsobom, takmer každé slovo vyžaduje nejaké vysvetlenie. Začneme preto vysvetlením významu slov, ktoré v tejto formulácii používame.
Nebudeme uvádzať najvšeobecnejšiu možnú definíciu jazyka, radšej sa obmedzíme na tie jazykové pojmy, ktoré budeme potrebovať neskôr. Existujú dva takéto pojmy: „abeceda jazyka“ a „súbor pravdivých výrokov jazyka“.
1.1.1. Abeceda
Abecedou rozumieme konečnú množinu elementárnych znakov (teda vecí, ktoré sa nedajú rozdeliť na jednotlivé časti). Tieto znaky sa nazývajú písmená abecedy. Slovom abecedy rozumieme konečný sled písmen. Napríklad bežné slová v angličtine (vrátane vlastných mien) sú slová 54-písmenovej abecedy (26 malých písmen, 26 veľkých písmen, pomlčka a apostrof). Ďalším príkladom je, že prirodzené čísla v desiatkovom zápise sú slová 10-písmenovej abecedy, ktorých písmená sú znaky: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Na označenie abecedy budeme používať obyčajné veľké písmená. Ak L je abeceda, potom L? bude označovať množinu všetkých slov abecedy L - slová utvorené z jej písmen. Budeme predpokladať, že každý jazyk má svoju vlastnú abecedu, takže všetky výrazy tohto jazyka (tj - názvy rôznych predmetov, výroky týkajúce sa týchto predmetov atď.) sú slová tejto abecedy. Napríklad akákoľvek ponuka anglický jazyk, ako aj akýkoľvek text napísaný v angličtine, možno považovať za slovo rozšírenej abecedy s 54 písmenami, ktoré zahŕňa aj interpunkčné znamienka, medzislovnú medzeru, znak červenej čiary a prípadne aj niektoré ďalšie užitočné znaky. Za predpokladu, že výrazy jazyka sú slová nejakej abecedy, vylúčime teda z úvahy „viacvrstvové“ výrazy ako ???f(x)dx. Toto obmedzenie však nie je príliš významné, keďže každý takýto výraz možno pomocou vhodných konvencií „roztiahnuť“ do lineárnej formy. Nejaká množina M obsiahnutá v L? sa nazýva množina slov abecedy L. Ak jednoducho povieme, že M je množina slov, tak máme na mysli, že ide o slovo nejakej abecedy. Vyššie uvedený predpoklad o jazyku možno teraz preformulovať takto: v akomkoľvek jazyku je každá množina výrazov množinou slov.
1.1.2. Veľa pravdivých tvrdení
Predpokladáme, že nám je daná podmnožina T množiny L? (kde L je abeceda nejakého jazyka, o ktorom uvažujeme), čo sa nazýva množina „pravdivých tvrdení“ (alebo jednoducho „právd“). Ak prejdeme priamo k podmnožine T, vynecháme nasledujúce medzikroky uvažovania: po prvé, ktoré slová abecedy L sú správne vytvorené výrazy jazyka, to znamená, že majú určitý význam v našej interpretácii tohto jazyka (napríklad 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 sú dobre vytvorené výrazy, zatiaľ čo výrazy ako +=x nie sú); po druhé, ktoré výrazy sú formule, t.j. môže závisieť od parametra (napríklad x=3, x=y, 2=3, 2=2); po tretie, ktoré zo vzorcov sú uzavreté vzorce, t.j. príkazy, ktoré nezávisia od parametrov (napríklad 2=3, 2=2); a nakoniec, ktoré uzavreté vzorce sú pravdivé výroky (napríklad 2=2).
1.1.3. Základná dvojica jazykov
1.2. "nedokázateľné"
„Nepreukázateľné“ znamená bez dôkazov.
1.3. Dôkaz
Hoci pojem „dôkaz“ je možno jedným z najdôležitejších v matematike (Bourbakiovci začínajú svoju knihu „Základy matematiky“ slovami: „Od čias starovekých Grékov hovoriť ‚matematika‘ znamenalo to isté, čo povedzme „dôkaz“), nemá vlastnú presnú definíciu. Vo všeobecnosti pojem dôkaz so všetkými jeho sémantickými vetvami patrí skôr do oblasti psychológie ako do matematiky. Ale nech je to akokoľvek, dôkaz je jednoducho argument, ktorý sami považujeme za celkom presvedčivý, aby sme presvedčili všetkých ostatných.
Po zapísaní sa dôkaz stane slovom v nejakej abecede P, rovnako ako každý anglický text je slovom v abecede L, ktorej príklad bol uvedený vyššie. Množina všetkých dôkazov tvorí podmnožinu (a dosť rozsiahlu podmnožinu) množiny P?. Nebudeme sa snažiť dať presná definícia tento súčasne „naivný“ a „absolútny“ koncept dôkazu, alebo – čo je ekvivalentné – definovať zodpovedajúcu podmnožinu P?. Namiesto toho budeme uvažovať o formálnej analógii tohto vágneho konceptu, pre ktorý budeme v budúcnosti stále používať termín „dôkaz“. Tento analóg má dve veľmi dôležité vlastnosti, ktoré ho odlišujú od intuitívneho konceptu (hoci intuitívna myšlienka dôkazu tieto vlastnosti do určitej miery stále odráža). Najprv pripustíme, že existujú rôzne koncepty dôkazov, to znamená, že sú prípustné rôzne podmnožiny dôkazov v P, a ešte viac: v skutočnosti pripustíme, že samotná abeceda dôkazov P sa môže meniť? . Ďalej budeme požadovať, aby pre každý takýto koncept dôkazu existoval efektívna metóda, inými slovami, algoritmus, ktorý by nevyhnutne určil, či dané slovo abecedy P je dôkazom alebo nie. Budeme tiež predpokladať, že existuje algoritmus, ktorý vždy dokáže určiť, ktoré tvrdenie daný dôkaz dokazuje. (V mnohých situáciách je tvrdenie, ktoré sa dokazuje, jednoducho posledným tvrdením v poradí krokov, ktoré tvoria dôkaz.)
Naša konečná definícia je teda nasledovná:
(1) Máme abecedu L (jazyková abeceda) a abecedu P (dôkazová abeceda).
(2) Dostali sme množinu P, ktorá je podmnožinou P? a ktorej prvky sa nazývajú „dôkazy“. V budúcnosti budeme predpokladať, že máme aj algoritmus, ktorý nám umožňuje určiť, či ľubovoľné slovo z abecedy P je prvkom množiny P, teda dôkazom, alebo nie.
(3) Máme tiež funkciu? (aby som zistil, čo presne bolo dokázané), o koho ide? spĺňa podmienku P???P?, a ktorého rozsah hodnôt je v P?. Predpokladáme, že máme algoritmus, ktorý túto funkciu počíta ( presná hodnota Slová „algoritmus vypočíta funkciu“ sú nasledovné: hodnoty funkcie sa získajú pomocou tohto algoritmu - súboru špeciálnych transformačných pravidiel). Povieme, že prvok p? P je dôkazom slova?(p) abecedy L.
Trojnásobné splnenie podmienok (1)-(3) sa nazýva deduktívny systém v abecede L.
Pre známeho čitateľa obvyklým spôsobom definíciu „dôkazu“ v pojmoch „axióma“ a „pravidlo inferencie“, teraz vysvetlíme, ako možno túto metódu považovať za špeciálny prípad definície uvedenej v časti 1.3.2. To znamená, že dôkaz je zvyčajne definovaný ako postupnosť takýchto jazykových výrazov, z ktorých každý je buď axióma alebo predtým získaný z už existujúcich tvrdení pomocou jedného z pravidiel vyvodzovania. Ak do abecedy nášho jazyka pridáme nové slovo *, potom môžeme takýto dôkaz napísať vo forme slova zloženého pomocou výslednej úpravy abecedy: sekvenciou výrazov sa stáva slovo C1*C2*...*Cn . V tomto prípade funkcia, ktorá určuje, čo presne bolo dokázané, má svoj význam v časti tohto slova bezprostredne nasledujúcej za posledným písmenom * v poradí. Algoritmus, ktorého existencia sa vyžaduje v časti 1.3.2. definíciu, možno ľahko skonštruovať, keď sme presne definovali ktorýkoľvek z akceptovaných významov slov „axióm“ a „pravidlá inferencie“.
1.4 Pokusy o presné formulovanie vety o neúplnosti
1.4.1. Prvý pokus
"Za určitých podmienok pre základný pár abecedného jazyka L a deduktívny systém nad L vždy existuje slovo v T, ktoré nemá žiadny dôkaz." Táto možnosť stále vyzerá nejasne. Najmä by sme mohli ľahko vymyslieť toľko deduktívnych systémov, koľko chceme, ktoré majú veľmi málo dokázateľných slov. Napríklad v prázdnom dedukčnom systéme (kde P = ?) nie sú vôbec žiadne slová, ktoré by mali dôkaz.
1.4.2. Druhý pokus
Existuje aj iný, prirodzenejší prístup. Predpokladajme, že je nám daný jazyk – v tom zmysle, že je nám daný základný pár tohto jazyka. Teraz budeme hľadať taký deduktívny systém nad L (intuitívne hľadáme dôkazovú techniku), pomocou ktorého by sme dokázali čo najviac slov z T, v limite všetky slová z T. Gödelovej vety opisujú situácia, v ktorej takýto deduktívny systém (pomocou ktorého by bolo dokázateľné každé slovo v T) neexistuje. Preto by sme chceli sformulovať nasledujúce vyhlásenie:
"Za určitých podmienok týkajúcich sa základného páru neexistuje deduktívny systém, v ktorom by každé slovo z T malo dôkaz."
Takéto tvrdenie je však zjavne nepravdivé, pretože je potrebné vziať iba dedukčný systém, v ktorom P = L, P = P? u?(p) = p pre všetky p z P?; potom každé slovo z L? je triviálne dokázateľné. Preto musíme prijať určité obmedzenie, aké deduktívne systémy používame.
1.5. Dôslednosť
Bolo by celkom prirodzené požadovať, aby bolo možné dokázať iba „pravdivé tvrdenia“, teda iba slová z T. Povieme, že deduktívny systém je konzistentný vzhľadom na základný pár if?(P)?T. Vo všetkých nasledujúcich diskusiách nás budú zaujímať iba takéto konzistentné deduktívne systémy. Ak dostaneme jazyk, potom by bolo mimoriadne lákavé nájsť konzistentný deduktívny systém, v ktorom by každé pravdivé tvrdenie malo dôkaz. Verzia Gödelovej vety, ktorá nás zaujíma, presne hovorí, že za určitých podmienok týkajúcich sa základného páru nie je možné nájsť takýto deduktívny systém.
1.6. Úplnosť
Hovorí sa, že deduktívny systém je úplný vzhľadom na základný pár za predpokladu, že?(P)?T. Potom má naša formulácia vety o neúplnosti nasledujúcu formu:
Za určitých podmienok týkajúcich sa základného páru neexistuje deduktívny systém nad L, ktorý by bol úplný a relatívne konzistentný.
Vety matematickej logiky, ktoré ukazujú nemožnosť úplnej formalizácie aritmetiky, ako aj silnejšie matematické teórie. Boli overené a publikované rakúskym. matematik K. Gödel v roku 1931. Prvá veta úzko súvisí s fenoménom algoritmus, nerozhodnuteľnosť, druhá je oveľa subtílnejšie tvrdenie o formálnych systémoch. Obsah prvej vety o neúplnosti (ak sa zatiaľ obmedzíme na aritmetiku) je nasledujúci. Nech A je aritmus. formálny systém obsahujúci Peanove axiómy (pozri Aritmetiku
formálne). V tomto prípade sa predpokladá, že A správne opisuje aritmetiku, t.j. že všetky vzorce odvodené v A sú pravdivé tvrdenia o prirodzené čísla. Pre každý takýto systém A prvá Gödelova veta hovorí, že nie všetky pravdivé aritmetické vzorce sú dokázateľné v A. Inými slovami, pojem pravdivosti aritmických vzorcov. jazyk je širší ako pojem preukázateľnosti v akomkoľvek formálnom systéme (ak je ten druhý správny). Nižšie je intuitívna myšlienka dôkazu tejto vety, ktorá je nevyhnutná pre pochopenie obsahu oboch viet o neúplnosti.
Predpokladajme opak, teda ten aritmus. pravda sa zhoduje s dokázateľnosťou v A. Keďže dôkazy v systéme A sú konečné postupnosti f-l, vzájomne prepojené pravidlami inferencie, potom sa kontroluje, či je daný sekvencia f-l dôkaz, vykonávané pomocou docela jednoduchý algoritmus. S vhodným kódovaním je možné tento algoritmus opísať aritmeticky. jazyk (pozri Aritmetizácia metamatematiky). Preto je možné zostaviť aritmus. f-lu, čo znamená, že x je kód dokázateľného f-ly v A. Teraz nie je ťažké napísať f-lu - nazvime ho v, ktorý vyjadruje vlastnú nedokázateľnosť. Presnejšie povedané, pre tento vzorec v systéme A existuje dokázateľná ekvivalencia:
kde je kód f-ly. Na základe predpokladu, že preukázateľnosť sa zhoduje s pravdou, dostávame, že vyjadruje aj vlastnú nepravdu. Potom však toto f-la nemôže byť ani pravdivé, ani nepravdivé, takže sa dostávame k známemu „paradoxu klamárov“. Preto sa pravda a dokázateľnosť nezhodujú. Príkladom pravdivého, ale nedokázateľného f-ly v A je práve f-la: je pravdivé, keďže tvrdí svoju nepreukázateľnosť a v skutočnosti je nepreukázateľné.
Vyššie uvedené heuristické úvahy v podstate využívajú predpoklad, že v A sú dokázateľné iba pravdivé vzorce. Dôkladnejšia štúdia však ukazuje, že nepreukázateľnosť možno vyvodiť zo slabšieho predpokladu konzistentnosti systému A. Toto objasnenie má zásadný charakter. Ide o to, že koncept aritmov. pravda je nevyjadrená v jazyku aritmetiky, zatiaľ čo tvrdenie o konzistencii A môže byť napísané vo forme pomerne jednoduchej aritmetiky. f-ly. Vďaka tomu možno prvú vetu o neúplnosti vyjadriť v jazyku aritmetiky pomocou vzorca:
Dá sa ukázať, že tento vzorec je odvoditeľný z Peanových axióm. To ľahko vedie k druhej verzii Gödelovej vety o neúplnosti, ktorá (voľne) hovorí, že konzistenciu formálneho systému A nemožno pomocou tohto systému dokázať. Presnejšie, ak je formálny systém A konzistentný a obsahuje Peanove axiómy, potom je f-la v . V skutočnosti z dokázateľnosti f-l (1) a (2) vyplýva, že vzorce a sú ekvivalentné v systéme A. Ale sú nedokázateľné v A, podľa prvej Gödelovej vety; To znamená, že je tiež nepreukázateľný.
Doteraz sme hovorili len o aritmetike. Ale všetky predchádzajúce argumenty platia aj pre dosť svojvoľné formálne systémy. Najmä nie je vôbec potrebné, aby jazyk systému A bol jazykom elementárnej aritmetiky. Jediná vec, ktorá sa tu vyžaduje, je, že zákl pojmy aritmetiky boli vyjadrené v jazyku uvažovaného formálneho systému a Peanove axiómy boli v tomto systéme dokázateľné. Preto Gödelove vety platia pre akúkoľvek rozumnú axiomatizáciu aritmetiky, analýzy alebo teórie množín.
Vety o neúplnosti zdôrazňujú jeden špecifický problém spojený s dôkazmi konzistencie. Jeho podstata je najpohodlnejšie ilustrovaná na príklade teórie plurality. Nech ZF je formálny systém teórie multiplicity založený na Zermelo-Frenkelových axiómach. Pre ZF stále neexistuje dôkaz o konzistentnosti. Vopred však môžeme povedať, že takýto dôkaz musí spĺňať nasledujúce dve požiadavky (z ktorých prvá je určená samotnou formuláciou otázky a druhá vyplýva z Gödelovej vety): a) tento dôkaz sa musí opierať iba o pojmy ktoré sú intuitívne jednoduchšie ako tie, ktoré sa používajú v samotnej teórii mn-v; b) nie je možné vykonať v rámci systému ZF. Systém ZF je však extrémne široký: formalizuje takmer všetku modernú matematiku. Preto je ťažké si predstaviť, ako by vyzerala matematika. dôkaz, ktorý spĺňa špecifikované požiadavky. Dotýka sa tu teda zložitých problémov základov matematiky, vďaka čomu majú Gödelove vety určitý filozofický význam.
Existuje názor, že vety o neúplnosti ukazujú nemožnosť kaše. modelovanie akýchkoľvek netriviálnych foriem duševnej činnosti. Zdá sa, že toto stanovisko nie je dostatočne odôvodnené; G. t. majú rovnaký vzťah k otázke strojovej tvorivosti ako napríklad logické paradoxy tvorivosťľudská myseľ. Otázka schopností „strojovej inteligencie“ je diskutabilná (pozri Umelá inteligencia).
Lit.: Kleene S.K. Per. z angličtiny M., 1973 [bibliogr. s. 451-465); FefermanS. Aritmetizácia metamatematiky vo všeobecnom prostredí. "Pundamenta mathematicae", 1960, v. 49; Lyndon P. Poznámky k logike. Per. z angličtiny M., 1968 [bibliogr. s. 123]; Arbib M. Mozog, stroj a matematika. Per. z angličtiny M., 1968 [bibliogr. s. 217-224]; Nagel E., Newman D. R. Gödelova veta. Per. z angličtiny M., 1970.