Gödelio neužbaigtumo teoremos filosofija. Įdomūs faktai ir naudingi patarimai

Gödelio neužbaigtumo teorema

Uspenskis V.A.

Galbūt Gödelio neužbaigtumo teorema yra tikrai unikali. Jis unikalus tuo, kad į jį kalbama, kai norima įrodyti „viską pasaulyje“ – nuo ​​dievų buvimo iki intelekto nebuvimo. Mane visada domino labiau „pirminis klausimas“ – kuris iš besikreipiančiųjų į nepilnumo teoremą galėtų ją ne tik suformuluoti, bet ir įrodyti? Skelbiu šį straipsnį dėl to, kad jame išdėstyta visiškai prieinama Gödelio teoremos formuluotė. Rekomenduoju pirmiausia perskaityti Tullio Regge'o Kurto Gödelio straipsnį ir jo garsiąją teoremą

Išvada apie universalaus tiesos kriterijaus neįmanomumą yra tiesioginė pasekmė rezultato, kurį Tarski gavo sujungdamas Gödelio teoremą apie neapibrėžtumą su savo paties tiesos teorija, pagal kurią negali būti universalaus tiesos kriterijaus net ir santykinai siauram. skaičių teorijos srityje, taigi ir bet kuriam aritmetiką naudojančiam mokslui. Natūralu, kad šis rezultatas a fortiori taikomas tiesos sampratai bet kurioje ne matematinėje žinių srityje, kurioje aritmetika plačiai naudojama.

Karlas Poperis

Uspenskis Vladimiras Andrejevičius gimė 1930 m. lapkričio 27 d. Maskvoje. Baigė Maskvos valstybinio universiteto Mechanikos ir matematikos fakultetą (1952). Fizinių ir matematikos mokslų daktaras (1964). Profesorius, Mechanikos-matematikos fakulteto Matematinės logikos ir algoritmų teorijos katedros vedėjas (1966). Skaito paskaitų kursus „Įvadas į matematinę logiką“, „Skaičiuojamosios funkcijos“, „Gedelio teorema apie išsamumą“. Parengė 25 kandidatus ir 2 mokslų daktarus

1. Problemos pareiškimas

Neužbaigtumo teorema, kurios tikslią formuluotę pateiksime šio skyriaus pabaigoje, o gal ir vėliau (jei skaitytoją tai domina) ir įrodymą, teigia maždaug taip: tam tikromis sąlygomis bet kurioje kalboje yra teisingi, bet neįrodomi teiginiai.

Kai taip formuluojame teoremą, beveik kiekvienas žodis reikalauja paaiškinimo. Todėl pradėsime paaiškindami žodžių, kuriuos vartojame šioje formuluotėje, reikšmę.

1.1. Kalba

Mes nepateiksime bendriausio įmanomo kalbos apibrėžimo, apsiribodami tomis kalbos sąvokomis, kurių mums prireiks vėliau. Yra dvi tokios sąvokos: „kalbos abėcėlė“ ir „tikrų kalbos teiginių rinkinys“.

1.1.1. Abėcėlė

Pagal abėcėlę turime omenyje baigtinį elementariųjų ženklų rinkinį (tai yra dalykų, kurių negalima suskirstyti į sudedamąsias dalis). Šie ženklai vadinami abėcėlės raidėmis. Abėcėlės žodžiu turime omenyje baigtinę raidžių seką. Pavyzdžiui, įprasti žodžiai anglų kalba (įskaitant tinkamus vardus) yra 54 raidžių abėcėlės žodžiai (26 mažosios raidės, 26 didžiosios raidės, brūkšnys ir apostrofas). Kitas pavyzdys – natūralūs skaičiai dešimtainėje raidėje yra 10 raidžių abėcėlės žodžiai, kurių raidės yra ženklai: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Abėcėlėms žymėti naudosime paprastosios didžiosios raidės. Jei L yra abėcėlė, tai L? žymės visų abėcėlės žodžių aibę L – žodžiai, sudaryti iš jos raidžių. Darysime prielaidą, kad bet kuri kalba turi savo abėcėlę, todėl visi šios kalbos posakiai (ty įvairių objektų pavadinimai, teiginiai apie šiuos objektus ir pan.) yra šios abėcėlės žodžiai. Pavyzdžiui, bet koks sakinys anglų kalba, taip pat bet koks tekstas, parašytas anglų kalba, gali būti laikomas žodžiu išplėstinėje 54 raidžių abėcėlėje, kurioje taip pat yra skyrybos ženklai, tarpo tarpas, raudonos linijos ženklas ir galbūt kai kurie kiti naudingi simboliai. . Darant prielaidą, kad kalbos posakiai yra tam tikros abėcėlės žodžiai, mes neįtraukiame dėmesio į „daugiasluoksnes“ išraiškas, tokias kaip ???f(x)dx. Tačiau šis apribojimas nėra per daug reikšmingas, nes bet kuri tokia išraiška, naudojant tinkamus susitarimus, gali būti „ištempta“ į linijinę formą. Bet koks rinkinys M yra L? vadinamas abėcėlės L žodžių aibe. Jei tiesiog sakome, kad M yra žodžių aibė, tai reiškia, kad tai yra kokios nors abėcėlės žodis. Dabar aukščiau pateiktą prielaidą apie kalbą galima perfrazuoti taip: bet kurioje kalboje bet koks posakių rinkinys yra žodžių rinkinys.

1.1.2. Daug teisingų teiginių

Darome prielaidą, kad mums duota aibės L poaibis T? (kur L yra tam tikros mūsų svarstomos kalbos abėcėlė), kuri vadinama „tikrųjų teiginių“ (arba tiesiog „tiesų“) rinkiniu. Pereidami tiesiai į poaibį T, praleidžiame šiuos tarpinius samprotavimo žingsnius: pirma, kurie abėcėlės L žodžiai yra teisingai suformuoti kalbos posakiai, tai yra, turintys tam tikrą reikšmę mūsų šios kalbos interpretacijoje (pvz., 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 yra gerai suformuotos išraiškos, o tokios išraiškos kaip +=x nėra); antra, kokios išraiškos yra formulės, t.y. gali priklausyti nuo parametro (pavyzdžiui, x=3, x=y, 2=3, 2=2); trečia, kurios iš formulių yra uždarosios formulės, t.y. teiginiai, kurie nepriklauso nuo parametrų (pvz., 2=3, 2=2); ir galiausiai, kurios uždarosios formulės yra teisingi teiginiai (pavyzdžiui, 2=2).

1.1.3. Pagrindinė kalbų pora

1.2. "Neįrodoma"

„Neįrodoma“ reiškia be įrodymų.

1.3. Įrodymas

Nors terminas „įrodymas“ yra bene vienas svarbiausių matematikoje (savo knygą „Matematikos pagrindai“ burbakiai pradeda žodžiais: „Nuo senovės graikų laikų sakyti „matematika“ reiškia tą patį, kaip pasakyti „įrodymas“), jis neturi savo tikslaus apibrėžimo. Apskritai įrodymo sąvoka su visomis semantinėmis šakomis labiau priklauso psichologijos, o ne matematikos sričiai. Bet kad ir kaip būtų, įrodymas yra tiesiog argumentas, kurį mes patys laikome gana įtikinamu, kad įtikintume visus kitus.

Užrašytas įrodymas tampa tam tikros abėcėlės P žodžiu, kaip ir bet koks angliškas tekstas yra L abėcėlės žodis, kurio pavyzdys buvo pateiktas aukščiau. Visų įrodymų aibė sudaro aibės P? poaibį (ir gana platų poaibį). Mes nebandysime tiksliai apibrėžti šios vienu metu „naivios“ ir „absoliučios“ įrodymo sąvokos arba – kas yra lygiavertė – pateikti atitinkamo P? poaibio apibrėžimą. Vietoje to apsvarstysime formalų šios neaiškios sąvokos analogą, kuriam ateityje vis tiek vartosime terminą „įrodymas“. Šis analogas turi dvi labai svarbias ypatybes, kurios išskiria jį nuo intuityvios koncepcijos (nors intuityvi įrodinėjimo idėja vis dar tam tikru mastu atspindi šias savybes). Pirmiausia pripažinsime, kad egzistuoja skirtingos įrodymų sąvokos, t. . Toliau reikalausime, kad kiekvienai tokiai įrodymo sąvokai egzistuotų veiksmingas metodas, kitaip tariant, algoritmas, kuris būtinai nustatytų, ar duotas P abėcėlės žodis yra įrodymas, ar ne. Taip pat manysime, kad yra algoritmas, kuris visada gali nustatyti, kurį teiginį įrodo pateiktas įrodymas. (Daugeliu atvejų įrodomas teiginys yra tiesiog paskutinis teiginys veiksmų sekoje, kuri sudaro įrodymą.)

Taigi galutinis mūsų apibrėžimas yra toks:

(1) Turime abėcėlę L (kalbos abėcėlė) ir abėcėlę P (įrodomąją abėcėlę).

(2) Mums duota aibė P, kuri yra P? poaibis ir kurios elementai vadinami „įrodymais“. Ateityje manysime, kad turime ir algoritmą, leidžiantį nustatyti, ar savavališkas abėcėlės P žodis yra aibės P elementas, tai yra įrodymas, ar ne.

(3) Ar mes taip pat turime funkciją? (norėdami sužinoti, kas tiksliai buvo įrodyta), kieno tai yra? atitinka sąlygą P???P?, o kurio reikšmių diapazonas yra P?. Darome prielaidą, kad turime algoritmą, kuris apskaičiuoja šią funkciją (tiksli žodžių „algoritmas apskaičiuoja funkciją“ reikšmė yra tokia: funkcijos reikšmės gaunamos naudojant šį algoritmą – specialių transformacijos taisyklių rinkinį). Sakysime, kad elementas p? P yra abėcėlės L žodžio?(p) įrodymas.

Troika<Р, Р, ?>, tenkinanti sąlygas (1)-(3), vadinama dedukcine sistema per abėcėlę L.

Skaitytojui, susipažinusiam su įprastu „įrodymų“ apibrėžimo būdu „aksioma“ ir „išvados taisyklėmis“, dabar paaiškinsime, kaip šį metodą galima laikyti ypatingu 1.3.2 skirsnyje pateikto apibrėžimo atveju. Tai yra, įrodymas paprastai apibrėžiamas kaip tokių kalbos posakių seka, kurių kiekviena yra arba aksioma, arba anksčiau gauta iš jau esamų teiginių, naudojant vieną iš išvados taisyklių. Jei į mūsų kalbos abėcėlę įtrauksime naują žodį *, tai tokį įrodymą galime parašyti žodžio forma, sudaryta naudojant gautą abėcėlės modifikaciją: posakių seka tampa žodžiu C1*C2*...*Cn . Šiuo atveju funkcija, kuri nustato, kas tiksliai buvo įrodyta, turi reikšmę šio žodžio dalyje, iškart po paskutinės sekos raidės *. Algoritmas, kurio egzistavimo reikalaujama 1.3.2 dalyje. apibrėžimą galima lengvai sudaryti, kai tiksliai apibrėžiame bet kurią iš priimtų žodžių „aksioma“ ir „išvados taisyklės“ reikšmių.

1.4 Bandoma tiksliai suformuluoti neužbaigtumo teoremą

1.4.1. Pirmas bandymas

„Esant tam tikroms sąlygoms pagrindinei abėcėlės kalbos L porai ir dedukcinei sistemai<Р, Р, ?>virš L – visada yra žodis T, kuris neturi įrodymų." Ši parinktis vis dar atrodo neaiški. Visų pirma, galėtume lengvai sugalvoti bet kokį skaičių dedukcinių sistemų, kuriose yra labai mažai įrodomų žodžių. Pavyzdžiui, tuščiame dedukciniame sistemoje (kur P =?) iš viso nėra žodžių, kurie turėtų įrodymų.

1.4.2. Antras bandymas

Yra ir kitas, natūralesnis požiūris. Tarkime, kad mums duota kalba – ta prasme, kad mums duota pagrindinė šios kalbos pora. Dabar ieškosime tokios dedukcinės sistemos virš L (intuityviai ieškome įrodinėjimo technikos), kurios pagalba galėtume įrodyti kuo daugiau žodžių iš T, riboje visi žodžiai iš T. Gödelio teoremos apibūdina situacija, kai tokios dedukcinės sistemos (kurios pagalba būtų įrodomas kiekvienas žodis T) nėra. Taigi norėtume suformuluoti tokį teiginį:

„Esant tam tikroms pagrindinės poros sąlygoms, neegzistuoja dedukcinė sistema, kurioje kiekvienas žodis iš T turėtų įrodymą.

Tačiau toks teiginys akivaizdžiai klaidingas, nes tereikia imti dedukcinę sistemą, kurioje P = L, P = P? u?(p) = p visiems p iš P?; tada kiekvienas žodis iš L? yra trivialiai įrodoma. Todėl turime priimti tam tikrus apribojimus, kokias dedukcines sistemas naudojame.

1.5. Nuoseklumas

Būtų visiškai natūralu reikalauti, kad būtų įrodinėjami tik „tikri teiginiai“, tai yra tik žodžiai iš T. Sakysime, kad dedukcinė sistema<Р, Р, ?>yra suderinamas su pagrindine pora if?(P)?T. Visose tolesnėse diskusijose mus domina tik tokios nuoseklios dedukcinės sistemos. Jei mums būtų duota kalba, būtų labai viliojanti rasti nuoseklią dedukcinę sistemą, kurioje kiekvienas teisingas teiginys turėtų įrodymą. Mus dominanti Gödelio teoremos versija tiksliai teigia, kad esant tam tikroms pagrindinės poros sąlygoms, tokios dedukcinės sistemos rasti neįmanoma.

1.6. Išbaigtumas

Sakoma, kad dedukcinė sistema<Р,Р,?>yra baigtas pagrindinės poros atžvilgiu, jei?(P)?T. Tada mūsų neužbaigtumo teoremos formuluotė įgauna tokią formą:

Tam tikromis sąlygomis pagrindinės poros atžvilgiu tokios dedukcinės sistemos nėra<Р,Р,?>virš L, kuris būtų išsamus ir palyginti nuoseklus.

Nuorodos

Šiam darbui parengti buvo panaudota medžiaga iš svetainės http://filosof.historic.ru

Viena iš žinomiausių matematinės logikos teoremų yra laiminga ir nepasisekusi tuo pačiu metu. Tuo jis panašus į specialiąją Einšteino reliatyvumo teoriją. Viena vertus, beveik visi yra ką nors apie juos girdėję. Kita vertus, populiariai aiškinant, Einšteino teorija, kaip žinoma, „sako, kad viskas pasaulyje yra reliatyvu“. Ir Gödelio teorema apie neužbaigtumą (toliau tiesiog TGN), maždaug ta pačia laisva liaudies formuluote, "įrodo, kad yra dalykų, kurie žmogaus protu nesuvokiami". Ir todėl vieni bando tai pritaikyti kaip argumentą prieš materializmą, o kiti, priešingai, jo pagalba įrodo, kad Dievo nėra. Juokingiausia ne tik tai, kad abi pusės negali būti teisios vienu metu, bet ir tai, kad nei viena, nei kita nesivargina išsiaiškinti, ką iš tikrųjų teigia ši teorema.

Taigi ką? Žemiau pabandysiu apie tai pasakyti ant pirštų. Mano pristatymas, žinoma, bus negriežtas ir intuityvus, bet paprašysiu matematikų manęs griežtai nesmerkti. Gali būti, kad ne matematikams (iš kurių, tiesą sakant, aš esu vienas), bus kažkas naujo ir naudingo, kas aprašyta žemiau.

Matematinė logika iš tiesų yra gana sudėtingas mokslas, o svarbiausia – nelabai pažįstamas. Tai reikalauja kruopštaus ir griežto manevravimo, kai svarbu nepainioti to, kas iš tikrųjų buvo įrodyta, su tuo, kas „jau aišku“. Tačiau tikiuosi, kad norint suprasti toliau pateiktą „TGN įrodymo metmenis“, skaitytojui tereikia vidurinės mokyklos matematikos/kompiuterijos žinių, loginio mąstymo įgūdžių ir 15-20 minučių laiko.

Šiek tiek supaprastinus, TGN tvirtina, kad pakankamai sudėtingomis kalbomis yra neįrodomų teiginių. Tačiau šioje frazėje beveik kiekvieną žodį reikia paaiškinti.

Pradėkime nuo bandymo išsiaiškinti, kas yra įrodymas. Paimkime mokyklinį aritmetinį uždavinį. Pavyzdžiui, tarkime, kad jums reikia įrodyti šios paprastos formulės teisingumą: „ “ (priminsiu, kad simbolis yra „bet kuriam“ ir vadinamas „universaliu kvantoriumi“). Galite tai įrodyti identiškai transformuodami, tarkime, taip:

Perėjimas nuo vienos formulės prie kitos vyksta pagal tam tikras gerai žinomas taisykles. Perėjimas nuo 4-osios formulės prie 5-osios įvyko, tarkime, todėl, kad kiekvienas skaičius yra lygus sau pačiam - tai aritmetikos aksioma. Taigi visa įrodinėjimo procedūra formulę paverčia Būlio verte TRUE. Rezultatas gali būti ir MELAS – jei paneigtume kokią nors formulę. Tokiu atveju įrodytume jos neigimą. Galima įsivaizduoti programą (o tokios programos iš tikrųjų buvo parašytos), kuri įrodytų panašius (ir sudėtingesnius) teiginius be žmogaus įsikišimo.

Tą patį pasakykime kiek formaliau. Tarkime, kad turime aibę, susidedančią iš kokios nors abėcėlės simbolių eilučių, ir yra taisyklės, pagal kurias iš šių eilučių galime pasirinkti poaibį vadinamosios. pareiškimus- tai yra gramatiškai prasmingos frazės, kurių kiekviena yra teisinga arba klaidinga. Galime sakyti, kad yra funkcija, kuri susieja teiginius su viena iš dviejų reikšmių: TRUE arba FALSE (tai yra, susiejant juos su dviejų elementų Būlio rinkiniu).

Pavadinkime tokią porą – teiginių rinkinį ir funkciją nuo iki – „pareiškimų kalba“. Atkreipkite dėmesį, kad kasdienine prasme kalbos sąvoka yra kiek platesnė. Pavyzdžiui, rusiška frazė "Ateik čia!" nei teisinga, nei klaidinga, tai yra matematinės logikos požiūriu, tai nėra teiginys.

Dėl to mums reikia algoritmo sąvokos. Čia nepateiksiu formalaus jo apibrėžimo – tai nuves mus gana toli. Apsiribosiu neoficialia: "algoritmas" yra vienareikšmių nurodymų seka („programa“), kuri baigtiniu žingsnių skaičiumi paverčia šaltinio duomenis į rezultatus. Tai, kas parašyta kursyvu, yra iš esmės svarbu – jei programa apjungia tam tikrus pradinius duomenis, ji neaprašo algoritmo. Dėl paprastumo ir pritaikymo mūsų atveju skaitytojas gali manyti, kad algoritmas yra programa, parašyta bet kuria jam žinoma programavimo kalba, kuri, esant bet kokiems tam tikros klasės įvesties duomenims, garantuotai užbaigs savo darbą ir pateiks Būlio rezultatą.

Paklauskime savęs: kiekvienai funkcijai yra „įrodinėjimo algoritmas“ (arba trumpai tariant, "dedukcinis"), lygiavertis šiai funkcijai, ty kiekvieną teiginį paversti lygiai tokia pačia Būlio verte kaip ir ji? Tą patį klausimą galima suformuluoti glaustai taip: ar kiekviena funkcija yra virš teiginių rinkinio apskaičiuojamas? Kaip jau spėjote, iš TGN galiojimo išplaukia, kad ne, ne kiekviena funkcija - yra tokio tipo neapskaičiuojamų funkcijų. Kitaip tariant, ne kiekvienas teisingas teiginys gali būti įrodytas.

Labai gali būti, kad šis pareiškimas sukels jumyse vidinį protestą. Taip yra dėl kelių aplinkybių. Pirma, kai mus moko mokyklinės matematikos, kartais susidaro klaidingas įspūdis, kad frazės „teorema yra teisinga“ ir „teoremą galima įrodyti arba patikrinti“ yra beveik visiškai identiškos. Bet jei gerai pagalvoji, tai nėra visiškai akivaizdu. Kai kurios teoremos įrodomos gana paprastai (pavyzdžiui, išbandant nedidelį skaičių variantų), o kitos yra labai sunkios. Apsvarstykite, pavyzdžiui, garsiąją Ferma paskutinę teoremą:

kurio įrodymas buvo rastas tik praėjus trims su puse šimtmečio po pirmosios formuluotės (ir tai toli gražu ne elementaru). Būtina atskirti teiginio teisingumą ir jo įrodomumą. Iš niekur neišplaukia, kad nėra teisingų, bet neįrodomų (ir nevisiškai patikrinamų) teiginių.

Antrasis intuityvus argumentas prieš TGN yra subtilesnis. Tarkime, kad turime neįrodomą (šio dedukcinio) teiginį. Kas mums trukdo priimti tai kaip naują aksiomą? Taigi mes šiek tiek apsunkinsime savo įrodymų sistemą, tačiau tai nėra baisu. Šis argumentas būtų visiškai teisingas, jei būtų baigtinis skaičius neįrodomų teiginių. Praktikoje gali nutikti taip: postulavęs naują aksiomą, užklysti ant naujo neįrodomo teiginio. Jei priimsite tai kaip kitą aksiomą, suklupsite prie trečiosios. Ir taip toliau iki begalybės. Jie sako, kad išskaitymas liks nepilnas. Taip pat galime priversti įrodinėjimo algoritmą užbaigti baigtiniu žingsnių skaičiumi su tam tikru rezultatu bet kuriai kalbos ištarai. Tačiau tuo pat metu jis pradės meluoti – veda prie tiesos dėl neteisingų teiginių arba į melą – tikintiesiems. Tokiais atvejais jie sako, kad atskaitymas prieštaringi. Taigi kita TGN formuluotė skamba taip: „Yra teiginių kalbų, kurioms visiškas nuoseklus deduktyvumas neįmanomas“ - taigi ir teoremos pavadinimas.

Kartais vadinamas „Gödelio teorema“, teiginys, kad bet kurioje teorijoje yra problemų, kurių negalima išspręsti pačios teorijos rėmuose ir kurias reikia apibendrinti. Tam tikra prasme tai tiesa, nors ši formuluotė labiau užgožia problemą, nei ją paaiškina.

Taip pat atkreipsiu dėmesį, kad jei kalbėtume apie pažįstamas funkcijas, kurios į ją susieja realiųjų skaičių aibę, tai funkcijos „neapskaičiuojamumas“ nieko nenustebintų (tik nepainiokite „apskaičiuojamų funkcijų“ ir „skaičiuojamų skaičių“). “ – tai skirtingi dalykai). Bet kuris moksleivis žino, kad, tarkime, funkcijos atveju jums turi labai pasisekti su argumentu, kad tikslaus šios funkcijos reikšmės dešimtainės dalies apskaičiavimo procesas būtų baigtas baigtiniu žingsnių skaičiumi. Bet greičiausiai jūs jį apskaičiuosite naudodami begalinę eilutę, ir šis skaičiavimas niekada neduos tikslaus rezultato, nors jis gali būti tiek arti, kiek norite – vien todėl, kad daugumos argumentų sinuso reikšmė yra neracionali. TGN tiesiog mums sako, kad net tarp funkcijų, kurių argumentai yra eilutės ir kurių reikšmės yra nulis arba viena, yra ir neapskaičiuojamų funkcijų, nors jos struktūrizuotos visiškai kitaip.

Tolimesniems tikslams apibūdinsime „formaliosios aritmetikos kalbą“. Apsvarstykite baigtinio ilgio teksto eilučių klasę, susidedančią iš arabiškų skaitmenų, kintamųjų (lotyniškos abėcėlės raidžių), paimančių natūralias reikšmes, tarpus, aritmetinius ženklus, lygybę ir nelygybę, kiekybinius rodiklius ("egzistuoja") ir ("bet kuriam") ir , galbūt , kai kurie kiti simboliai (tikslus jų skaičius ir sudėtis mums nesvarbu). Akivaizdu, kad ne visos tokios eilutės yra prasmingos (pavyzdžiui, „ “ yra nesąmonė). Šios klasės prasmingų posakių poaibis (ty eilutės, kurios teisingos arba klaidingos įprastos aritmetikos požiūriu) bus mūsų teiginių rinkinys.

Formalių aritmetinių teiginių pavyzdžiai:

ir tt Dabar pavadinkime „formulę su laisvuoju parametru“ (FSP) eilute, kuri tampa teiginiu, jei į jį kaip šį parametrą pakeičiamas natūralusis skaičius. FSP pavyzdžiai (su parametru):

ir tt Kitaip tariant, FSP yra lygiavertės natūralioms argumentų funkcijoms su Būlio reikšmėmis.

Visų FSP aibę pažymėkime raide . Aišku, kad galima surikiuoti (pavyzdžiui, iš pradžių išrašome abėcėlės tvarka išdėstytas vienos raidės formules, po to dvi raides ir pan.; mums nesvarbu, kokia abėcėlė vyks rikiavimas). Taigi bet kuris FSP atitinka jo numerį užsakytame sąraše, ir mes jį pažymėsime .

Dabar pereikime prie TGN įrodymo eskizo šioje formuluotėje:

• Formaliosios aritmetikos teiginių kalbai nėra visos nuoseklios dedukcinės sistemos.

Mes tai įrodysime prieštaravimu.

Taigi, tarkime, kad tokia dedukcinė sistema egzistuoja. Apibūdinkime šį pagalbinį algoritmą, kuris natūraliam skaičiui priskiria Būlio reikšmę taip:

Paprasčiau tariant, algoritmas pateikia reikšmę TRUE tada ir tik tada, kai mūsų sąrašo FSP pakeitus savo numerį gaunamas klaidingas teiginys.

Čia mes priėjome prie vienintelės vietos, kur paprašysiu skaitytojo pasitarti.

Akivaizdu, kad remiantis pirmiau padaryta prielaida, bet kurį FSP galima palyginti su algoritmu, kurio įvestyje yra natūralusis skaičius, o išvestyje - Būlio reikšmė. Priešingai yra mažiau akivaizdu:

Šios lemos įrodymui reikėtų bent formalaus, o ne intuityvaus algoritmo sąvokos apibrėžimo. Tačiau, jei šiek tiek pagalvoji, tai gana tikėtina. Tiesą sakant, algoritmai parašyti algoritminėmis kalbomis, tarp kurių yra ir tokių egzotiškų, kaip, pavyzdžiui, „Brainfuck“, susidedantis iš aštuonių vieno simbolio žodžių, kuriuose vis dėlto galima įgyvendinti bet kurį algoritmą. Būtų keista, jei mūsų aprašyta turtingesnė formaliosios aritmetikos formulių kalba pasirodytų prastesnė – nors, be jokios abejonės, ji nelabai tinka įprastam programavimui.

Pravažiavę šią slidžią vietą, greitai pasiekiame pabaigą.

Taigi, aukščiau aprašėme algoritmą. Pagal lemą, kuria paprašiau patikėti, yra lygiavertis FSP. Sąraše yra tam tikras skaičius – tarkime, . Paklauskime savęs, kam tolygu? Tegul tai būna TIESA. Tada pagal algoritmo (taigi ir jam lygiavertės funkcijos) konstrukciją tai reiškia, kad skaičiaus pakeitimo į funkciją rezultatas yra FALSE. Lygiai taip pat tikrinama ir priešingybė: nuo FALSE seka TRUE. Mes pasiekėme prieštaravimą, o tai reiškia, kad pirminė prielaida yra neteisinga. Taigi formaliai aritmetikai nėra visos nuoseklios dedukcinės sistemos. Q.E.D.

Čia dera prisiminti Epimenidą (žr. portretą pavadinime), kuris, kaip žinoma, pareiškė, kad visi kretiečiai yra melagiai, pats būdamas kretietis. Trumpiau suformulavus, jo teiginys (žinomas kaip „melagių paradoksas“) gali būti išreikštas taip: „Aš meluoju“. Kaip tik tokį teiginį, kuris pats skelbia savo klaidingumą, mes panaudojome įrodymui.

Baigdamas noriu pažymėti, kad TGN nepretenduoja į ką nors ypač stebinančio. Juk visi jau seniai priprato prie to, kad ne visus skaičius galima pavaizduoti kaip dviejų sveikųjų skaičių santykį (atminkite, šis teiginys turi labai elegantišką įrodymą, kuriam daugiau nei du tūkstančiai metų?). Ir ne visi skaičiai yra daugianario šaknys su racionaliais koeficientais. Ir dabar paaiškėja, kad ne visos natūralaus argumento funkcijos yra apskaičiuojamos.

Pateiktas įrodymo eskizas buvo skirtas formaliai aritmetikai, tačiau nesunku pastebėti, kad TGN tinka daugeliui kitų teiginių kalbų. Žinoma, ne visos kalbos yra tokios. Pavyzdžiui, apibrėžkime kalbą taip:

• „Bet kuri frazė kinų kalba yra teisinga, jei ji yra draugo Mao Zedongo citatų knygoje, ir neteisinga, jei jos nėra.

Tada atitinkamas išsamus ir nuoseklus įrodinėjimo algoritmas (gali būti vadinamas „dogmatiniu dedukciniu“) atrodo maždaug taip:

• „Vartykite draugo Mao Zedongo citatų knygą, kol rasite posakį, kurio ieškote. Jei randama, vadinasi, tiesa, bet jei citatų knygelė baigta ir teiginys nerastas, vadinasi, jis neteisingas.

Čia mus gelbsti tai, kad bet kuri citatų knyga yra akivaizdžiai baigtinė, todėl „įrodinėjimo“ procesas neišvengiamai baigsis. Taigi TGN netaikomas dogmatinių teiginių kalbai. Bet mes kalbėjome apie sudėtingas kalbas, tiesa?

Bet kuri matematinių aksiomų sistema, pradedant nuo tam tikro sudėtingumo lygio, yra arba viduje prieštaraujanti, arba neišsami.

1900 m. Paryžiuje įvyko Pasaulinė matematikų konferencija, kurioje Davidas Hilbertas (1862–1943) tezių forma pristatė 23 svarbiausias, jo nuomone, problemas, kurias turėjo išspręsti ateinančio XX amžiaus teoretikai. Antras numeris jo sąraše buvo viena iš tų paprastų problemų, kurios atsakymas atrodo akivaizdus, ​​kol neįsigilini. Šiuolaikiškai kalbant, toks buvo klausimas: ar matematika yra savarankiška? Antroji Hilberto užduotis susivedė į poreikį griežtai įrodyti, kad aksiomų sistema – pagrindiniai teiginiai, matematikoje priimami kaip pagrindas be įrodymų – yra tobula ir išbaigta, tai yra leidžia matematiškai apibūdinti viską, kas egzistuoja. Reikėjo įrodyti, kad galima apibrėžti tokią aksiomų sistemą, kad jos, pirma, būtų tarpusavyje nuoseklios, antra, iš jų būtų galima padaryti išvadą dėl bet kurio teiginio teisingumo ar klaidingumo.

Paimkime pavyzdį iš mokyklos geometrijos. Standartinėje Euklido planimetrijoje (geometrija plokštumoje) galima neabejotinai įrodyti, kad teiginys „trikampio kampų suma yra 180°“ yra teisingas, o teiginys „trikampio kampų suma yra 137“ °“ yra klaidinga. Iš esmės Euklido geometrijoje bet koks teiginys yra klaidingas arba teisingas, ir nėra trečios galimybės. O XX amžiaus pradžioje matematikai naiviai tikėjo, kad bet kurioje logiškai nuoseklioje sistemoje turi būti stebima tokia pati situacija.

Ir tada, 1931 m., koks nors akiniuotas Vienos matematikas Kurtas Gödelis paskelbė trumpą straipsnį, kuris tiesiog sutrikdė visą vadinamosios „matematinės logikos“ pasaulį. Po ilgų ir sudėtingų matematinių ir teorinių preambulių jis pažodžiui nustatė štai ką. Paimkime bet kurį teiginį, pavyzdžiui: „Šios aksiomų sistemos prielaida Nr. 247 yra logiškai neįrodoma“ ir pavadinkime ją „teiginiu A“. Taigi Gödelis tiesiog įrodė tokią nuostabią bet kurios aksiomų sistemos savybę:

„Jei teiginys A gali būti įrodytas, tada teiginys ne A gali būti įrodytas.

Kitaip tariant, jeigu teiginio „247 prielaida neįrodoma“ pagrįstumą galima įrodyti, tai teiginio „247 prielaida yra įrodoma“ pagrįstumą taip pat galima įrodyti. Tai yra, grįžtant prie antrosios Hilberto problemos formulavimo, jei aksiomų sistema yra baigta (tai yra, bet kuris joje esantis teiginys gali būti įrodytas), tada ji yra prieštaringa.

Vienintelė išeitis iš šios situacijos yra priimti nepilną aksiomų sistemą. Tai reiškia, kad turime susitaikyti su tuo, kad bet kokios loginės sistemos kontekste vis tiek turėsime „A tipo“ teiginius, kurie yra akivaizdžiai teisingi arba klaidingi – ir mes galime spręsti apie jų teisingumą tik už mūsų turimos aksiomatikos rėmų. priimtas. Jei tokių teiginių nėra, tai mūsų aksiomatika yra prieštaringa ir jos rėmuose neišvengiamai atsiras formuluočių, kurias galima ir įrodyti, ir paneigti.

Taigi, Gödelio pirmosios, arba silpnosios, neužbaigtumo teoremos formuluotė: „Bet kuri formali aksiomų sistema turi neišspręstų prielaidų“. Tačiau Gödelis tuo nesustojo, suformuluodamas ir įrodinėdamas antrąją, arba stiprią, Gödelio neužbaigtumo teoremą: „Jokios aksiomų sistemos loginio užbaigtumo (arba neužbaigtumo) negalima įrodyti šios sistemos rėmuose. Norint tai įrodyti ar paneigti, reikalingos papildomos aksiomos (sistemos stiprinimas).“

Saugiau būtų manyti, kad Gödelio teoremos yra abstrakčios prigimties ir liečia ne mus, o tik didingos matematinės logikos sritis, tačiau iš tikrųjų paaiškėjo, kad jos yra tiesiogiai susijusios su žmogaus smegenų sandara. Anglų matematikas ir fizikas Rogeris Penrose'as (g. 1931 m.) parodė, kad Gödelio teoremos gali būti naudojamos įrodant esminių skirtumų tarp žmogaus smegenų ir kompiuterio egzistavimą. Jo samprotavimų prasmė paprasta. Kompiuteris veikia griežtai logiškai ir negali nustatyti, ar teiginys A yra teisingas ar klaidingas, jei jis peržengia aksiomatikos ribas, o tokie teiginiai, remiantis Gödelio teorema, neišvengiamai egzistuoja. Žmogus, susidūręs su tokiu logiškai neįrodomu ir nepaneigiamu teiginiu A, visada gali nustatyti jo teisingumą ar klaidingumą – remdamasis kasdiene patirtimi. Bent jau šiuo požiūriu žmogaus smegenys yra pranašesnės už kompiuterį, kurį suvaržo grynos loginės grandinės. Žmogaus smegenys gali suprasti visą Gödelio teoremose esančios tiesos gylį, tačiau kompiuterinės smegenys niekada to nesugeba. Todėl žmogaus smegenys yra ne kas kita, o kompiuteris. Jis sugeba priimti sprendimus ir išlaikys Turingo testą.

Įdomu, ar Hilbertas suprato, kaip toli jo klausimai mus nuves?

Kurtas GÖDEL
Kurtas Godelis, 1906–78

Austrijos, vėliau amerikiečių matematikas. Gimė Briunne (dabar Brno, Čekija). Baigė Vienos universitetą, kur liko matematikos katedros mokytojas (nuo 1930 m. profesorius). 1931 m. jis paskelbė teoremą, kuri vėliau gavo jo pavadinimą. Būdamas grynai apolitiškas žmogus, jis nepaprastai sunkiai išgyveno nacių studento įvykdytą savo draugo ir katedros kolegos nužudymą ir pateko į gilią depresiją, kurios atkryčiai jį persekiojo visą likusį gyvenimą. 1930-aisiais emigravo į JAV, bet grįžo į gimtąją Austriją ir vedė. 1940 m., pačiame karo įkarštyje, jis buvo priverstas bėgti į Ameriką tranzitu per SSRS ir Japoniją. Kurį laiką dirbo Prinstono pažangiųjų studijų institute. Deja, mokslininko psichika negalėjo to pakęsti, ir jis mirė psichiatrijos klinikoje iš bado, atsisakęs valgyti, nes buvo įsitikinęs, kad jie jį nunuodys.

Kaip gamtos moksluose vystosi mokslinis modelis? Sukaupta kasdienė ar mokslinė patirtis, jos gairės kruopščiai suformuluotos postulatų pavidalu ir sudaro modelio pagrindą: teiginių rinkinį, kurį priima visi, dirbantys šio modelio rėmuose.

Anatolijus Wassermanas

1930 m. Kurtas Gödelis įrodė dvi teoremas, kurios, išverstos iš matematikos kalbos į žmonių kalbą, reiškia maždaug taip: Bet kuri aksiomų sistema, pakankamai turtinga, kad ją būtų galima panaudoti aritmetikai apibrėžti, bus arba neišsami, arba prieštaringa. Ne pilna sistema – tai reiškia, kad sistemoje galima suformuluoti teiginį, kurio šios sistemos pagalba negalima nei įrodyti, nei paneigti. Tačiau Dievas pagal apibrėžimą yra galutinė visų priežasčių priežastis. Matematikos požiūriu tai reiškia, kad įvedus aksiomą apie Dievą visa mūsų aksiomatika tampa užbaigta. Jei Dievas yra, tai bet koks teiginys gali būti įrodytas arba paneigtas, vienaip ar kitaip nurodant Dievą. Tačiau, pasak Gödelio, visa aksiomų sistema neišvengiamai prieštaringa. Tai yra, jei tikime, kad Dievas egzistuoja, tada esame priversti prieiti prie išvados, kad gamtoje galimi prieštaravimai. O kadangi prieštaravimų nėra, kitaip nuo šių prieštaravimų subyrėtų visas mūsų pasaulis, turime prieiti prie išvados, kad Dievo buvimas nesuderinamas su gamtos egzistavimu.

Sosinskis A. B.

Gödelio teorema kartu su reliatyvumo, kvantinės mechanikos ir DNR atradimais paprastai laikoma didžiausiu XX amžiaus mokslo laimėjimu. Kodėl? Kokia jo esmė? Kokia jo reikšmė? Šiuos klausimus savo paskaitoje pagal projektą „Viešos paskaitos „Polit.ru““ sprendžia Aleksejus Bronislavovičius Sosinskis, matematikas, Nepriklausomo Maskvos universiteto profesorius, Prancūzijos Respublikos akademinių palmių ordino karininkas, premijos laureatas. Rusijos vyriausybės premija švietimo srityje 2012 m. Visų pirma, buvo pateiktos kelios skirtingos jo formuluotės, aprašyti trys jo įrodinėjimo būdai (pats Kolmogorovas, Chaitinas ir Gödelis), paaiškinta jo reikšmė matematikai, fizikai, informatikai ir filosofijai.

Uspenskis V.A.

Paskaita skirta Gödelio neužbaigtumo teoremos sintaksinei versijai. Pats Gödelis įrodė sintaksinę versiją remdamasis stipresne prielaida nei nuoseklumas, ty vadinamąja omega konsistencija.

Uspenskis V.A.

Paskaitos vasaros mokykloje „Modernioji matematika“, Dubna.

Gödelio neužbaigtumo teoremos

Gödelio neužbaigtumo teoremos

Gödelio neužbaigtumo teoremos- dvi matematinės logikos teoremos apie esminius formaliosios aritmetikos ir, kaip pasekmė, bet kurios pakankamai stiprios pirmos eilės teorijos apribojimus.

Pirmoji teorema teigia, kad jei formali aritmetika yra nuosekli, tai joje yra neredukuojama ir nepaneigiama formulė.

Antroji teorema teigia, kad jei formali aritmetika yra nuosekli, tai joje yra tam tikra formulė, prasmingai tvirtinanti šios teorijos nuoseklumą.

Pirmoji Gödelio neužbaigtumo teorema

Pirmosios Gödelio neužbaigtumo teoremos teiginį galima teigti taip:

Įrodinėdamas teoremą Gödelis sukonstravo formulę G aiškiai, kartais ji vadinama Gödelio neapsprendžiama formule. Standartiniu aiškinimu sakinys G teigia savo neredukuojamumą S. Todėl pagal Gödelio teoremą, jei teorija S yra nuosekli, tai ši formulė iš tikrųjų yra neredukuojama S ir todėl teisinga standartinėje interpretacijoje. Taigi natūraliųjų skaičių formulė G yra tiesa, bet ne išvestinė S.

Gödelio įrodymas gali būti atliktas bet kuriai teorijai, gautai iš S, pridedant naujas aksiomas, pavyzdžiui, formulę G kaip aksioma. Todėl bet kokia nuosekli teorija, kuri yra formaliosios aritmetikos išplėtimas, bus neišsami.

Norėdamas įrodyti pirmąją neužbaigtumo teoremą, Gödelis kiekvienam simboliui, išraiškai ir išraiškų sekai formaliojoje aritmetikoje priskyrė konkretų skaičių. Kadangi formulės ir teoremos yra aritmetikos sakiniai, o formalieji teoremų dariniai – formulių sekos, apie teoremas ir įrodymus atsirado galimybė kalbėti natūraliųjų skaičių požiūriu. Pavyzdžiui, tegul Gödelio neapsprendžiama formulė G turi numerį m, tada jis atitinka tokį teiginį aritmetikos kalba: „tokio natūraliojo skaičiaus nėra n, Ką n yra formulės išvesties numeris su skaičiumi m". Toks formulių ir natūraliųjų skaičių palyginimas vadinamas matematikos aritmetizavimu ir pirmą kartą jį atliko Gödelis. Vėliau ši idėja tapo raktu sprendžiant daugelį svarbių matematinės logikos problemų.

Įrodinėjimo eskizas

Pataisykime kokią nors formalią PM sistemą, kurioje būtų galima pavaizduoti elementarias matematines sąvokas.

Formalios sistemos išraiškos, žiūrint iš išorės, yra baigtinės primityvių simbolių sekos (kintamieji, loginės konstantos ir skliaustai arba taškai), ir nesunku griežtai nurodyti, kurios primityvių simbolių sekos yra formulės, o kurios ne. Panašiai, formaliuoju požiūriu, įrodymai yra ne kas kita, kaip baigtinės formulių sekos (su griežtai apibrėžtomis savybėmis). Matematikos požiūriu nesvarbu, kokius objektus laikome primityviais simboliais, ir nusprendžiame šiems tikslams naudoti natūraliuosius skaičius. Atitinkamai formulė yra baigtinė natūraliųjų skaičių seka, formulės išvada – baigtinė natūraliųjų skaičių baigtinių sekų seka. Taigi matematinės sąvokos (teiginiai) tampa sąvokomis (teiginiais) apie natūraliuosius skaičius ar jų sekas, todėl pačios gali būti išreikštos PM sistemos simbolika (bent iš dalies). Visų pirma galima parodyti, kad sąvokos „formulė“, „išvestinė“, „išvestinė formulė“ yra apibrėžiamos PM sistemoje, tai yra, galima atkurti, pavyzdžiui, formulę. F(v) PM su vienu laisvu kintamuoju v(kurios tipas yra skaičių seka), kad F(v), intuityviu aiškinimu reiškia: v- išvestinė formulė. Dabar sukurkime neapsprendžiamą PM sistemos sakinį, tai yra sakinį A, kuriam nei A, nei ne A neišvestiniai, kaip nurodyta toliau:

Formulė PM su tiksliai vienu laisvu kintamuoju, kurio tipas yra natūralusis skaičius (klasių klasė), bus vadinama išraiškos klase. Sudėkime klasių išraiškas į seką kokiu nors būdu, pažymėkite n-e per R(n), ir atkreipkite dėmesį, kad sąvoka „klasės išraiška“, taip pat tvarkos santykis R galima nustatyti PM sistemoje. Tegu α yra savavališka klasės išraiška; per [α; n] žymi formulę, kuri susidaro iš klasės išraiškos α pakeičiant laisvąjį kintamąjį natūraliojo skaičiaus simboliu n. Trišalis ryšys x = [y;z] taip pat pasirodo esąs apibrėžtas PM. Dabar mes nustatysime klasę K natūraliuosius skaičius taip:

(kur Bew x reiškia: x- išvestinė formulė). Kadangi visos šiame apibrėžime esančios sąvokos gali būti išreikštos PM, tas pats pasakytina ir apie sąvoką K, kuri yra sukonstruota iš jų, tai yra, yra tokia išraiškos klasė S, kad formulė [ S;n], intuityviai interpretuojama, reiškia, kad natūralusis skaičius n priklauso K. Kaip išraiškos klasė, S identiški kai kuriems specifiniams R(q) mūsų numeracijoje, tai yra

galioja tam tikram natūraliam skaičiui q. Dabar parodysime, kad sakinys [ R(q);q] neapsisprendžiama PM. Taigi, jei sakinys [ R(q);q] yra laikomas išvestiniu, tada paaiškėja, kad tai tiesa, tai yra pagal tai, kas buvo pasakyta aukščiau, q priklausys K, tai yra pagal (*), ¬Bew[ R(q);q] bus įvykdytas, o tai prieštarauja mūsų prielaidai. Kita vertus, jei neigimas [ R(q);q] buvo galima daryti išvadą, tada ¬ n ∈ K, tai yra, Bew[ R(q);q] bus tiesa. Vadinasi, [ R(q);q] kartu su jo neigimu bus išskaitomas, o tai vėlgi neįmanoma.

Polinominė forma

Antroji Gödelio neužbaigtumo teorema

Formaliojoje aritmetinėje S galima sukonstruoti formulę, kuri pagal standartinį aiškinimą yra teisinga tada ir tik tada, kai teorija S yra nuosekli. Šiai formulei antrosios Gödelio teoremos teiginys yra teisingas:

Kitaip tariant, formaliosios aritmetikos nuoseklumas negali būti įrodytas naudojant šią teoriją. Tačiau yra formaliosios aritmetikos nuoseklumo įrodymų, naudojant joje neišreiškiamas priemones.

Įrodinėjimo eskizas

Pirmiausia sukuriama formulė Con, kuris prasmingai išreiškia negalėjimą išvesti kokios nors formulės teorijoje S kartu su jos neigimu. Tada pirmosios Gödelio teoremos teiginys išreiškiamas formule Con ⊃ G, Kur G- Neišsprendžiama Gödelio formulė. Visi samprotavimai, įrodantys pirmąją teoremą, gali būti išreikšti ir atlikti naudojant S priemones, tai yra, formulė yra išskaitoma iš S Con ⊃ G. Vadinasi, jei S yra išvedamas Con, tada jis yra išskaičiuojamas ir G. Tačiau pagal pirmąją Gödelio teoremą, jei S yra nuoseklus, tada G joje nėra išskaitoma. Vadinasi, jei S yra nuoseklus, tada joje esanti formulė taip pat yra neredukuojama Con.

Pastabos

Taip pat žr

Nuorodos

• V. A. Uspenskis Gödelio neužbaigtumo teorema. - M.: Nauka, 1982. - 110 p. - (Populiarios matematikos paskaitos).
• Akademikas Yu L. Ershovas „Įrodymas matematikoje“, A. Gordon programa, 2003 m. birželio 16 d
• A. B. Sosinskis Gödelio teorema // Vasaros mokykla „Šiuolaikinė matematika“. - Dubna: 2006 m.
• P. J. Cohenas Apie aibių teorijos pagrindus // Matematikos mokslų pažanga. - 1974. - T. 29. - Nr.5(179). - 169–176 p.
• M. Kordonskis Tiesos pabaiga. - ISBN 5-946448-001-04
• V. A. Uspenskis Gödelio teorema apie neužbaigtumą ir keturi į ją vedantys keliai // Vasaros mokykla „Šiuolaikinė matematika“. - Dubna: 2007 m.
• Zenkinas A.A. Laiko padalijimo principas ir vienos klasės kvazibaigtinių tikėtinų samprotavimų analizė (naudojant G. Kantoro neskaičiuojamumo teoremos pavyzdį) // DAN. - 1997. - T. 356. - Nr. 6. - P. 733-735.
• Čechulinas V. L. Apie trumpą Gödelio teoremų įrodymo versiją // „Pagrindinės matematikos ir informacijos mokslų problemos“, XXXIV Tolimųjų Rytų matematikos mokyklos-seminaro medžiaga, pavadinta akademiko E.V. Zolotova. - Chabarovskas, Rusija: 2009. - P. 60-61.

Wikimedia fondas.

2010 m.

Pažiūrėkite, kas yra „Gödelio teoremos apie neužbaigtumą“ kituose žodynuose:

Šis terminas turi kitas reikšmes, žr. Gödelio teoremą. Gödelio teorema apie neužbaigtumą ir antroji Gödelio teorema [1] dvi matematinės logikos teoremos apie esminius formaliosios aritmetikos apribojimus ir dėl to bet kokius ... ... Vikipedija

Gödelio neužbaigtumo teoremos yra dvi matematinės logikos teoremos apie tam tikros rūšies formalių sistemų neužbaigtumą. Turinys 1 Pirmoji Gėdelio neužbaigtumo teorema 2 Antroji Gėdelio neužbaigtumo teorema ... Vikipedija

Šis terminas turi kitas reikšmes, žr. Gödelio teoremą. Gödelio teorema apie predikatinio skaičiavimo išsamumą yra viena iš pagrindinių matematinės logikos teoremų: ji nustato nedviprasmišką ryšį tarp loginės tiesos... ... Vikipedija Bendras dviejų K. Gödelio nustatytų teoremų pavadinimas. Pirmiausia G. t. teigia, kad bet kurioje nuoseklioje formalioje sistemoje, kurioje yra aritmetikos minimumas (ženklai ir įprastos jų tvarkymo taisyklės), yra formaliai neapsprendžiamas... ...

Uspenskis V.A.

Matematinė enciklopedija

Gödelio neužbaigtumo teorema.1994 m.

Teorinis kompiuterių mokslas 130, 1994, p.273-238.

Galbūt Gödelio neužbaigtumo teorema yra tikrai unikali. Jis unikalus tuo, kad į jį kalbama, kai norima įrodyti „viską pasaulyje“ – nuo ​​dievų buvimo iki intelekto nebuvimo. Mane visada domino labiau „pirminis klausimas“ – kuris iš besikreipiančiųjų į nepilnumo teoremą galėtų ją ne tik suformuluoti, bet ir įrodyti? Skelbiu šį straipsnį dėl to, kad jame išdėstyta visiškai prieinama Gödelio teoremos formuluotė. Rekomenduoju pirmiausia perskaityti Tullio Regge'o Kurto Gödelio straipsnį ir jo garsiąją teoremą

tiesioginė Tarskio derinant gauto rezultato pasekmė

Gödelio neapsprendžiamumo teorema su savo paties tiesos teorija, pasak

kuriems negali būti universalaus tiesos kriterijaus net santykinai

siaura skaičių teorijos sritis, taigi ir bet kuriam jį naudojančiam mokslui

aritmetika. Natūralu, kad šis rezultatas a fortiori taikomas tiesos sampratai

bet kurioje ne matematinėje žinių srityje, kurioje ji yra plačiai paplitusi

naudojama aritmetika.

Karlas Poperis

Uspenskis Vladimiras Andrejevičius gimė 1930 m. lapkričio 27 d. Maskvoje. Baigė Maskvos valstybinio universiteto Mechanikos ir matematikos fakultetą (1952). Fizinių ir matematikos mokslų daktaras (1964). Profesorius, Mechanikos-matematikos fakulteto Matematinės logikos ir algoritmų teorijos katedros vedėjas (1966). Skaito paskaitų kursus „Įvadas į matematinę logiką“, „Skaičiuojamosios funkcijos“, „Gedelio teorema apie išsamumą“. Parengė 25 kandidatus ir 2 mokslų daktarus

1. Problemos pareiškimas

Neužbaigtumo teorema, kurios tikslią formuluotę pateiksime šio skyriaus pabaigoje, o gal ir vėliau (jei skaitytoją tai domina) ir įrodymą, teigia maždaug taip: tam tikromis sąlygomis bet kurioje kalboje yra teisingi, bet neįrodomi teiginiai.

Kai taip formuluojame teoremą, beveik kiekvienas žodis reikalauja paaiškinimo. Todėl pradėsime paaiškindami žodžių, kuriuos vartojame šioje formuluotėje, reikšmę.

Mes nepateiksime bendriausio įmanomo kalbos apibrėžimo, apsiribodami tomis kalbos sąvokomis, kurių mums prireiks vėliau. Yra dvi tokios sąvokos: „kalbos abėcėlė“ ir „tikrų kalbos teiginių rinkinys“.

1.1.1. Abėcėlė

Pagal abėcėlę turime omenyje baigtinį elementariųjų ženklų rinkinį (tai yra dalykų, kurių negalima suskirstyti į sudedamąsias dalis). Šie ženklai vadinami abėcėlės raidėmis. Abėcėlės žodžiu turime omenyje baigtinę raidžių seką. Pavyzdžiui, įprasti žodžiai anglų kalba (įskaitant tinkamus vardus) yra 54 raidžių abėcėlės žodžiai (26 mažosios raidės, 26 didžiosios raidės, brūkšnys ir apostrofas). Kitas pavyzdys – natūralūs skaičiai dešimtainėje raidėje yra 10 raidžių abėcėlės žodžiai, kurių raidės yra ženklai: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Abėcėlėms žymėti naudosime paprastosios didžiosios raidės. Jei L yra abėcėlė, tai L? žymės visų abėcėlės žodžių aibę L – žodžiai, sudaryti iš jos raidžių. Darysime prielaidą, kad bet kuri kalba turi savo abėcėlę, todėl visi šios kalbos posakiai (ty įvairių objektų pavadinimai, teiginiai apie šiuos objektus ir pan.) yra šios abėcėlės žodžiai. Pavyzdžiui, bet koks sakinys anglų kalba, taip pat bet koks tekstas, parašytas anglų kalba, gali būti laikomas žodžiu išplėstinėje 54 raidžių abėcėlėje, kurioje taip pat yra skyrybos ženklai, tarpo tarpas, raudonos linijos ženklas ir galbūt kai kurie kiti naudingi simboliai. . Darant prielaidą, kad kalbos posakiai yra tam tikros abėcėlės žodžiai, mes neįtraukiame dėmesio į „daugiasluoksnes“ išraiškas, tokias kaip ???f(x)dx. Tačiau šis apribojimas nėra per daug reikšmingas, nes bet kuri tokia išraiška, naudojant tinkamus susitarimus, gali būti „ištempta“ į linijinę formą. Bet koks rinkinys M yra L? vadinamas abėcėlės L žodžių aibe. Jei tiesiog sakome, kad M yra žodžių aibė, tai reiškia, kad tai yra kokios nors abėcėlės žodis. Dabar aukščiau pateiktą prielaidą apie kalbą galima perfrazuoti taip: bet kurioje kalboje bet koks posakių rinkinys yra žodžių rinkinys.

1.1.2. Daug teisingų teiginių

Darome prielaidą, kad mums duota aibės L poaibis T? (kur L yra tam tikros mūsų svarstomos kalbos abėcėlė), kuri vadinama „tikrųjų teiginių“ (arba tiesiog „tiesų“) rinkiniu. Pereidami tiesiai į poaibį T, praleidžiame šiuos tarpinius samprotavimo žingsnius: pirma, kurie abėcėlės L žodžiai yra teisingai suformuoti kalbos posakiai, tai yra, turintys tam tikrą reikšmę mūsų šios kalbos interpretacijoje (pvz., 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 yra gerai suformuotos išraiškos, o tokios išraiškos kaip +=x nėra); antra, kokios išraiškos yra formulės, t.y. gali priklausyti nuo parametro (pavyzdžiui, x=3, x=y, 2=3, 2=2); trečia, kurios iš formulių yra uždarosios formulės, t.y. teiginiai, kurie nepriklauso nuo parametrų (pvz., 2=3, 2=2); ir galiausiai, kurios uždarosios formulės yra teisingi teiginiai (pavyzdžiui, 2=2).

1.1.3. Pagrindinė kalbų pora

1.2. "Neįrodoma"

„Neįrodoma“ reiškia be įrodymų.

1.3. Įrodymas

Nors terminas „įrodymas“ yra bene vienas svarbiausių matematikoje (savo knygą „Matematikos pagrindai“ burbakiai pradeda žodžiais: „Nuo senovės graikų laikų sakyti „matematika“ reiškia tą patį, kaip pasakyti „įrodymas“), jis neturi savo tikslaus apibrėžimo. Apskritai įrodymo sąvoka su visomis semantinėmis šakomis labiau priklauso psichologijos, o ne matematikos sričiai. Bet kad ir kaip būtų, įrodymas yra tiesiog argumentas, kurį mes patys laikome gana įtikinamu, kad įtikintume visus kitus.

Užrašytas įrodymas tampa tam tikros abėcėlės P žodžiu, kaip ir bet koks angliškas tekstas yra L abėcėlės žodis, kurio pavyzdys buvo pateiktas aukščiau. Visų įrodymų aibė sudaro aibės P? poaibį (ir gana platų poaibį). Mes nebandysime tiksliai apibrėžti šios vienu metu „naivios“ ir „absoliučios“ įrodymo sąvokos arba – kas yra lygiavertė – pateikti atitinkamo P? poaibio apibrėžimą. Vietoje to apsvarstysime formalų šios neaiškios sąvokos analogą, kuriam ateityje vis tiek vartosime terminą „įrodymas“. Šis analogas turi dvi labai svarbias ypatybes, kurios išskiria jį nuo intuityvios koncepcijos (nors intuityvi įrodinėjimo idėja vis dar tam tikru mastu atspindi šias savybes). Pirmiausia pripažinsime, kad egzistuoja skirtingos įrodymų sąvokos, t. . Toliau reikalausime, kad kiekvienai tokiai įrodymo sąvokai egzistuotų veiksmingas metodas, kitaip tariant, algoritmas, kuris būtinai nustatytų, ar duotas P abėcėlės žodis yra įrodymas, ar ne. Taip pat manysime, kad yra algoritmas, kuris visada gali nustatyti, kurį teiginį įrodo pateiktas įrodymas. (Daugeliu atvejų įrodomas teiginys yra tiesiog paskutinis teiginys veiksmų sekoje, kuri sudaro įrodymą.)

Taigi galutinis mūsų apibrėžimas yra toks:

(1) Turime abėcėlę L (kalbos abėcėlė) ir abėcėlę P (įrodomąją abėcėlę).

(2) Mums duota aibė P, kuri yra P? poaibis ir kurios elementai vadinami „įrodymais“. Ateityje manysime, kad turime ir algoritmą, leidžiantį nustatyti, ar savavališkas abėcėlės P žodis yra aibės P elementas, tai yra įrodymas, ar ne.

(3) Ar mes taip pat turime funkciją? (norėdami sužinoti, kas tiksliai buvo įrodyta), kieno tai yra? atitinka sąlygą P???P?, o kurio reikšmių diapazonas yra P?. Darome prielaidą, kad turime algoritmą, kuris apskaičiuoja šią funkciją (tiksli žodžių „algoritmas apskaičiuoja funkciją“ reikšmė yra tokia: funkcijos reikšmės gaunamos naudojant šį algoritmą – specialių transformacijos taisyklių rinkinį). Sakysime, kad elementas p? P yra abėcėlės L žodžio?(p) įrodymas.

Trigubai tenkinančios sąlygos (1)-(3) vadinamos dedukcine sistema per abėcėlę L.

Skaitytojui, susipažinusiam su įprastu „įrodymų“ apibrėžimo būdu „aksioma“ ir „išvados taisyklėmis“, dabar paaiškinsime, kaip šį metodą galima laikyti ypatingu 1.3.2 skirsnyje pateikto apibrėžimo atveju. Tai yra, įrodymas paprastai apibrėžiamas kaip tokių kalbos posakių seka, kurių kiekviena yra arba aksioma, arba anksčiau gauta iš jau esamų teiginių, naudojant vieną iš išvados taisyklių. Jei į mūsų kalbos abėcėlę įtrauksime naują žodį *, tai tokį įrodymą galime parašyti žodžio forma, sudaryta naudojant gautą abėcėlės modifikaciją: posakių seka tampa žodžiu C1*C2*...*Cn . Šiuo atveju funkcija, kuri nustato, kas tiksliai buvo įrodyta, turi reikšmę šio žodžio dalyje, iškart po paskutinės sekos raidės *. Algoritmas, kurio egzistavimo reikalaujama 1.3.2 dalyje. apibrėžimą galima lengvai sudaryti, kai tiksliai apibrėžiame bet kurią iš priimtų žodžių „aksioma“ ir „išvados taisyklės“ reikšmių.

1.4 Bandoma tiksliai suformuluoti neužbaigtumo teoremą

1.4.1. Pirmas bandymas

„Esant tam tikroms sąlygoms, kai kalbama apie pagrindinę abėcėlės kalbos porą L ir dedukcinę sistemą virš L, visada yra žodis T, kuris neturi jokio įrodymo. Ši parinktis vis dar atrodo neaiški. Visų pirma, galėtume lengvai sugalvoti tiek dedukcinių sistemų, kiek norime, ir kuriose būtų labai mažai įrodomų žodžių. Pavyzdžiui, tuščioje dedukcinėje sistemoje (kur P =?) iš viso nėra žodžių, turinčių įrodymų.

1.4.2. Antras bandymas

Yra ir kitas, natūralesnis požiūris. Tarkime, kad mums duota kalba – ta prasme, kad mums duota pagrindinė šios kalbos pora. Dabar ieškosime tokios dedukcinės sistemos virš L (intuityviai ieškome įrodinėjimo technikos), kurios pagalba galėtume įrodyti kuo daugiau žodžių iš T, riboje visi žodžiai iš T. Gödelio teoremos apibūdina situacija, kai tokios dedukcinės sistemos (kurios pagalba būtų įrodomas kiekvienas žodis T) nėra. Taigi norėtume suformuluoti tokį teiginį:

„Esant tam tikroms pagrindinės poros sąlygoms, neegzistuoja dedukcinė sistema, kurioje kiekvienas žodis iš T turėtų įrodymą.

Tačiau toks teiginys akivaizdžiai klaidingas, nes tereikia imti dedukcinę sistemą, kurioje P = L, P = P? u?(p) = p visiems p iš P?; tada kiekvienas žodis iš L? yra trivialiai įrodoma. Todėl turime priimti tam tikrus apribojimus, kokias dedukcines sistemas naudojame.

1.5. Nuoseklumas

Būtų visiškai natūralu reikalauti, kad būtų įrodinėjami tik „tikri teiginiai“, tai yra tik žodžiai iš T. Sakysime, kad dedukcinė sistema yra nuosekli pagrindinės poros atžvilgiu if?(P)?T. Visose tolesnėse diskusijose mus domina tik tokios nuoseklios dedukcinės sistemos. Jei mums būtų duota kalba, būtų labai viliojanti rasti nuoseklią dedukcinę sistemą, kurioje kiekvienas teisingas teiginys turėtų įrodymą. Mus dominanti Gödelio teoremos versija tiksliai teigia, kad esant tam tikroms pagrindinės poros sąlygoms, tokios dedukcinės sistemos rasti neįmanoma.

1.6. Išbaigtumas

Sakoma, kad dedukcinė sistema yra baigta pagrindinės poros atžvilgiu, jei?(P)?T. Tada mūsų neužbaigtumo teoremos formuluotė įgauna tokią formą:

Esant tam tikroms pagrindinės poros sąlygoms, nėra dedukcinės sistemos virš L, kuri būtų išsami ir santykinai nuosekli.