Gödelova druga teorema. Zanimljive činjenice i korisni savjeti

Gedelov teorem o nepotpunosti

Uspensky V.A.

Možda je Gedelov teorem o nepotpunosti zaista jedinstven. Jedinstven je po tome što se na njega poziva kada žele da dokažu „sve na svetu“ – od prisustva bogova do odsustva inteligencije. Oduvijek me zanimalo „primarnije pitanje“ – ko bi od onih koji se pozivaju na teoremu o nepotpunosti mogao ne samo da je formuliše, već i da dokaže? Ovaj članak objavljujem iz razloga što iznosi potpuno pristupačnu formulaciju Gödelove teoreme. Preporučujem da prvo pročitate članak Tullija Reggea Kurta Gödela i njegovu čuvenu teoremu

Zaključak o nemogućnosti univerzalnog kriterija istine direktna je posljedica rezultata koji je Tarski dobio kombinacijom Gödelove teoreme o neodlučivosti s vlastitom teorijom istine, prema kojoj ne može postojati univerzalni kriterij istine čak ni za relativno uske polje teorije brojeva, a samim tim i za svaku nauku koja koristi aritmetiku. Naravno, ovaj rezultat se a fortiori primjenjuje na koncept istine u bilo kojoj nematematičkoj oblasti znanja u kojoj se aritmetika široko koristi.

Karl Popper

Uspenski Vladimir Andrejevič rođen je 27. novembra 1930. godine u Moskvi. Diplomirao na Mehaničko-matematičkom fakultetu Moskovskog državnog univerziteta (1952). Doktor fizičko-matematičkih nauka (1964). Profesor, šef Katedre za matematičku logiku i teoriju algoritama, Mehanički i matematički fakultet (1966). Drži kolegije predavanja "Uvod u matematičku logiku", "Izračunljive funkcije", "Gödelov teorem o potpunosti". Pripremio 25 kandidata i 2 doktora nauka

1. Izjava o problemu

Teorema o nepotpunosti, čiju ćemo tačnu formulaciju dati na kraju ovog poglavlja, a možda i kasnije (ako čitaoca to zanima) i dokaz, otprilike iznosi sljedeće: pod određenim uvjetima u bilo kojem jeziku postoje istiniti ali nedokazive izjave.

Kada formulišemo teoremu na ovaj način, gotovo svaka riječ zahtijeva neko objašnjenje. Stoga ćemo početi objašnjavanjem značenja riječi koje koristimo u ovoj formulaciji.

1.1. Jezik

Nećemo davati najopštiju moguću definiciju jezika, radije ćemo se ograničiti na one jezičke koncepte koji će nam kasnije biti potrebni. Postoje dva takva koncepta: “abeceda jezika” i “skup istinitih iskaza jezika”.

1.1.1. Abeceda

Pod abecedom podrazumijevamo konačan skup elementarnih znakova (tj. stvari koje se ne mogu rastaviti na sastavne dijelove). Ovi znakovi se nazivaju slovima abecede. Pod riječju abecede podrazumijevamo konačan niz slova. Na primjer, obične riječi na engleskom (uključujući vlastita imena) su riječi abecede od 54 slova (26 malih slova, 26 velikih slova, crtica i apostrof). Drugi primjer je da su prirodni brojevi u decimalnom zapisu riječi abecede od 10 slova, čija su slova znakovi: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Za označavanje alfabeta koristit ćemo običnim velikim slovima. Ako je L abeceda, onda je L? će označavati skup svih riječi abecede L - riječi nastale od njegovih slova. Pretpostavićemo da svaki jezik ima svoje pismo, tako da su svi izrazi ovog jezika (tj. - nazivi raznih objekata, iskazi u vezi sa tim objektima itd.) reči ovog pisma. Na primjer, bilo koja ponuda na engleskom, kao i svaki tekst napisan na engleskom jeziku, može se smatrati riječju proširene abecede od 54 slova, koja uključuje i znakove interpunkcije, razmak među riječima, znak crvene linije i, eventualno, neke druge korisne znakove. Uz pretpostavku da su izrazi jezika riječi nekog alfabeta, mi stoga iz razmatranja isključujemo „višeslojne“ izraze poput ???f(x)dx. Međutim, ovo ograničenje nije previše značajno, budući da se svaki takav izraz, koristeći prikladne konvencije, može "rastegnuti" u linearni oblik. Bilo koji skup M sadržan u L? naziva se skup riječi abecede L. Ako jednostavno kažemo da je M skup riječi, onda mislimo da je riječ neke abecede. Sada se gornja pretpostavka o jeziku može preformulisati na sljedeći način: u bilo kojem jeziku, bilo koji skup izraza je skup riječi.

1.1.2. Mnogo istinitih izjava

Pretpostavljamo da nam je dat podskup T skupa L? (gdje je L abeceda nekog jezika koji razmatramo), koji se naziva skup "tačnih iskaza" (ili jednostavno "istina"). Prelazeći direktno na podskup T, izostavljamo sljedeće međukorake rasuđivanja: prvo, koje riječi abecede L su ispravno formirani izrazi jezika, odnosno imaju određeno značenje u našoj interpretaciji ovog jezika (na primjer, 2 + 3, x + 3, x=y, x=3, 2=3, 2=2 su dobro oblikovani izrazi, dok izrazi poput +=x nisu); drugo, koji izrazi su formule, tj. može zavisiti od parametra (na primjer, x=3, x=y, 2=3, 2=2); treće, koje od formula su zatvorene formule, tj. izjave koje ne zavise od parametara (na primjer, 2=3, 2=2); i konačno, koje su zatvorene formule istinite izjave (na primjer, 2=2).

1.1.3. Osnovni jezički par

1.2. "Nedokazivo"

"Nedokazivo" znači bez dokaza.

1.3. Dokaz

Iako je termin "dokaz" možda jedan od najvažnijih u matematici (Bourbakijevi počinju svoju knjigu "Osnove matematike" riječima: "Još od vremena starih Grka, reći 'matematika' znači isto što i recimo 'dokaz'"), nema svoju tačnu definiciju. Općenito, pojam dokaza sa svim svojim semantičkim granama prije pripada polju psihologije nego matematike. Ali kako god bilo, dokaz je jednostavno argument koji i mi sami smatramo prilično uvjerljivim da bismo uvjerili sve ostale.

Jednom zapisan, dokaz postaje riječ u nekoj abecedi P, kao i svaka engleski tekst je riječ abecede L, čiji je primjer dat gore. Skup svih dokaza čini podskup (i prilično opsežan podskup) skupa P?. Nećemo pokušavati da damo preciznu definiciju ovog istovremeno “naivnog” i “apsolutnog” koncepta dokaza, ili – što je ekvivalentno – da damo definiciju odgovarajućeg podskupa P?. Umjesto toga, razmotrit ćemo formalni analog ovog nejasnog koncepta, za koji ćemo u budućnosti i dalje koristiti termin „dokaz“. Ovaj analog ima dvije vrlo važne karakteristike koje ga razlikuju od intuitivnog koncepta (iako intuitivna ideja dokaza još uvijek u određenoj mjeri odražava ove karakteristike). Prije svega, priznat ćemo da postoje različiti koncepti dokaza, odnosno da su različiti podskupovi dokaza u P prihvatljivi, pa čak i više od toga: mi ćemo, zapravo, priznati da se sama abeceda dokaza P može mijenjati? . Dalje ćemo zahtijevati da za svaki takav koncept dokaza postoji efikasna metoda, drugim riječima, algoritam, koji bi nužno odredio da li je data riječ abecede P dokaz ili ne. Također ćemo pretpostaviti da postoji algoritam koji uvijek može odrediti koji iskaz dokazuje dati dokaz. (U mnogim situacijama, tvrdnja koja se dokazuje jednostavno je posljednja izjava u nizu koraka koji čini dokaz.)

Dakle, naša konačna definicija je sljedeća:

(1) Imamo alfabet L (jezičko pismo) i pismo P (dokazno pismo).

(2) Dat nam je skup P, koji je podskup od P?, i čiji se elementi nazivaju “dokazi”. U budućnosti ćemo pretpostaviti da imamo i algoritam koji nam omogućava da odredimo da li je proizvoljna riječ abecede P element skupa P, odnosno dokaz ili ne.

(3) Da li također imamo funkciju? (da se pronađe šta je tačno dokazano), čiji je domen definicije? zadovoljava uslov P???P?, a čiji je raspon vrijednosti u P?. Pretpostavljamo da imamo algoritam koji izračunava ovu funkciju ( tačna vrijednost Riječi "algoritam izračunava funkciju" su sljedeće: vrijednosti funkcije se dobivaju pomoću ovog algoritma - skupa posebnih pravila transformacije). Reći ćemo da je element p? P je dokaz riječi?(p) abecede L.

Trojka<Р, Р, ?>, koji zadovoljava uslove (1)-(3) naziva se deduktivni sistem nad abecedom L.

Za čitaoca koji je upoznat sa uobičajenim načinom definisanja "dokaza" u terminima "aksioma" i "pravila zaključivanja", sada ćemo objasniti kako se ovaj metod može smatrati posebnim slučajem definicije date u odeljku 1.3.2. Odnosno, dokaz se obično definira kao niz takvih jezičkih izraza, od kojih je svaki ili aksiom ili prethodno dobiven iz već postojećih iskaza korištenjem jednog od pravila zaključivanja. Ako u abecedu našeg jezika dodamo novu riječ *, onda možemo napisati takav dokaz u obliku riječi sastavljene korištenjem rezultirajuće modifikacije abecede: niz izraza postaje riječ C1*C2*...*Cn . U ovom slučaju, funkcija koja određuje šta je tačno dokazano ima svoje značenje u dijelu ove riječi odmah iza posljednjeg slova * u nizu. Algoritam čije se postojanje zahtijeva u dijelu 1.3.2. definicija, može se lako konstruisati nakon što smo precizno definisali bilo koje od prihvaćenih značenja reči "aksiom" i "pravila zaključivanja".

1.4 Pokušaji da se precizno formuliše teorema o nepotpunosti

1.4.1. Prvi pokušaj

„Pod određenim uslovima za osnovni par alfabetskog jezika L i deduktivnog sistema<Р, Р, ?>preko L - uvijek postoji riječ u T koja nema dokaza." Ova opcija još uvijek izgleda nejasno. Konkretno, lako bismo mogli doći do bilo kojeg broja deduktivnih sistema koji imaju vrlo malo riječi koje se mogu dokazati. Na primjer, u praznoj dedukciji sistem (gde je P = ?) uopšte ne postoje reči koje imaju dokaz.

1.4.2. Drugi pokušaj

Postoji još jedan, prirodniji pristup. Pretpostavimo da nam je dat jezik - u smislu da nam je dat osnovni par ovog jezika. Sada ćemo tražiti deduktivni sistem preko L (intuitivno, tražimo tehniku ​​dokaza) uz pomoć koje bismo mogli dokazati što je više moguće više riječi iz T, u granicama sve riječi iz T. Gödelove teoreme opisuju situaciju u kojoj takav deduktivni sistem (preko kojeg bi svaka riječ u T bila dokaziva) ne postoji. Stoga bismo željeli formulirati sljedeću izjavu:

"Pod određenim uslovima u vezi sa osnovnim parom, ne postoji deduktivni sistem u kojem svaka reč iz T ima dokaz."

Međutim, takva izjava je očigledno netačna, jer je potrebno uzeti samo deduktivni sistem u kojem je P = L, P = P? u?(p) = p za sve p iz P?; onda svaka riječ iz L? je trivijalno dokazivo. Stoga, moramo prihvatiti određena ograničenja u pogledu deduktivnih sistema koje koristimo.

1.5. Dosljednost

Bilo bi sasvim prirodno zahtijevati da se dokazuju samo “tačni iskazi”, odnosno samo riječi iz T. Reći ćemo da je deduktivni sistem<Р, Р, ?>je konzistentan u odnosu na osnovni par ako?(P)?T. U svim narednim raspravama će nas zanimati samo takvi konzistentni deduktivni sistemi. Ako nam je dat jezik, onda bi bilo izuzetno primamljivo pronaći konzistentan deduktivni sistem u kojem bi svaka istinita izjava imala dokaz. Verzija Gedelove teoreme koja nas zanima upravo kaže da je pod određenim uslovima u vezi sa osnovnim parom nemoguće pronaći takav deduktivni sistem.

1.6. Kompletnost

Kaže se da je deduktivni sistem<Р,Р,?>je kompletan u odnosu na osnovni par, pod uslovom da?(P)?T. Tada naša formulacija teoreme o nepotpunosti poprima sljedeći oblik:

Pod određenim uslovima u vezi sa osnovnim parom, takav deduktivni sistem ne postoji<Р,Р,?>preko L, što bi bilo i potpuno i relativno konzistentno.

Bibliografija

Za pripremu ovog rada korišteni su materijali sa stranice http://filosof.historic.ru

Priznajem da sam samu ideju o razmatranju pitanja postojanja Boga s ove strane pročitao od Anatolija Aleksandroviča Vasermana:
http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D1%82%D0%BE%D0%BB%D0%B8%D0%B9_%D0%90%D0 %BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87_%D0%92 %D0%B0%D1%81%D1%81%D0%B5%D1%80%D0%BC%D0%B0%D0%BD#.D0.A0.D0.B5.D0.BB.D0.B8. D0.B3.D0.B8.D0.BE.D0.B7.D0.BD.D1.8B.D0.B5_.D0.B2.D0.B7.D0.B3.D0.BB.D1.8F.D0. B4.D1.8B

Ali želio bih da razvijem ovu ideju i opišem je malo detaljnije.
U religiji (kao i u nereligiji) postoji određena aksiomatika konstrukcije. Barem u idealnom slučaju, ako ovo nije samo slijepo vjerovanje, već svjestan i informiran izbor. Na primjer, aksiom fizike se može smatrati „prirodom se može spoznati kroz razum i logičke zaključke, svi zakoni fizike su isti u svim tačkama u prostoru i u bilo koje vrijeme“. Na primjer, aksiomom religije može se smatrati izjava „Bog postoji i prvi je uzrok svih stvari“. Drugim riječima, nema sumnje da se sve brojne pojedinosti i grane mogu svesti na nekoliko važnih, nedokazivih tvrdnji, a to su upravo ti aksiomi.

Razmotrimo sa ovih pozicija vjerskih uvjerenja. Najvažniji aksiom religije: “Bog postoji i prvi je uzrok svih stvari.”
Sada se prisjetimo jedne od najvažnijih matematičkih teorema, Gödelove teoreme.
http://elementy.ru/trefil/21142
Slab Gedelov teorem: "Svaki formalni sistem aksioma sadrži nerazjašnjene pretpostavke" ili "ako je sistem aksioma potpun, onda je nedosledan."
Gedelova jaka teorema: "Logička potpunost (ili nepotpunost) bilo kog sistema aksioma ne može se dokazati u okviru ovog sistema. Da bi se to dokazalo ili opovrglo, potrebni su dodatni aksiomi (jačanje sistema)."

Prisjetimo se nekih definicija. Sistem aksioma je potpun ako je bilo koja izjava formulisana za dati sistem aksioma dokaziva (to jest, tačna je ili netačna). Nerazjašnjena pretpostavka je tvrdnja za koju se ne može dokazati ni njena istinitost ni netačnost, odnosno tvrdnja nije logički dokaziva. Sistem aksioma je kontradiktoran ako se može dokazati da je jedna te ista izjava istinita i netačna.

Iz Gedelove teoreme proizilazi da ako je pojam Boga uključen u aksiomatski sistem, onda ovaj sistem nije potpun, odnosno postoje posljedice (fenomeni) koje nisu dokazive, odnosno mogu postojati, ali i ne moraju postojati. nije dokazivo.
Ali ovo je u suprotnosti sa sljedećim dvjema odredbama (izaberite ono što je najuvjerljivije): priroda ne sadrži fenomene koji se mogu smatrati i postojećim i nepostojećim, bilo koji prirodni fenomen ili postoji ili ne postoji. Druga pozicija kaže da je, po definiciji, Bog osnovni uzrok svega, pa Bog ili vodi do postojanja određenih stvari (izjava) ili do njihovog nepostojanja, pozivajući se na Boga može ili dokazati ili opovrgnuti bilo koju tvrdnju. Ovo je u suprotnosti sa nekompletnošću sistema.

Ili drugo. Ako pojam Boga uključimo u aksiomatski sistem i pretpostavimo da je potpun (svaka tvrdnja u kompletnom sistemu aksioma je dokaziva), onda će prema Gedelovoj teoremi takav sistem aksioma biti kontradiktoran, odnosno postojati će fenomeni. za koje se može dokazati da i postoje i da ne postoje.

Nema smisla uključivati ​​Boga u kontradiktorni sistem aksioma, jer je on kontradiktoran, odnosno sadrži pojave za koje se može dokazati da postoje i da ne postoje, što je, kako je rečeno, u suprotnosti s prirodom i konceptom Boga.

Konačno, ako pojam Boga nije uključen u aksiomatski sistem, onda se ne može smatrati temeljnom osnovom univerzuma, iz koje proizlazi sve što postoji, što je suštinski protivrečno definiciji Boga.

Za valjanost ovog dokaza potrebno je priznati valjanost zakona matematičke logike (propozicijska logika + predikatski račun), koji omogućavaju utvrđivanje zakona posljedice, istine, lažnosti, nedosljednosti, konzistentnosti iskaza i dr. svojstva i relacije između iskaza.

Ako pretpostavimo da matematička logika nije primjenjiva na proučavanje pitanja postojanja Boga, onda će posljedica biti da ovo pitanje nije moguće proučavati uz pomoć rasuđivanja, uz pomoć razuma. Drugim riječima, dosljedan razum uvijek dolazi do negativnog odgovora na pitanje postojanja Boga.

Šta se na kraju desi... svaka čak i iole racionalna osoba, naravno, priznaje valjanost zakona logike, što znači da uvek dolazi do zaključka da Bog u definiciji „uzroka svih stvari“ ne postoji . Neracionalna osoba koja tvrdi da se Boga može spoznati samo kroz osjećaje (a ne razum), naravno, to može reći, ali ne postoji način da se drugi uvjeri u to; Štaviše, pojam Boga je koncept formulisan razumom. Kako se predlaže da se koncept razuma prevede u senzaciju, pa čak i na način da se može prenijeti drugoj osobi, nije jasno. Opet, čak i donekle racionalna osoba će reći da to nije moguće: prevesti apstraktni koncept razuma u osjećaj i osjetiti ga.

Konačno, postoji još jedna opcija: “Bog nije prvi uzrok svega.” Tada takve kontradikcije ne nastaju, međutim, ovo je značajno slabljenje pozicije religije, jer je upravo činjenica da je Bog sve stvorio, da je Bog početak svih početaka, temelj za brojne tvrdnje religije i opravdanja u sporovima.

P.S. Vrijedi napomenuti još jednu zanimljivost, zanimljivu za fizičare. IN ovu definiciju Bog ne govori ništa o svojoj racionalnosti. Odnosno, moglo bi se dodati „Bog je racionalni uzrok svih stvari“, ali ovo je sužavanje definicije, koje u početku nije potrebno za dokaz. Bez inteligencije, koncept „boga“ se lako može zamijeniti „singularnošću i veliki prasak- uzrok svega što postoji." A odgovor će biti isti: singularnost i veliki prasak nisu osnovni uzrok svega što postoji.
Provodeći još veću apstrakciju, možemo reći da niti jedan fenomen ili uzrok ne može biti osnovni uzrok svih stvari, odnosno da osnovni uzrok u principu ne postoji. Rasuđujući u okviru bilo koje aksiomatike, može se doći do zaključka da osnovni uzrok svega ne postoji. Najjednostavnije rečeno, bez obzira na to koliko fundamentalno razumijemo svemir, pitanja će uvijek ostati u duhu: „odakle je došao veliki prasak, odakle je došao singularitet, odakle je došao pulsirajući svemir, odakle je došao iz kojeg dolazi multiverzum, zašto univerzum uvijek postoji?” i tako dalje. Osnovni uzrok svega se u principu ne može naći ni u jednom predmetu, fenomenu ili pojmu. Dakle, za osobu je ovo ekvivalentno njegovom odsustvu. Teoretski, može se pretpostaviti postojanje vanjskog posmatrača izvan našeg svemira, koji će odgovoriti na pitanje odakle je sve došlo (taj isti dodatni aksiom, proširenje u Gedelovoj teoremi), ali tada će se postaviti pitanje gdje je vanjski promatrač, njegov univerzum i korijenski uzrok svega ovoga dolazi iz.

Svaki sistem matematičkih aksioma, počevši od određenog nivoa složenosti, ili je interno kontradiktoran ili nepotpun.

Godine 1900. u Parizu je održana Svjetska konferencija matematičara na kojoj je David Hilbert (1862-1943) u formi teza iznio 23 najvažnija, po njegovom mišljenju, problema koje su teoretičari nadolazećeg dvadesetog vijeka morali riješiti. Broj dva na njegovoj listi bio je jedan od njih jednostavni zadaci, odgovor na koji se čini očiglednim dok ne zadubite malo dublje. Govoreći savremeni jezik, bilo je pitanje: da li je matematika samodovoljna? Hilbertov drugi zadatak se svodio na potrebu da se striktno dokaže da je sistem aksiome- osnovni iskazi uzeti kao osnova u matematici bez dokaza - savršen je i potpun, odnosno omogućava da se sve što postoji matematički opiše. Trebalo je dokazati da je moguće definisati takav sistem aksioma koji će, prvo, biti međusobno konzistentni, a drugo, iz njih se može izvesti zaključak o istinitosti ili neistinitosti bilo koje tvrdnje.

Uzmimo primjer iz školske geometrije. Standard Euklidska planimetrija(ravninska geometrija) može se bezuslovno dokazati da je tvrdnja “zbir uglova trougla 180°” tačna, a tvrdnja “zbir uglova trougla je 137°” netačna. U suštini, u euklidskoj geometriji svaka izjava je ili lažna ili istinita, i ne postoji treća opcija. A početkom dvadesetog veka matematičari su naivno verovali da istu situaciju treba posmatrati u svakom logički doslednom sistemu.

A onda ga je 1931. neki bečki matematičar Kurt Gödel s naočalama uzeo i objavio kratak članak, koji je jednostavno preokrenuo čitav svijet takozvane “matematičke logike”. Nakon dugih i složenih matematičkih i teorijskih preambula, ustanovio je doslovno sljedeće. Uzmimo bilo koju izjavu poput: “Pretpostavka br. 247 u ovom sistemu aksioma je logički nedokaziva” i nazovimo je “tvrdnjom A”. Dakle, Gödel je jednostavno dokazao sljedeće neverovatna nekretnina bilo koji aksiomski sistemi:

“Ako možete dokazati tvrdnju A, onda možete dokazati tvrdnju ne-A.”

Drugim riječima, ako je moguće dokazati valjanost tvrdnje „pretpostavka 247 Ne dokazivo", onda je moguće dokazati valjanost tvrdnje "pretpostavka 247 dokazivo" Odnosno, vraćajući se na formulaciju Hilbertovog drugog problema, ako je sistem aksioma potpun (to jest, bilo koja izjava u njemu se može dokazati), onda je on kontradiktoran.

Jedini izlaz iz ove situacije je prihvatanje nekompletan sistem aksiom. Odnosno, moramo da se pomirimo sa činjenicom da ćemo u kontekstu bilo kog logičkog sistema i dalje imati iskaze tipa A koji su očigledno tačni ili lažni - i možemo samo da sudimo o njihovoj istinitosti vani okvir aksiomatike koju smo usvojili. Ako takvih tvrdnji nema, onda je naša aksiomatika kontradiktorna, au njenom okviru će se neizbježno naći formulacije koje se mogu i dokazati i opovrgnuti.

Dakle, formulacija prvo,or slab Gedelove teoreme o nepotpunosti: “Svaki formalni sistem aksioma sadrži neriješene pretpostavke.” Ali Gödel nije stao na tome, formulirajući i dokazujući sekunda, ili jaka Gedelov teorem o nepotpunosti: „Logička potpunost (ili nepotpunost) bilo kojeg sistema aksioma ne može se dokazati u okviru ovog sistema. Da bi se to dokazalo ili opovrglo, potrebni su dodatni aksiomi (jačanje sistema).“

Bilo bi sigurnije misliti da su Gödelove teoreme apstraktne prirode i da se ne tiču ​​nas, već samo područja uzvišene matematičke logike, ali se u stvari pokazalo da su u direktnoj vezi sa strukturom ljudskog mozga. Engleski matematičar i fizičar Roger Penrose (r. 1931.) pokazao je da se Gedelove teoreme mogu koristiti za dokazivanje postojanja fundamentalnih razlika između ljudskog mozga i kompjutera. Smisao njegovog rezonovanja je jednostavan. Kompjuter djeluje striktno logički i nije u stanju odrediti da li je izjava A istinita ili lažna ako ide dalje od aksiomatike, a takvi iskazi, prema Gödelovom teoremu, neizbježno postoje. Osoba, suočena sa tako logički nedokazivom i nepobitnom tvrdnjom A, uvijek je u stanju da utvrdi njenu istinitost ili neistinitost – na osnovu svakodnevnog iskustva. Barem u ovom pogledu ljudski mozak je superiorniji od kompjutera ograničenog čistim logičkim sklopovima. Ljudski mozak je sposoban da shvati punu dubinu istine sadržane u Gedelovim teoremama, ali kompjuterski mozak nikada ne može. Stoga je ljudski mozak sve samo ne kompjuter. On je sposoban odluke, i Turingov test će proći.

Pitam se da li je Hilbert imao pojma dokle će nas njegova pitanja odvesti?

Kurt Godel, 1906-78

austrijski, zatim američki matematičar. Rođen u Brünnu (sada Brno, Češka). Diplomirao je na Univerzitetu u Beču, gdje je ostao nastavnik na odsjeku za matematiku (od 1930. - profesor). Godine 1931. objavio je teoremu koja je kasnije dobila njegovo ime. Kao čisto apolitična osoba, izuzetno je teško podnio ubistvo svog prijatelja i kolege iz odjeljenja od strane nacističkog studenta i pao je u duboku depresiju čiji su ga recidivi pratili do kraja života. 1930-ih emigrirao je u SAD, ali se vratio u rodnu Austriju i oženio. 1940. godine, na vrhuncu rata, bio je prisiljen pobjeći u Ameriku u tranzitu kroz SSSR i Japan. Radio je neko vrijeme na Princeton Institute for Advanced Study. Nažalost, psiha naučnika to nije mogla izdržati i on je umro psihijatrijsku kliniku od gladi, odbijajući da jede, jer je bio ubeđen da nameravaju da ga otruju.

Jedna od najpoznatijih teorema u matematičkoj logici je sreća i nesreća u isto vreme. Po tome je slična Ajnštajnovoj specijalnoj teoriji relativnosti. S jedne strane, skoro svi su čuli nešto o njima. S druge strane, u narodna interpretacija Poznato je da je Ajnštajnova teorija “kaže da je sve na svijetu relativno”. I Gödelov teorem o nepotpunosti (u daljem tekstu jednostavno TGN), u približno istoj slobodnoj narodnoj formulaciji, "dokazuje da postoje stvari koje su neshvatljive ljudskom umu". I tako ga neki pokušavaju prilagoditi kao argument protiv materijalizma, dok drugi, naprotiv, uz njegovu pomoć dokazuju da Boga nema. Smiješno je ne samo da obje strane ne mogu biti u pravu u isto vrijeme, već i to što se ni jedna ni druga ne trude da shvate šta ova teorema zapravo kaže.

Pa šta? U nastavku ću pokušati da vam ispričam o tome „na prste“. Moja prezentacija će, naravno, biti nerigorozna i intuitivna, ali ću zamoliti matematičare da me ne osuđuju striktno. Moguće je da će za nematematičare (od kojih sam, u stvari, i ja) biti nešto novo i korisno u onome što je opisano u nastavku.

Matematička logika je zaista prilično složena nauka, i što je najvažnije, nije baš poznata. Zahtijeva pažljive i stroge manevre, u kojima je važno ne brkati ono što je stvarno dokazano sa onim što je „već jasno“. Međutim, nadam se da će čitaocu za razumijevanje sljedećeg “crta dokaza TGN-a” trebati samo znanje matematike/informatike u srednjoj školi, vještine logičkog razmišljanja i 15-20 minuta vremena.

Pojednostavljujući donekle, TGN tvrdi da je to dovoljno složenih jezika postoje nedokazive izjave. Ali u ovoj frazi gotovo svaka riječ treba objašnjenje.

Počnimo s pokušajem da shvatimo šta je dokaz. Uzmimo neki školski aritmetički problem. Na primjer, recimo da trebate dokazati ispravnost sljedeće jednostavne formule: “ ” (da vas podsjetim da simbol glasi “za bilo koji” i da se zove “univerzalni kvantifikator”). To možete dokazati identičnom transformacijom, recimo, ovako:

Prijelaz s jedne formule na drugu odvija se prema određenim poznata pravila. Prijelaz sa 4. formule na 5. dogodio se, recimo, zato što je svaki broj jednak samom sebi - to je aksiom aritmetike. I čitava procedura dokazivanja, dakle, prevodi formulu u Booleovu vrijednost TRUE. Rezultat bi mogao biti i LAŽ - ako bismo opovrgli neku formulu. U ovom slučaju bismo dokazali njegovo poricanje. Može se zamisliti program (a takvi programi su zapravo napisani) koji bi dokazao slične (i složenije) izjave bez ljudske intervencije.

Recimo istu stvar malo formalnije. Pretpostavimo da imamo skup koji se sastoji od nizova znakova neke abecede, a postoje pravila po kojima iz tih nizova možemo odabrati podskup tzv. izjave- odnosno gramatički značajne fraze, od kojih je svaka istinita ili netačna. Možemo reći da postoji funkcija koja naredbe povezuje s jednom od dvije vrijednosti: TRUE ili FALSE (to jest, preslikava ih u Boolean skup od dva elementa).

Nazovimo takav par - skup iskaza i funkciju od do - "jezik izjava". Imajte na umu da je u svakodnevnom smislu pojam jezika nešto širi. Na primjer, ruski izraz "Dođi ovamo!" ni istinit ni netačan, odnosno, sa stanovišta matematičke logike, to nije izjava.

Za ono što slijedi, potreban nam je koncept algoritma. Neću davati formalnu definiciju toga ovdje - to bi nas odvelo prilično daleko. Ograničiću se na neformalno: "algoritam" je niz nedvosmislenih instrukcija (“program”) koji u konačnom broju koraka pretvara izvorne podatke u rezultate. Ono što je u kurzivu je fundamentalno važno - ako program petlja na nekim početnim podacima, onda ne opisuje algoritam. Radi jednostavnosti i primjene na naš slučaj, čitalac može smatrati da je algoritam program napisan na bilo kojem njemu poznatom programskom jeziku, za koji je zagarantovano da će, za bilo koji ulazni podatak iz date klase, završiti svoj rad dajući Boolean rezultat.

Zapitajmo se: za svaku funkciju postoji “algoritam za dokazivanje” (ili, ukratko, "deduktivan"), ekvivalentno ovoj funkciji, odnosno pretvaranje svake izjave u potpuno istu Booleovu vrijednost kao i ona? Isto pitanje može se sažetije formulirati na sljedeći način: da li je svaka funkcija nad skupom iskaza izračunljiv? Kao što ste već pretpostavili, iz valjanosti TGN-a proizilazi da ne, ne svaka funkcija - postoje neizračunljive funkcije ovog tipa. Drugim riječima, ne može se dokazati svaka istinita izjava.

Vrlo je moguće da će ova izjava kod vas izazvati interni protest. To je zbog nekoliko okolnosti. Prvo, kada nas uče skolska matematika, onda se ponekad stvara lažni utisak o gotovo potpunoj istovjetnosti izraza „teorema je istinita“ i „teorema se može dokazati ili potvrditi“. Ali, ako razmislite o tome, to nije nimalo očigledno. Neke teoreme se dokazuju prilično jednostavno (na primjer, isprobavanjem malog broja opcija), dok su druge vrlo teške. Razmotrimo, na primjer, Fermatovu čuvenu Posljednju teoremu:

čiji je dokaz pronađen tek tri i po stoljeća nakon prve formulacije (i daleko je od elementarnog). Potrebno je razlikovati istinitost iskaza i njegovu dokazivost. Nigde ne proizilazi da ne postoje istinite, već nedokazive (i ne u potpunosti proverljive) izjave.

Drugi intuitivni argument protiv TGN-a je suptilniji. Recimo da imamo neku nedokazivu (u okviru ove deduktivne) tvrdnje. Šta nas sprečava da to prihvatimo kao novi aksiom? Tako ćemo malo zakomplikovati naš sistem dokaza, ali to nije strašno. Ovaj argument bi bio potpuno tačan da postoji konačan broj nedokazivih izjava. U praksi se može dogoditi sljedeće: nakon postuliranja novog aksioma, naiđete na novu nedokazivu tvrdnju. Ako to prihvatite kao još jedan aksiom, naići ćete na treći. I tako redom do beskonačnosti. Kažu da će odbitak ostati nepotpuna. Također možemo natjerati algoritam za dokazivanje da završi u konačnom broju koraka sa nekim rezultatom za bilo koji izgovor jezika. Ali u isto vrijeme, on će početi lagati - dovodeći do istine za netačne izjave, ili do laži - za vjernike. U takvim slučajevima kažu taj odbitak kontradiktorno. Dakle, druga formulacija TGN-a zvuči ovako: "Postoje propozicijski jezici za koje je nemoguća potpuna dosljedna deduktivnost" - otuda i naziv teoreme.

Ponekad se naziva "Gödelov teorem", izjava je da bilo koja teorija sadrži probleme koji se ne mogu riješiti unutar okvira same teorije i zahtijevaju njenu generalizaciju. U određenom smislu to je tačno, iako ova formulacija teži da zamagli problem, a ne da ga razjasni.

Također ću napomenuti da ako govorimo o uobičajenim funkcijama koje prikazuju skup realni brojevi u njega, onda "neizračunljivost" funkcije nikoga ne bi iznenadila (samo nemojte brkati "izračunljive funkcije" i "izračunljive brojeve" - ​​to su različite stvari). Svaki školarac zna da, recimo, u slučaju funkcije, morate imati veliku sreću s argumentom da bi se proces izračunavanja točne decimalne reprezentacije vrijednosti ove funkcije završio u konačnom broju koraka. Ali najvjerovatnije ćete ga izračunati pomoću beskonačnog niza, a ovo izračunavanje nikada neće dovesti do tačnog rezultata, iako se može približiti koliko god želite - jednostavno zato što je vrijednost sinusa većine argumenata iracionalna. TGN nam jednostavno govori da čak i među funkcijama čiji su argumenti nizovi i čije su vrijednosti nula ili jedan, postoje i neizračunljive funkcije, iako su strukturirane na potpuno drugačiji način.

U daljnje svrhe, opisat ćemo „jezik formalne aritmetike“. Razmotrimo klasu tekstualnih nizova konačne dužine, koja se sastoji od arapskih brojeva, varijabli (slova latinske abecede) koje uzimaju prirodne vrijednosti, razmaka, aritmetičkih znakova, jednakosti i nejednakosti, kvantifikatora („postoji“) i („za bilo koje“) i , možda , neki drugi simboli (njihov tačan broj i sastav su za nas nevažni). Jasno je da nisu svi takvi redovi smisleni (na primjer, “ ” je besmislica). Podskup smislenih izraza iz ove klase (to jest, nizovi koji su istiniti ili netačni sa stanovišta obične aritmetike) biće naš skup iskaza.

Primjeri formalnih aritmetičkih iskaza:

itd. Nazovimo sada "formulu sa slobodnim parametrom" (FSP) stringom koji postaje izraz ako se u njega kao ovaj parametar unese prirodni broj. Primjeri FSP-a (sa parametrom):

itd. Drugim riječima, FSP-ovi su ekvivalentni prirodnim argument funkcijama s Booleovim vrijednostima.

Označimo skup svih FSP-ova slovom . Jasno je da se može poređati (npr. prvo ispisujemo jednoslovne formule poredane po abecednom redu, zatim dvoslovne itd.; nije nam bitno kojim će se pismom redati). Dakle, bilo koji FSP odgovara svom broju u uređenoj listi, a mi ćemo ga označiti .

Pređimo sada na skicu dokaza TGN-a u sljedećoj formulaciji:

• Za propozicioni jezik formalne aritmetike ne postoji potpuni konzistentan deduktivni sistem.

Mi ćemo to dokazati kontradikcijom.

Dakle, pretpostavimo da takav deduktivni sistem postoji. Hajde da opišemo sledeći pomoćni algoritam, koji dodeljuje Booleovu vrednost prirodnom broju na sledeći način:

Jednostavno rečeno, algoritam daje vrijednost TRUE ako i samo ako rezultat zamjene vlastitog broja u FSP-u na našoj listi daje lažnu izjavu.

Ovdje dolazimo do jedinog mjesta gdje ću zamoliti čitaoca da mi vjeruje na riječ.

Očigledno je da se, pod pretpostavkom koja je gore napravljena, bilo koji FSP može uporediti sa algoritmom koji sadrži prirodni broj na ulazu i Booleovu vrijednost na izlazu. Obrnuto je manje očigledno:

Dokaz ove leme zahtevao bi, u najmanju ruku, formalnu, a ne intuitivnu definiciju koncepta algoritma. Međutim, ako malo razmislite, to je sasvim uvjerljivo. Zapravo, algoritmi su napisani na algoritamskim jezicima, među kojima ima i egzotičnih, kao što je, na primjer, Brainfuck, koji se sastoji od osam riječi od jednog znaka, u kojima se, ipak, može implementirati bilo koji algoritam. Bilo bi čudno kada bi se bogatiji jezik formula formalne aritmetike koji smo opisali pokazao lošijim - iako, bez sumnje, nije baš pogodan za obično programiranje.

Prošavši ovo klizavo mjesto, brzo stižemo do kraja.

Dakle, gore smo opisali algoritam. Prema lemi u koju sam vas zamolio da vjerujete, postoji ekvivalentni FSP. Ima neki broj na listi - recimo, . Zapitajmo se, čemu je jednako? Neka ovo bude ISTINA. Zatim, prema konstrukciji algoritma (a samim tim i funkciji koja mu je ekvivalentna), to znači da je rezultat zamjene broja u funkciju FALSE. Na isti način se provjerava suprotno: iz FALSE slijedi TRUE. Došli smo do kontradikcije, što znači da je prvobitna pretpostavka netačna. Dakle, ne postoji potpuni konzistentan deduktivni sistem za formalnu aritmetiku. Q.E.D.

Ovdje je prikladno podsjetiti se na Epimenida (vidi portret u naslovu), koji je, kao što je poznato, izjavio da su svi Krićani lažovi, a da je i sam Krićanin. U sažetijoj formulaciji, njegova izjava (poznata kao “paradoks lažova”) može se reći na sljedeći način: “Lažem”. Upravo smo ovu vrstu iskaza, koji sami proglašavaju netačnim, koristili za dokaz.

U zaključku, želim napomenuti da TGN ne tvrdi ništa posebno iznenađujuće. Na kraju, svi su odavno navikli na činjenicu da se svi brojevi ne mogu predstaviti kao omjer dva cijela broja (zapamtite, ova izjava ima vrlo elegantan dokaz star više od dvije hiljade godina?). A nisu ni svi brojevi korijeni polinoma s racionalnim koeficijentima. A sada se ispostavlja da nisu sve funkcije prirodnog argumenta izračunljive.

Skica datog dokaza bila je za formalnu aritmetiku, ali je lako vidjeti da je TGN primjenjiv na mnoge druge propozicione jezike. Naravno, nisu svi jezici ovakvi. Na primjer, definirajmo jezik na sljedeći način:

• „Bilo koja fraza kineski jezik je istinita izjava, ako se nalazi u citatniku druga Mao Zedonga, i netačan ako nije sadržan.”

Tada odgovarajući kompletan i dosljedan algoritam dokazivanja (moglo bi se nazvati “dogmatski deduktivni”) izgleda otprilike ovako:

• “Prelistavajte citatnik druga Mao Zedonga dok ne pronađete izreku koju tražite. Ako se nađe, onda je istina, ali ako je citatnik gotov, a izjava nije pronađena, onda je netačna.”

Ono što nas ovdje spašava je to što je svaki citatnik očigledno konačan, tako da će se proces “dokazivanja” neizbježno završiti. Dakle, TGN nije primjenjiv na jezik dogmatskih izjava. Ali pričali smo o složenim jezicima, zar ne?

na temu: “GODELOVA TEOREMA”

Kurt Gödel

Kurt Gödel, glavni specijalista matematičke logike, rođen je 28. aprila 1906. u Brunnu (danas Brno, Češka). Diplomirao je na Univerzitetu u Beču, gdje je odbranio doktorsku disertaciju, a bio je docent 1933–1938. Nakon anšlusa emigrirao je u SAD. Od 1940. do 1963. Gödel je radio na Princeton Institute of Advanced Studies. Gödel je počasni doktor univerziteta Yale i Harvard, član je Nacionalne akademije nauka SAD i Američkog filozofskog društva.

Kurt Gödel je 1951. godine dobio najvišu naučnu nagradu u Sjedinjenim Državama - Einsteinovu nagradu. U članku posvećenom ovom događaju, drugi veliki matematičar našeg vremena, John von Neumann, napisao je: „Doprinos Kurta Gödela modernoj logici je zaista monumentalan. Ovo je više od spomenika. Ovo je prekretnica koja razdvaja dvije ere... Bez ikakvog preterivanja, može se reći da je Gödelov rad radikalno promijenio sam predmet logike kao nauke.”

Zaista, čak i suhi popis Gödelovih dostignuća u matematičkoj logici pokazuje da je njihov autor u suštini postavio temelje za čitave dijelove ove nauke: teoriju modela (1930; tzv. teorema o potpunosti uskog predikatskog računa, pokazujući, grubo govoreći, dovoljnost sredstava „formalne logike” „da dokaže sve istinite rečenice izražene njenim jezikom), konstruktivnu logiku (1932–1933; rezultira mogućnošću svođenja određenih klasa rečenica klasične logike na njihove intuicionističke analoge, što je postavilo temelj za sistematsku upotrebu „operacija uranjanja“ koje omogućavaju takvo smanjenje raznih logičkih sistema jedni druge), formalna aritmetika (1932–1933; rezultati o mogućnosti svođenja klasične aritmetike na intuicionističku aritmetiku, pokazujući u određenom smislu konzistentnost prve u odnosu na drugu), teoriju algoritama i rekurzivnih funkcija (1934; definicija koncepta opće rekurzivne funkcije, koja je odigrala odlučujuću ulogu u utvrđivanju algoritamske nerješivosti niza najvažnijih problema u matematici, s jedne strane, i u realizaciji logičko-matematičkih problema na elektronskim računarima drugi), aksiomatska teorija skupova (1938; dokaz relativne konzistentnosti aksioma izbora i Cantorove hipoteze kontinuuma iz teorije skupova, koja je postavila temelje za niz važnih rezultata o relativnoj konzistentnosti i nezavisnosti teorije skupova). principi).

Gedelov teorem o nepotpunosti

Uvod

Godine 1931. u jednom od njemačkih naučnih časopisa pojavio se relativno mali članak s prilično zastrašujućim naslovom “O formalno neodlučivim propozicijama Principia Mathematica i srodnih sistema”. Njegov autor je bio dvadesetpetogodišnji matematičar sa Univerziteta u Beču Kurt Gödel, koji je kasnije radio na Princeton Institute for Advanced Study. Ovo djelo je odigralo odlučujuću ulogu u historiji logike i matematike. Odluka Univerziteta Harvard da dodeli Gödel počasni doktorat (1952) opisala ju je kao jednu od najveća dostignuća moderna logika.

Međutim, u vrijeme objavljivanja, ni naziv Gödelovog djela. Ni njegov sadržaj većini matematičara nije ništa značio. Pomenuta u svom naslovu, Principia Mathematica je monumentalna rasprava Alfreda North Whiteheada i Bertranda Russela u tri toma o matematičkoj logici i osnovama matematike; poznavanje traktata nikako nije bio neophodan uslov za uspešan rad u većini grana matematike. Interesovanje za pitanja koja se obrađuju u Gödelovom radu oduvijek je bila u nadležnosti vrlo male grupe naučnika. U isto vrijeme, obrazloženje koje je Gödel dao u svojim dokazima bilo je tako neobično za svoje vrijeme. Za njihovo potpuno razumijevanje bilo je potrebno izuzetno poznavanje predmeta i poznavanje literature posvećene ovim vrlo specifičnim problemima.

Prva teorema o nepotpunosti

Gödelov prvi teorem o nepotpunosti, očigledno je najznačajniji rezultat u matematičkoj logici. Zvuči ovako:

Za proizvoljnu konzistentnu formalnu i izračunljivu teoriju u kojoj se osnovni aritmetički iskazi mogu dokazati, može se konstruirati istinita aritmetička izjava, čija se istinitost ne može dokazati u okviru teorije. Drugim riječima, bilo koja potpuno korisna teorija dovoljna da predstavi aritmetiku ne može biti i konzistentna i potpuna.

Ovdje riječ “teorija” znači “beskonačan broj” tvrdnji, od kojih se za neke vjeruje da su istinite bez dokaza (takve se tvrdnje nazivaju aksiomi), dok se druge (teoreme) mogu izvesti iz aksioma i stoga im se vjeruje (dokazano ) da bude istina. Izraz “teorijski dokazivo” znači “izvodljivo iz aksioma i primitiva teorije (konstantni simboli abecede) koristeći standardnu ​​(prvog reda) logiku.” Teorija je konzistentna (konzistentna) ako je u njoj nemoguće dokazati kontradiktornu tvrdnju. Izraz “može se konstruirati” znači da postoji neka mehanička procedura (algoritam) koja može konstruirati iskaz zasnovan na aksiomima, primitivima i logici prvog reda. “Elementarna aritmetika” se sastoji od operacija sabiranja i množenja prirodnih brojeva. Rezultirajuća istinita, ali nedokaziva izjava se za datu teoriju često naziva „Gödelov niz“, ali postoji beskonačan broj drugih izjava u teoriji koje imaju isto svojstvo: nedokaziva istina unutar teorije.

Pretpostavka da je teorija izračunljiva znači da je u principu moguća implementirati kompjuterski algoritam (kompjuterski program), koji (ako mu je dozvoljeno da računa u proizvoljno dugom vremenu, do beskonačnosti) će izračunati listu svih teorema teorije. U stvari, dovoljno je izračunati samo listu aksioma, a sve teoreme se mogu efikasno dobiti iz takve liste.

Prva teorema o nekompletnosti bila je naslovljena "Teorema VI" u Gödelovom radu iz 1931. O formalno neodlučivim propozicijama u Principia Mathematica i srodnim sistemima I. U originalnom Gödelovom snimku zvučalo je ovako:

“Opšti zaključak o postojanju neodlučivih propozicija je sljedeći:

Teorema VI .

Za svaku ω-konzistentnu rekurzivnu klasu k FORMULA postoje rekurzivni ZNAKOVI r tako da ni jedno ni drugo (v Gen r), niti ¬( v Gen r)ne pripadaju Flg (k)(gdje je v FREE VARIABLE r ) ».

Oznaka Flg dolazi od njega. Folgerungsmenge– mnogo sekvenci, Gen dolazi od njega. Generalizacija– generalizacija.

Grubo rečeno, Gödelova izjava G navodi: „istina G ne može se dokazati." Ako G može se dokazati u okviru teorije, onda bi u ovom slučaju teorija sadržavala teoremu koja je kontradiktorna sama sebi, pa bi stoga teorija bila kontradiktorna. Ali ako G nedokazivo, onda je istinito i stoga je teorija nekompletna (tvrdnja G se u njemu ne može zaključiti).

Ovo je objašnjenje na čistom engleskom prirodni jezik, pa stoga nije sasvim matematički rigorozna. Da bi pružio rigorozan dokaz, Gödel je numerisao izjave koristeći prirodni brojevi. U ovom slučaju, teorija koja opisuje brojeve takođe pripada skupu iskaza. Pitanja o dokazivosti iskaza mogu se u ovom slučaju predstaviti u obliku pitanja o svojstvima prirodnih brojeva, koji moraju biti izračunljivi ako je teorija potpuna. U ovim terminima, Gödelova izjava kaže da ne postoji broj sa nekim specifičnim svojstvom. Broj sa ovim svojstvom će biti dokaz nekonzistentnosti teorije. Ako takav broj postoji, teorija je nedosljedna, suprotno prvobitnoj pretpostavci. Dakle, pod pretpostavkom da je teorija konzistentna (kao što se pretpostavlja u premisi teoreme), ispada da takav broj ne postoji, a Gödelov iskaz je istinit, ali ga je u okviru teorije nemoguće dokazati ( stoga je teorija nekompletna). Važna konceptualna tačka je da je neophodno pretpostaviti da je teorija konzistentna da bi se Gedelov iskaz proglasio istinitim.

Druga Gödelova teorema o nepotpunosti

Gödelova druga teorema o nepotpunosti glasi kako slijedi:

Za bilo koju formalno rekurzivno nabrojivu (tj. efektivno generiranu) teoriju T, uključujući osnovne izjave aritmetičke istine i određene izjave formalne dokazivosti, data teorija T uključuje tvrdnju o njenoj konzistentnosti ako i samo ako je teorija T nekonzistentna.

Drugim riječima, konzistentnost dovoljno bogate teorije ne može se dokazati pomoću ove teorije. Međutim, može se ispostaviti da se konzistentnost jedne određene teorije može uspostaviti pomoću druge, snažnije formalne teorije. Ali onda se postavlja pitanje konzistentnosti ove druge teorije itd.

Mnogi su pokušali da koriste ovu teoremu da dokažu da se inteligentna aktivnost ne može svesti na proračune. Na primjer, davne 1961. godine poznati logičar John Lucas smislio je sličan program. Pokazalo se da je njegovo razmišljanje prilično ranjivo - međutim, zadatak je postavio šire. Roger Penrose ima malo drugačiji pristup, koji je u knjizi u potpunosti opisan, „od nule“.

Diskusije

Posledice teorema utiču na filozofiju matematike, posebno na one formalizme koji koriste formalnu logiku da definišu svoje principe. Prvu teoremu o nepotpunosti možemo preformulisati na sljedeći način: “ nemoguće je pronaći sveobuhvatni sistem aksioma koji bi se mogao dokazati Sve matematičke istine, a nijedna laž" S druge strane, sa stanovišta stroge formalnosti, ova preformulacija nema mnogo smisla, jer pretpostavlja da su pojmovi „istina“ i „laž“ definisani u apsolutnom smislu, a ne u relativnom smislu za svaku konkretnu sistem.