>

Gödelov teorem o formalnoj logici. Zanimljive činjenice i korisni savjeti

Gedelove teoreme o nepotpunosti

Gedelove teoreme o nepotpunosti

Gedelove teoreme o nepotpunosti- dvije teoreme matematičke logike o osnovnim ograničenjima formalne aritmetike i, kao posljedica, bilo koje dovoljno jake teorije prvog reda.

Prva teorema kaže da ako je formalna aritmetika konzistentna, onda sadrži neoborivu i neoborivu formulu.

Druga teorema kaže da ako je formalna aritmetika konzistentna, onda je neka formula u njoj neizvodljiva, što smisleno potvrđuje konzistentnost ove teorije.

Gödelov prvi teorem o nepotpunosti

Tvrdnja prve Gödelove teoreme o nepotpunosti može se izreći na sljedeći način:

Ako je formalna aritmetika S je konzistentan, onda sadrži zatvorenu formulu G takvu da ni G ni njegova negacija ¬G nisu izvodljivi u S .

U dokazivanju teoreme, Gödel je konstruirao formulu G eksplicitno, ponekad se naziva i Gödelova nerješiva ​​formula. U standardnom tumačenju, rečenica G potvrđuje sopstvenu neizvodljivost u S. Prema tome, prema Gödelovom teoremu, ako je teorija S konzistentna, onda je ova formula zaista neizvodljiva u S i stoga istinita u standardnoj interpretaciji. Dakle, za prirodne brojeve, formula G je tačno, ali se ne može izvesti u S.

Gödelov dokaz se također može izvesti za bilo koju teoriju dobivenu iz S dodavanjem novih aksioma, na primjer, formule G kao aksiom. Stoga će svaka konzistentna teorija koja je proširenje formalne aritmetike biti nepotpuna.

Da bi dokazao prvi teorem o nepotpunosti, Gödel je svakom simbolu, izrazu i nizu izraza u formalnoj aritmetici dodijelio određeni broj. Budući da su formule i teoreme rečenice aritmetike, a formalne derivacije teorema nizovi formula, postalo je moguće govoriti o teoremama i dokazima u terminima prirodnih brojeva. Na primjer, neka je Gödelova nerješiva ​​formula G ima broj m, onda je to ekvivalentno sljedećoj izjavi na jeziku aritmetike: "ne postoji takav prirodni broj n, Šta n postoji derivacija formule broj sa brojem m Ovakvo poređenje formula i prirodnih brojeva naziva se aritmetizacija matematike i po prvi put je izveo Gödel. Ova ideja je kasnije postala ključ za rješavanje mnogih važnih problema matematičke logike.

probna skica

Popravimo neki formalni sistem PM u kojem se mogu predstaviti elementarni matematički koncepti.

Izrazi formalnog sistema su, izvana, konačni nizovi primitivnih simbola (varijable, logičke konstante i zagrade ili tačke) i nije teško striktno odrediti koji nizovi primitivnih simbola su formule, a koji nisu. Slično, sa formalne tačke gledišta, dokazi nisu ništa drugo do konačni nizovi formula (sa strogo definisanim svojstvima). Za matematičko razmatranje, nije važno koje objekte uzeti kao primitivne simbole, a mi odlučujemo koristiti prirodne brojeve u ove svrhe. Prema tome, formula je konačan niz prirodnih brojeva, derivacija formule je konačan niz konačnih nizova prirodnih brojeva. Matematički pojmovi (iskazi) tako postaju pojmovi (tvrdnje) o prirodnim brojevima ili njihovim nizovima, pa se stoga i sami mogu izraziti u simbolici PM sistema (barem djelomično). Može se posebno pokazati da su pojmovi "formula", "derivacija", "formula koja se može izvesti" definisati unutar PM sistema, odnosno da se može povratiti, na primjer, formula F(v) u PM sa jednom slobodnom varijablom v(čiji je tip numerički niz) tako da F(v), u intuitivnom tumačenju, znači: v- izvodljiva formula. Sada konstruirajmo neodlučivu rečenicu PM sistema, odnosno rečenicu A, za koje ni jedno ni drugo A, niti ne-A ne može se zaključiti, kako slijedi:

Formula u PM-u sa tačno jednom slobodnom promenljivom čiji je tip prirodan broj (klasa klasa) zvaće se klasa izraza. Hajde da na neki način uredimo izraze klase u nizu, označimo n-e kroz R(n), i napominjemo da je koncept "klasa-izraz", kao i odnos narudžbe R može se definisati u PM sistemu. Neka je α proizvoljan klasni izraz; kroz [α; n] označava formulu koja se formira iz izraza klase α zamjenom slobodne varijable simbolom prirodnog broja n. Ternarna relacija x = [y;z] se također ispostavilo da se može definirati u PM-u. Sada ćemo definisati klasu K prirodni brojevi kako slijedi:

n ∈ K≡ ¬Bew[ R(n);n] (*)

(gde Bew x znači: x- izvodljiva formula). Budući da se svi koncepti koji se javljaju u ovoj definiciji mogu biti izraženi u PM, isto vrijedi i za koncept K, koji je izgrađen od njih, odnosno postoji takav class-izraz S da je formula [ S;n], što se intuitivno tumači, znači da je prirodan broj n pripada K. Kao izraz klase, S identično nekom posebnom R(q) u našoj numeraciji, tj

S = R(q)

važi za neki određeni prirodni broj q. Pokažimo sada da rečenica [ R(q);q] je neodlučivo u PM. Dakle, ako rečenica [ R(q);q] se pretpostavlja da je izvodljivo, onda se ispostavlja da je istinito, odnosno u skladu sa gore navedenim, q pripadaće K, odnosno prema (*), ¬Bew[ R(q);q] će biti zadovoljan, što je u suprotnosti sa našom pretpostavkom. S druge strane, ako je negacija [ R(q);q] je bilo moguće izvesti, zatim ¬ n ∈ K, odnosno Bew[ R(q);q] će biti istina. Dakle, [ R(q);q] zajedno sa svojom negacijom biće izvodljivi, što je opet nemoguće.

Polinomski oblik

Za svaku konzistentnu teoriju T može se specificirati takva cjelobrojna vrijednost parametra K da jednačina (θ + 2 z − b 5) 2 + (u + tθ − l) 2 + (y + mθ − e) 2 + (n − q 16) 2 + ((g + eq 3 + lq 5 + (2(e − zλ)(1 + g) 4 + λ b 5+λ b 5 q 4)q 4)(n 2 − n) + (q 3 − bl + l + θλ q 3 + (b 5 − 2)q 5)(n 2 − 1) − r) 2 + (str − 2ws 2 r 2 n 2) 2 + (str 2 k 2 − k 2 + 1 − τ 2) 2 + (4(c − ksn 2) 2 + η − k 2) 2 + (r + 1 + hstr − h − k) 2 + (a − (wn 2 + 1)rsn 2) 2 + (2r+ 1 + φ − c) 2 + (bw + ca − 2c+ 4αγ − 5γ − d) 2 + ((a 2 − 1)c 2 + 1 − d 2) 2 + ((a 2 − 1)i 2 c 4 + 1 − f 2) 2 + (((a + f 2 (d 2 − a)) 2 − 1)(2r + 1 + jc) 2 + 1 − (d + of) 2) 2 + (((z + u + y) 2 + u) 2 + y − K) 2 = 0 nema rješenja u nenegativnim cijelim brojevima, ali se ta činjenica ne može dokazati u teoriji T . Štaviše, za svaku konzistentnu teoriju, skup vrijednosti parametra K koje imaju ovo svojstvo je beskonačan i algoritamski nenabrojiv.

Druga Gödelova teorema o nepotpunosti

U formalnoj aritmetici S, može se konstruisati formula koja je, u standardnoj interpretaciji, istinita ako i samo ako je teorija S konzistentna. Za ovu formulu je tačna izjava Gödelove druge teoreme:

Ako je formalna aritmetika S je konzistentan, onda sadrži formulu koja se ne može izvesti koja suštinski potvrđuje konzistentnost S .

Drugim riječima, konzistentnost formalne aritmetike ne može se dokazati pomoću ove teorije. Međutim, postoje dokazi o konzistentnosti formalne aritmetike koristeći sredstva koja su u njoj neizreciva.

probna skica

Prvo se pravi formula Con, smisleno izražavajući nemogućnost izvođenja bilo koje formule u teoriji S zajedno sa njenom negacijom. Tada se iskaz prve Gödelove teoreme izražava formulom Con ⊃ G, Gdje G- Gedelova nerešiva ​​formula. Svi argumenti za dokaz prve teoreme mogu se izraziti i izvesti pomoću S, odnosno iz S formula je izvodljiva Con ⊃ G. Dakle, ako je S izvodljiv Con, onda u njemu izvodimo i G. Međutim, prema Gödelovom prvom teoremu, ako je S konzistentan, onda G u njemu nije izvodljivo. Stoga, ako je S konzistentan, onda formula Con.

Bilješke

vidi takođe

Linkovi

  • V. A. Uspensky Godelova teorema o nepotpunosti. - M.: Nauka, 1982. - 110 str. - (Popularna predavanja iz matematike).
  • akademik Yu. L. Ershov "Dokazi u matematici", Program A. Gordona od 16. juna 2003
  • A. B. Sosinsky Gödelov teorem // ljetna škola "Savremena matematika". - Dubna: 2006.
  • P. J. Cohen Na temeljima teorije skupova // Napredak u matematičkim naukama. - 1974. - T. 29. - br. 5 (179). - S. 169–176.
  • M. Kordonsky Kraj istine. - ISBN 5-946448-001-04
  • V. A. Uspensky Gedelova teorema o nepotpunosti i četiri puta koja vode do nje // ljetna škola "Savremena matematika". - Dubna: 2007.
  • Zenkin A. A. Princip dijeljenja vremena i analiza jedne klase kvazi-konačnih vjerodostojnih razmišljanja (na primjeru teoreme o nebrojenosti G. Kantora) // DAN. - 1997. - T. 356. - Br. 6. - S. 733-735.
  • Čečulin V. L. O kratkoj verziji dokaza Gödelovih teorema // „Osnovni problemi matematike i informacionih nauka“, materijali XXXIV Dalekoistočne matematičke škole-seminar po imenu akademika E.V. Zolotova. - Habarovsk, Rusija: 2009. - S. 60-61.

Wikimedia fondacija. 2010 .

Pogledajte šta su "Gödelove teoreme o nepotpunosti" u drugim rječnicima:

    Ovaj izraz ima druga značenja, vidi Gedelovu teoremu. Gedelova teorema o nepotpunosti i Gedelova druga teorema [1] su dvije teoreme matematičke logike o osnovnim ograničenjima formalne aritmetike i, kao posljedica toga, bilo koje ... ... Wikipedia

    Gedelove teoreme o nepotpunosti su dvije teoreme matematičke logike o nepotpunosti formalnih sistema određene vrste. Sadržaj 1 Gödelova prva teorema o nepotpunosti 2 Gödelova druga teorema o nepotpunosti ... Wikipedia

    Ovaj izraz ima druga značenja, vidi Gedelovu teoremu. Gedelova teorema o potpunosti predikatskog računa jedna je od temeljnih teorema matematičke logike: uspostavlja nedvosmislen odnos između logičke istine ... ... Wikipedia

    Uobičajeni naziv za dvije teoreme koje je ustanovio K. Gödel. Prvi G. t. o n. tvrdi da u svakom doslednom formalnom sistemu koji sadrži minimum aritmetike (znakove i uobičajena pravila za rukovanje njima), postoji formalno neodlučivo ... ... Mathematical Encyclopedia

Ideja dokaza je da se konstruiše izraz koji bi svjedočio o tome

vlastitu nedokazivost. Ova izgradnja se može izvesti u tri koraka:

Prva faza je uspostavljanje korespondencije između formalne aritmetike i skupa cijelih brojeva (gedelizacija);

Druga faza je konstrukcija nekog posebnog svojstva za koje se ne zna da li je to teorema formalne aritmetike ili ne;

Treća faza je zamjena u umjesto x određenog cijelog broja povezanog sa samim sobom, tj. zamjena ovim brojevima svih

Prva faza. Godelizacija formalne aritmetike

Formalna aritmetika se može aritmetizirati (tj. Gaedelizirati) na sljedeći način: svakoj njenoj teoremi je dodijeljen određeni broj. Međutim, pošto je bilo koji broj također teorema, onda se svaka teorema može smatrati, s jedne strane, teoremom formalne aritmetike, as druge strane, teoremom nad skupom teorema formalne aritmetike, tj. metateorema koja odgovara dokazu određene teoreme.

Dakle, možemo zaključiti da sistem formalne aritmetike sadrži i svoj metasistem.

Sada predstavljamo naše rezultate konkretnije i detaljnije.

Prvo, možemo svakom simbolu i formalnoj aritmetici pridružiti posebnu kodnu oznaku, koja se u ovom slučaju zove Gödelov broj

Drugo, svakom nizu znakova dodjeljujemo isti Gödelov broj koristeći neku funkciju kompozicije. Neka gdje su nizovi znakova koji formiraju

Treće (i to je bitno), svakom dokazu niza aksioma i pravila zamjene (ili pravila zamjene) dodjeljuje se broj gdje označava slijed teorema korištenih u dokazu

Dakle, svakom dokazu u formalnoj aritmetici odgovara određeni broj - njegov Gödelov broj.Svako rezonovanje u formalnoj aritmetici pretvara se u proračune na skupu prirodnih brojeva.

Dakle, umjesto manipulacije simbolima, teoremama, dokazima, možete koristiti

proračuni na skupu cijelih brojeva. Bilo koji izraz kao što je, na primjer, sljedeći: dokazivo u formalnoj aritmetici, sada odgovara određenom broju, koji ćemo označiti kao

Formulirajmo sljedeći prijedlog.

Formalna metaaritmetika sadržana je u skupu prirodnih brojeva, a sama je sadržana u tumačenju formalne aritmetike.

Ova situacija s formalnom aritmetikom podsjeća na situaciju s prirodnim jezikom: na kraju krajeva, ništa nas ne sprječava da ga koristimo kako bismo u njemu formulirali njegove osnovne koncepte i pravila.

Pravilan izbor funkcije omogućava da se napravi nedvosmislen prijelaz iz A u, tj. da se dva različita broja-broja dodijele dva različita dokaza. Na primjer, Gedelove brojeve možemo izabrati na način da svaki simbol abecede formalne aritmetike ima svoj prost broj, kao što je prikazano, na primjer, u tabeli. 3.2.

Tabela 3.2

Svaka formula (koja se sastoji od simbola koji variraju od 1 do redom je kodirana nizom koji se sastoji od prvih prostih brojeva, tj. broja

gdje je prost broj.

Zauzvrat, dokaz, tj. niz formula će biti kodiran na sličan način brojem

I obrnuto, zahvaljujući ovoj metodi konstruisanja brojeva, postaje moguće, počevši od određenog broja, razlaganjem na proste faktore (zbog jedinstvenosti rastavljanja prirodnih brojeva na proizvode stepena prostih brojeva), vratiti se u dva korake do eksponenata, odnosno do primitivnih simbola formalne aritmetike. Naravno, ovo je uglavnom od teorijske važnosti, jer brojke brzo postaju prevelike.

tako da se njima može manipulisati. Međutim, treba napomenuti da je suštinska mogućnost ove operacije neophodna.

Primjer. Neka je zadan broj T, koji odgovara nekom dokazu i predstavlja proizvod prostih brojeva:

Ova dekompozicija znači da dokaz teoreme sadrži dva stupnja: jedan odgovara broju 1981027125 253, a drugi broj 1981027125 211. Ponovo dekomponirajući na proste faktore svaki od ovih brojeva, dobijamo

Iz tablice kodiranja formalne aritmetičke abecede (tabela 3.2) nalazimo da naši Gödelovi brojevi za ova dva broja

će odgovarati sljedećem dokazu:

Formula slijedi iz formule

Dakle, u metaaritmetici, vrijednost originalnog broja se dobija iz formalne aritmetike.

Druga faza. Gödelova lema

Svaki broj T povezan sa dokazom odgovara teoremi koja se može dokazati u formalnoj aritmetici. “Gaudelizirana” formalna aritmetika naziva se aritmetizirana formalna aritmetika. Pošto svaki aksiom i svako pravilo aritmetizovane formalne aritmetike odgovara nekoj aritmetičkoj operaciji, onda je uz pomoć sistematizovane provere moguće utvrditi da li dati broj T odgovara dokazu neke teoreme o broju T iu ovom slučaju obliku par konjugiranih brojeva. Izraz i su konjugirani” Reprezentabilan unutar najaritmetizovanije formalne aritmetike. To znači da postoji Gödelov broj koji digitalizuje ovu izjavu.

Došli smo do kritične tačke Gödelovog dokaza. Neka je A izraz aritmetizovane formalne aritmetike koji sadrži neku slobodnu promenljivu. Umjesto toga, možete izvršiti zamjenu nekog termina. Konkretno, moguće je zamijeniti izraz A samim izrazom A. U ovom slučaju, broj-izraz A istovremeno obavlja dvije različite uloge (vidi gornje konstrukcije

Cantor i Richard): to je i pravi izraz za zamjenu i rezultirajući termin. Ova posebna zamjena će biti označena kao Dakle, formula znači da je broj Gödelov broj dobiven zamjenom izraza A:

Gödel zatim konstruiše izraz (za koji se ne zna da li je teorema ili ne-teorema) u koji uvodi ovu zamenu. Izraz izgleda ovako:

Treća faza. Konačna zamjena

U aritmetiziranoj formalnoj aritmetici, ovaj izraz je predstavljen u numeričkom obliku. Neka je E njegov Gödelov broj. Pošto izraz sadrži slobodnu varijablu, imamo pravo izvršiti zamjenu - preko zamjene broja E i označavanja - zamjene E:

Ovaj drugi izraz označavamo sa a, a njegov Gödelov broj sa E. Hajde da damo tumačenje izraza e.

Prvo tumačenje. Ne postoji takav par za koji bi istovremeno vrijedilo sljedeće: s jedne strane, T je broj aritmetiziranog dokaza teoreme koji je sam aritmetiziran, a s druge strane, postojala bi zamjena Ali pošto postoji isti transformacija kao i ostali, on je reprezentativan u terminima i u njihovoj kodnoj notaciji - Gödelovi brojevi i, prema tome, takav broj postoji. Onda možda broj T ne postoji.

Drugo tumačenje. Ne postoji aritmetizirani dokaz T teoreme koji bi bio zamjena za E. Dakle, ako nema dokaza, to je zato što nije sama po sebi teorema. Ovo dovodi do trećeg tumačenja.

Treće tumačenje. Izraz za koji je Gödelov broj -supstitucija E nije teorema u aritmetiziranoj formalnoj aritmetici. Ali tu leži kontradiktornost, pošto je po konstrukciji sam -supstitucija za E, a broj po konstrukciji nije ništa drugo do sam broj E. Ovo implicira posljednju interpretaciju e.

09sen

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

Godine 1900. održana je Svjetska konferencija matematičara u Parizu, gdje je David Gilbert(David Hilbert, 1862–1943) je u formi teza iznio 23 najvažnija, po njegovom mišljenju, zadatka koje su teoretičari nadolazećeg dvadesetog vijeka morali riješiti. Broj dva na njegovoj listi bio je jedan od onih jednostavnih problema koji se čine očiglednim dok ne zakopate malo dublje. U modernim terminima, to je bilo pitanje: da li je matematika dovoljna sama po sebi? Hilbertov drugi zadatak svodio se na potrebu da se striktno dokaže da je sistem aksioma – osnovnih tvrdnji koje se u matematici uzimaju kao osnova bez dokaza – savršen i potpun, odnosno da omogućava matematički opis svega što postoji. Bilo je potrebno dokazati da je moguće postaviti takav sistem aksioma koji će, prvo, biti međusobno konzistentni, a drugo, iz njih se može izvući zaključak o istinitosti ili neistinitosti bilo koje tvrdnje.

Uzmimo primjer iz školske geometrije. U standardnoj euklidskoj planimetriji (geometrija na ravni) može se bezuslovno dokazati da je tvrdnja "zbir uglova trougla 180°" tačna, a tvrdnja "zbir uglova trougla je 137° " je lažno. U suštini, u euklidskoj geometriji, svaka izjava je ili lažna ili istinita, a treća nije data. A početkom dvadesetog veka matematičari su naivno verovali da istu situaciju treba posmatrati u svakom logički doslednom sistemu.

A onda 1931. neki bečki matematičar s naočalama Kurt Gödel- uzeo i objavio kratak članak koji je jednostavno preokrenuo cijeli svijet takozvane "matematičke logike". Nakon dugih i složenih matematičkih i teorijskih preambula, on je doslovno ustanovio sljedeće. Uzmimo bilo koju izjavu poput: "Pretpostavka #247 je logički nedokaziva u ovom sistemu aksioma" i nazovimo je "tvrdnjom A". Dakle, Gödel je jednostavno dokazao sljedeće zadivljujuće svojstvo bilo kojeg sistema aksioma:

"Ako se izjava A može dokazati, onda se može dokazati izjava koja nije A."

Drugim riječima, ako je moguće dokazati valjanost tvrdnje „Pretpostavka 247 nije dokaziva“, onda je moguće dokazati i valjanost tvrdnje „Pretpostavka 247 je dokaziva“. Odnosno, vraćajući se na formulaciju drugog Hilbertovog problema, ako je sistem aksioma potpun (tj. bilo koja izjava u njemu može biti dokazana), onda je nedosljedan.

Jedini izlaz iz ove situacije je prihvatanje nekompletnog sistema aksioma. Odnosno, moramo se pomiriti sa činjenicom da ćemo u kontekstu bilo kojeg logičkog sistema i dalje imati iskaze tipa A koji su očigledno tačni ili lažni, a o njihovoj istinitosti možemo suditi samo izvan okvira aksiomatike koju imamo. usvojeno. 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 Gödelove prve, ili slabe, teoreme o nepotpunosti glasi: "Svaki formalni sistem aksioma sadrži nerazjašnjene pretpostavke". Ali Gedel se tu nije zaustavio, formulišući i dokazujući Gedelovu drugu ili jaku teoremu 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 Godelove teoreme apstraktne 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. To je pokazao engleski matematičar i fizičar Roger Penrose (rođen 1931.). Gödelove teoreme može se koristiti za dokazivanje postojanja fundamentalnih razlika između ljudskog mozga i kompjutera. Poenta njegovog rezonovanja je jednostavna. Kompjuter radi strogo logički i nije u stanju da utvrdi da li je izjava A tačna ili netačna ako izlazi iz okvira aksiomatike, a takvi iskazi, prema Gödelovoj teoremi, neizbež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 ovome, ljudski mozak je superiorniji od kompjutera okovanog čistim logičkim sklopovima. Ljudski mozak je u stanju da shvati punu dubinu istine sadržanu u Gedelovim teoremama, ali kompjuter nikada ne može. Stoga je ljudski mozak sve samo ne kompjuter. On je u stanju da donosi odluke i Turingov test će proći.

Teoreme o nepotpunosti Kurta Gödela bile su prekretnica u matematici 20. vijeka. A u njegovim rukopisima, objavljenim nakon njegove smrti, sačuvan je logičan dokaz postojanja Boga. Na poslednjim Božićnim čitanjima zanimljiv izveštaj o ovom malo poznatom nasleđu izneo je vanredni profesor Tobolske bogoslovije, kandidat teologije, sveštenik Dimitrije Kirjanov. "NS" je zatražio da objasni glavne ideje naučnika.

Gödelove teoreme o nepotpunosti: rupa u matematici

- Možete li nekako popularno objasniti Gedelove teoreme o nepotpunosti? Brijač brije samo one koji se ne briju sami. Da li se brijač sam brije? Ima li ovaj famozni paradoks ikakve veze s njima?

Glavna teza logičkog dokaza postojanja Boga, koju je iznio Kurt Gödel: "Bog postoji u razmišljanju. Ali postojanje u stvarnosti je veće od postojanja samo u misli. Stoga, Bog mora postojati." Na fotografiji: autor teoreme nepotpunosti Kurt Godel sa svojim prijateljem, autorom teorije relativnosti Albertom Ajnštajnom. Preston. Amerika. 1950

— Da, naravno da jeste. Prije Gedela postojao je problem aksiomatizacije matematike i problem takvih paradoksalnih rečenica koje se formalno mogu napisati na bilo kojem jeziku. Na primjer: "Ova izjava je lažna." Šta je istina ove izjave? Ako je istina, onda je lažna, ako je lažna, onda je istinita; što rezultira lingvističkim paradoksom. Gödel je istraživao aritmetiku i u svojim teoremama pokazao da se njena konzistentnost ne može dokazati iz njenih samoočiglednih principa: aksioma sabiranja, oduzimanja, dijeljenja, množenja itd. Potrebne su nam neke dodatne pretpostavke da to opravdamo. Ovo se zasniva na najjednostavnijoj teoriji, ali šta je sa složenijim (fizičke jednadžbe, itd.)! Da bismo opravdali neki sistem rezonovanja, uvek smo prinuđeni da pribegnemo nekom dodatnom rezonovanju, koje nije opravdano u okviru sistema.

Prije svega, ovo ukazuje na ograničenost tvrdnji ljudskog uma u spoznaji stvarnosti. Odnosno, ne možemo reći da ćemo izgraditi neku vrstu sveobuhvatne teorije univerzuma koja će sve objasniti – takva teorija ne može biti naučna.

Kako matematičari sada misle o Gedelovim teoremama? Niko ih ne pokušava opovrgnuti, nekako zaobići?

“To je kao da pokušavate opovrgnuti Pitagorinu teoremu. Teoreme imaju rigorozan logički dokaz. Istovremeno se pokušavaju pronaći ograničenja u primjeni Gedelovih teorema. Ali većina kontroverzi se vrti oko filozofskih implikacija Gödelovih teorema.

Koliko je razrađen Gödelov dokaz postojanja Boga? Je li gotovo?

- To je detaljno razrađeno, iako se sam naučnik nije usudio da to objavi do svoje smrti. Gödel razvija ontološku (metafizičku. — "NS") argument koji je prvi predložio Anselm od Canterburyja. U sažetom obliku, ovaj argument se može izraziti na sljedeći način: „Bog je, po definiciji, Onaj veći od koga se ništa ne može zamisliti. Bog postoji u mislima. Ali postojanje u stvarnosti je veće od postojanja samo u mislima. Dakle, Bog mora postojati." Anselmov argument su kasnije razvili René Descartes i Gottfried Wilhelm Leibniz. Dakle, prema Descartesu, misliti Više savršeno biće, kojem nedostaje postojanje, znači pasti u logičku kontradikciju. U kontekstu ovih ideja, Gödel razvija svoju vlastitu verziju dokaza, koja doslovno staje na dvije stranice. Nažalost, izlaganje njegovog argumenta nemoguće je bez uvođenja vrlo složene modalne logike u temelje.

Naravno, logička besprijekornost Godelovih zaključaka ne tjera osobu da postane vjernik pod pritiskom sile dokaza. Ne trebamo biti naivni i misliti da ontološkim argumentima ili drugim dokazima možemo uvjeriti bilo koju razumnu osobu da vjeruje u Boga. Vjera se rađa kada se čovjek suoči licem u lice s evidentnim prisustvom vrhovne transcendentne stvarnosti Boga. Ali postoji barem jedna osoba koju je ontološki argument doveo do religijskog vjerovanja, a to je pisac Clive Staples Lewis, koji je to i sam priznao.

Daleka budućnost je daleka prošlost

Kako su se Gedelovi savremenici osjećali o njemu? Da li je bio prijatelj sa jednim od velikih naučnika?

- Ajnštajnov asistent na Prinstonu svedoči da je jedina osoba sa kojom se družio poslednjih godina života bio Kurt Gedel. Bili su različiti gotovo u svemu - Ajnštajn je društven, veseo, a Gedel izuzetno ozbiljan, potpuno usamljen i nepoverljiv. Ali imali su zajednički kvalitet: oboje su išli pravo i iskreno na centralna pitanja nauke i filozofije. Uprkos prijateljstvu sa Ajnštajnom, Gödel je imao svoj specifičan pogled na religiju. Odbacio je ideju o Bogu kao bezličnom biću, kao što je Bog bio za Ajnštajna. Tom prilikom Gödel je primijetio: „Ajnštajnova religija je previše apstraktna, poput Spinoze i indijske filozofije. Spinozin Bog je manje od osobe; moj Bog je više od osobe; jer Bog može igrati ulogu osobe.” Možda postoje duhovi koji nemaju tijelo, ali mogu komunicirati s nama i utjecati na svijet.”

Kako je Gödel završio u Americi? Bežeći od nacista?

- Da, u Ameriku je došao 1940. godine iz Nemačke, uprkos tome što su ga nacisti priznali kao Arijevca i velikog naučnika, oslobodivši ga vojne obaveze. On i njegova supruga Adele proputovali su se kroz Rusiju preko Transsibirske željeznice. Nije ostavio uspomene na ovo putovanje. Adel se sjeća samo stalnog straha noću da će stati i vratiti se nazad. Nakon osam godina života u Americi, Gödel je postao američki državljanin. Kao i svi podnosioci zahteva za državljanstvo, morao je da odgovara na pitanja u vezi sa Ustavom SAD. Kao skrupulozna osoba, vrlo pažljivo se pripremao za ovaj ispit. Na kraju je rekao da je pronašao nedosljednost u Ustavu: "Otkrio sam logičnu legitimnu mogućnost u kojoj bi Sjedinjene Države mogle postati diktatura." Njegovi prijatelji su priznali da je, bez obzira na logičku vrijednost Gödelovog argumenta, ova mogućnost bila čisto hipotetičke prirode, i upozorili su na duge razgovore o toj temi na ispitu.

Da li su Gödel i Einstein koristili ideje jedni drugih u naučnom radu?

— Godine 1949. Gödel je izrazio svoje kosmološke ideje u matematičkom eseju, koji je, prema Albertu Ajnštajnu, bio važan doprinos opštoj teoriji relativnosti. Gödel je vjerovao da će vrijeme, “taj tajanstveni i u isto vrijeme samo-kontradiktorni entitet koji čini osnovu svijeta i našeg vlastitog postojanja”, na kraju postati najveća iluzija. Ono "jednog dana" će prestati da postoji i doći će drugi oblik bića, koji se može nazvati večnošću. Ova ideja vremena dovela je velikog logičara do neočekivanog zaključka. Napisao je: „Uvjeren sam u zagrobni život, bez obzira na teologiju. Ako je svijet inteligentno izgrađen, onda mora postojati zagrobni život.”

“Vrijeme je samo-kontradiktoran entitet.” Zvuči čudno; ima li to neko fizičko značenje?

Gödel je pokazao da je u okviru Ajnštajnove jednačine moguće konstruisati kosmološki model sa zatvorenim vremenom, gde se daleka prošlost i daleka budućnost poklapaju. U ovom modelu putovanje kroz vrijeme postaje teoretski moguće. Zvuči čudno, ali matematički se može izraziti – to je poenta. Ovaj model može, ali i ne mora imati eksperimentalne implikacije. To je teorijska konstrukcija koja može, ali ne mora biti korisna u izgradnji novih kosmoloških modela. Moderna teorijska fizika, posebno kvantna kosmologija, ima tako složenu matematičku strukturu da je vrlo teško dati ovim strukturama jednoznačno filozofsko razumijevanje. Štoviše, neke od njegovih teoretskih konstrukcija su još uvijek eksperimentalno neprovjerljive iz jednostavnog razloga što njihova provjera zahtijeva detekciju čestica vrlo visoke energije. Sjetite se kako su se ljudi prestrašili zbog lansiranja Velikog hadronskog sudarača: mediji su stalno plašili ljude da dolazi smak svijeta. U stvari, bio je postavljen ozbiljan naučni eksperiment kako bi se testirali modeli kvantne kosmologije i takozvane "teorije velikog ujedinjenja". Kada bi bilo moguće otkriti takozvane Higgsove čestice, onda bi to bio sljedeći korak u našem razumijevanju najranijih faza postojanja našeg svemira. Ali dok ne postoje eksperimentalni podaci, konkurentni modeli kvantne kosmologije i dalje su samo matematički modeli.

Vjera i intuicija

“…Moj Bog je više od osobe; pošto Bog može da igra ulogu čoveka...” Da li je Gedelova vera još uvek daleko od pravoslavnog ispovedanja?

— Sačuvano je vrlo malo Gödelovih izjava o njegovoj vjeri, skupljaju se malo po malo. Uprkos činjenici da je Gödel napravio prve nacrte svoje verzije argumenta još 1941. godine, sve do 1970. godine, plašeći se podsmijeha svojih kolega, o tome nije govorio. U februaru 1970., osjetivši da mu se bliži smrt, dozvolio je svom pomoćniku da kopira verziju njegovog dokaza. Nakon Gödelove smrti 1978. godine, u njegovim radovima pronađena je nešto drugačija verzija ontološkog argumenta. Supruga Kurta Gödela, Adele, rekla je dva dana nakon muževljeve smrti da je Gödel, "iako nije išao u crkvu, bio religiozan i čitao Bibliju u krevetu svake nedjelje ujutro".

Kada govorimo o naučnicima poput Gödela, Einsteina ili recimo Galilea ili Newtona, važno je naglasiti da oni nisu bili ateisti. Videli su da iza Univerzuma postoji Razum, izvesna Viša Moć. Za mnoge naučnike, vjera u postojanje Vrhovnog Uma bila je jedna od posljedica njihovog naučnog promišljanja, a to promišljanje nije uvijek dovelo do pojave duboke religiozne veze između čovjeka i Boga. Što se tiče Gedela, može se reći da je osećao potrebu za ovom vezom, budući da je isticao da je teista, da o Bogu misli kao o ličnosti. Ali, naravno, njegova se vjera ne može nazvati pravoslavnom. Bio je, da tako kažemo, "domaći luteran".

— Možete li navesti istorijske primjere: kako različiti naučnici vjeruju u Boga? Evo genetike Francisa Collinsa, prema njegovim priznanjima, proučavanje strukture DNK dovelo je do vjere u Boga...

„Samo po sebi, prirodno znanje o Bogu nije dovoljno za spoznaju Boga. Nije dovoljno otkriti Boga proučavajući prirodu – važno je naučiti ga upoznati kroz Otkrivenje koje je Bog dao čovjeku. Dolazak osobe do vjere, bio on naučnik ili ne, uvijek se oslanja na nešto što nadilazi puke logičke ili naučne argumente. Francis Collins piše da je u vjeru došao sa 27 godina nakon dugog intelektualnog spora sa samim sobom i pod utjecajem Clivea Staplesa Lewisa. Dvoje ljudi su u istoj istorijskoj situaciji, pod istim početnim uslovima: jedan postaje vernik, drugi ateista. Samo proučavanje DNK vodi do vjerovanja u postojanje Boga. Drugi proučava i ne dolazi do toga. Dvoje ljudi gledaju sliku: jedan misli da je prelepa, a drugi kaže: "Tako-tako, obična slika!" Jedan ima ukus, intuiciju, a drugi nema. Profesor Pravoslavnog humanitarnog univerziteta Sveti Tihon Vladimir Nikolajevič Katasonov, doktor filozofije, matematičar po prvom obrazovanju, kaže: „Nijedan dokaz u matematici nije moguć bez intuicije: matematičar prvo vidi sliku, a onda formuliše dokaz.“

Pitanje o dolasku osobe u vjeru uvijek je pitanje koje nadilazi puko logičko rasuđivanje. Kako objasniti šta vas je dovelo do vjere? Čovek odgovara: Otišao sam u hram, razmišljao, čitao ovo i to, video harmoniju univerzuma; ali najvažniji, najizuzetniji trenutak, u kojem čovjek odjednom postane svjestan da je naišao na prisustvo Boga, ne može se izraziti. To je uvek tajna.

- Možete li identifikovati probleme koje savremena nauka ne može da reši?

— Svejedno, nauka je dovoljno samouveren, nezavisan i dobro uspostavljen poduhvat da tako oštro govori. To je dobar i vrlo koristan alat u ljudskim rukama. Od vremena Francisa Bacona, znanje je zaista postalo sila koja je promijenila svijet. Nauka se razvija u skladu sa svojim unutrašnjim zakonima: naučnik nastoji da shvati zakone svemira, i nema sumnje da će ovo traganje dovesti do uspjeha. Ali u isto vrijeme potrebno je biti svjestan granica nauke. Ne treba brkati nauku sa onim ideološkim pitanjima koja se mogu postaviti u vezi sa naukom. Ključni problemi današnjice nisu povezani toliko sa naučnim metodom koliko sa vrednosnim orijentacijama. Nauku tokom dugog dvadesetog veka ljudi su doživljavali kao apsolutno dobro koje doprinosi napretku čovečanstva; i vidimo da je dvadeseti vek postao najokrutniji u smislu ljudskih žrtava. I tu se postavlja pitanje vrijednosti naučnog napretka, znanja općenito. Etičke vrijednosti ne proizilaze iz same nauke. Briljantan naučnik može da izmisli oružje za uništenje čitavog čovečanstva i tu se postavlja pitanje moralne odgovornosti naučnika, na koje nauka ne može da odgovori. Nauka ne može čovjeku ukazati na smisao i svrhu njegovog postojanja. Nauka nikada neće moći odgovoriti na pitanje zašto smo ovdje? Zašto univerzum postoji? Ova pitanja se rješavaju na različitim nivoima znanja, kao što su filozofija i religija.

— Osim Gedelovih teorema, postoji li još neki dokaz da naučna metoda ima svoje granice? Da li to sami naučnici prepoznaju?

- Već početkom 20. veka filozofi Bergson i Huserl su ukazivali na relativni značaj naučnog poznavanja prirode. Sada je postalo gotovo univerzalno uvjerenje među filozofima nauke da naučne teorije predstavljaju hipotetičke modele za objašnjenje fenomena. Jedan od tvoraca kvantne mehanike, Erwin Schrödinger, rekao je da su elementarne čestice samo slike, ali da možemo bez njih. Prema filozofu i logičaru Karlu Popperu, naučne teorije su poput mreže kroz koju pokušavamo da uhvatimo svijet, one nisu kao fotografije. Naučne teorije su u stalnom razvoju i mijenjanju. Tvorci kvantne mehanike, poput Paulija, Bora, Heisenberga, govorili su o granicama naučne metode. Pauli je napisao: "...fizika i psiha se mogu smatrati dodatnim aspektima iste stvarnosti" - i fokusirao se na nesvodljivost viših nivoa bića na niže. Razna objašnjenja svaki put pokrivaju samo jedan aspekt materije, ali sveobuhvatna teorija nikada neće biti postignuta.

Ljepota i harmonija svemira pretpostavlja mogućnost njegovog saznanja naučnim metodama. U isto vrijeme, kršćani su uvijek razumjeli neshvatljivost misterije iza ovog materijalnog univerzuma. Univerzum nema utemeljenje u sebi i ukazuje na savršeni izvor bića – Boga.

Ekologija života. Nauka i otkriće: Gedelova teorema o nepotpunosti, jedna od najpoznatijih teorema u matematičkoj logici, istovremeno je i srećna i nesrećna. Po tome je slična Ajnštajnovoj specijalnoj teoriji relativnosti. S jedne strane, skoro svi su čuli nešto o njima. Prema drugom tumačenju, Ajnštajnova teorija „kaže da je sve na svetu relativno“.

Teorema Gödel o nepotpunosti, jedna od najpoznatijih teorema u matematičkoj logici, bila je sretna i nesrećna u isto vrijeme. 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 narodnoj interpretaciji Ajnštajnova teorija, kao što je poznato, " kaže da je sve na svetu relativno". A Gedelov teorem o nepotpunosti(u daljem tekstu jednostavno TGN), u približno istoj slobodnoj narodnoj formulaciji, " dokazuje da postoje stvari koje su neshvatljive ljudskom umu».

A sada neki pokušavaju da to prilagode kao argument protiv mat erijalizam , dok drugi, naprotiv, uz njegovu pomoć dokazuju, da nema boga . Smiješno je ne samo da obje strane ne mogu biti u pravu u isto vrijeme, već i da se ni jedna ni druga ne trude da dokuče šta, u stvari, ova teorema kaže.

Pa šta? U nastavku ću pokušati da "na prste" pričam o tome. Moje izlaganje, naravno, neće biti rigorozno i ​​intuitivno, ali ću zamoliti matematičare da me ne osuđuju striktno. Moguće je da će za nematematičare (kojima, u stvari, i ja pripadam), biti nešto novo i korisno u onome što je rečeno u nastavku.

Matematička logika je zaista prilično komplikovana nauka, i što je najvažnije, nije baš poznata. Zahtijeva pažljive i stroge manevre, u kojima je važno ne pobrkati stvarno dokazano sa činjenicom da je "već jasno". Međutim, nadam se da će čitatelju za razumijevanje sljedećeg „crta dokaza TGN-a“ biti potrebno samo znanje školske matematike/informatike, vještine logičkog razmišljanja i 15-20 minuta vremena.

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

Počnimo pokušavajući da shvatimo šta je dokaz. Uzmimo neki školski zadatak iz aritmetike. Na primjer, neka se traži da se dokaže ispravnost sljedeće jednostavne formule: „∀x(x−1)(x−2)−2=x(x−3)” (podsjetimo da se simbol ∀ čita „za bilo koji” i naziva se “univerzalni kvantifikator”). To se može dokazati identičnom transformacijom, recimo, ovako:

    ∀x(x−1)(x−2)−2=x(x−3)

    ∀xx2−3x+2−2=x2−3x

    ∀xx2−3x–x2+3x=0

    ∀x0=0

    ISTINITO

Prijelaz s jedne formule na drugu odvija se prema određenim dobro poznatim pravilima. Prijelaz sa 4. formule na 5. dogodio se, recimo, zato što je svaki broj jednak samom sebi - takav je aksiom aritmetike. I cijeli postupak dokazivanja, dakle, prevodi formulu u logičku vrijednost TRUE. Rezultat bi mogao biti LAŽAN - ako bismo opovrgli neku formulu. U ovom slučaju bismo dokazali njegovu negaciju. Moguće je zamisliti program (a takvi su programi zapravo napisani) koji bi dokazao takve (i složenije) tvrdnje bez ljudske intervencije.

Recimo istu stvar malo formalnije. Pretpostavimo da imamo skup koji se sastoji od nizova znakova neke abecede i postoje pravila po kojima se podskup S može odabrati iz ovih nizova takozvani iskazi - to jest, gramatički značajne fraze, od kojih je svaka tačna ili netačna. Možemo reći da postoji funkcija P koja naredbama iz S dodjeljuje jednu od dvije vrijednosti: TRUE ili FALSE (to jest, preslikava ih na Boolean skup B od dva elementa).

Nazovimo ovaj par- skup iskaza S i funkcija P od >S do B - "jezik izjava". Imajte na umu da je u svakodnevnom smislu pojam jezika nešto širi. Na primjer, ruski izraz " Pa, dođi ovamo!„nije istinito i nije lažno, odnosno, sa stanovišta matematičke logike, nije izjava.

Za ono što slijedi, potreban nam je pojam algoritma. Neću ovdje davati njegovu formalnu definiciju - to bi nas odvelo prilično u stranu. Ograničiću se na neformalno: "algoritam" je niz nedvosmislenih instrukcija ("program"), koji, u konačnom broju koraka, prevodi početne podatke u rezultat.

Kurziv je fundamentalno važan - ako se program zaglavi na nekim početnim podacima, onda ne opisuje algoritam. Radi jednostavnosti i u primjeni na naš slučaj, čitalac može smatrati da je algoritam program napisan u bilo kojem njemu poznatom programskom jeziku, za koji je zagarantovano da će za bilo koji ulazni podatak iz date klase završiti svoj rad s Booleovim rezultatom.

Zapitajmo se: za svaku funkciju P postoji “algoritam za dokazivanje” (ili, ukratko, “ deductics”) ekvivalentno ovoj funkciji, odnosno pretvaranje svake izjave u potpuno istu logičku vrijednost kao i ona? Konciznije, isto pitanje se može formulirati na sljedeći način: Je li svaka funkcija nad skupom propozicija izračunljiva?

Kao što već možete pretpostaviti, iz valjanosti TGN-a proizilazi da ne, ne bilo koje - postoje neizračunljive funkcije ovog tipa. Drugim riječima, Ne može se dokazati svaka tačna tvrdnja.

Vrlo je moguće da će ova izjava izazvati vaš interni protest. To je zbog nekoliko okolnosti. Prvo, kada nas poučavaju školskoj matematici, ponekad se stvara lažan utisak o gotovo potpunom identitetu fraza „Teorema X je istinita“ i „Moguće je dokazati ili potvrditi teoremu X“.

Ali ako razmislite o tome, to uopće nije očigledno. Neke teoreme se dokazuju prilično jednostavno (na primjer, nabrajanjem malog broja opcija), a neke su vrlo teške. Prisjetimo se, na primjer, čuvenog Velikog Fermatova teorema:

Ne postoje prirodni x,y,z i n>2 takvi da je xn+yn=zn,

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

Drugi intuitivni argument protiv TGN-a je suptilniji. Pretpostavimo 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 savršeno tačan da postoji konačan broj nedokazivih tvrdnji. U praksi se može dogoditi sljedeće: nakon postuliranja novog aksioma, naići ćete na novu nedokazivu tvrdnju. Uzmite to kao još jedan aksiom - naići ćete na treći. I tako u nedogled.

Kažu to odbitak će ostati nepotpun. Također možemo poduzeti snažne mjere tako da se algoritam za dokazivanje završi nakon konačnog broja koraka s nekim rezultatom za bilo koju izjavu jezika. Ali u isto vrijeme, on će početi lagati - dovesti do istine za netačne izjave, ili do laži - za vjernike.

U takvim slučajevima se kaže da je deduktiv nedosljedan. Dakle, druga formulacija TGN-a zvuči ovako: Postoje propozicioni jezici za koje je nemoguća potpuna konzistentna dedukcija.- otuda i naziv teoreme.

Ponekad se naziva "Gödelov teorem" tvrdnja 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 takva formulacija zamagljuje problem, a ne razjašnjava ga.

Također napominjem da ako govorimo o uobičajenim funkcijama koje preslikavaju skup realnih brojeva 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).

Kurt Gödel

Svaki školarac zna da, recimo, u slučaju sin⁡x funkcije morate imati veliku sreću s argumentom tako da se proces izračunavanja tačne decimalne reprezentacije vrijednosti ove funkcije završava u konačnom broju koraka.

I najvjerovatnije ćete ga izračunati koristeći beskonačan niz, a ovaj proračun 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 raspoređene na potpuno drugačiji način.

U nastavku ćemo opisati "jezik formalne aritmetike". Razmotrimo klasu tekstualnih nizova konačne dužine, koja se sastoji od arapskih brojeva, varijabli (slova latinskog alfabeta) koje uzimaju prirodne vrijednosti, razmaka, znakova aritmetičkih operacija, jednakosti i nejednakosti, kvantifikatora ∃ („postoji“) i ∀ („za bilo koji”) 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, "12=+∀x>" je besmislica). Podskup smislenih izraza iz ove klase (to jest, nizovi koji su istiniti ili netačni u smislu obične aritmetike) biće naš skup iskaza.

Primjeri formalnih aritmetičkih iskaza:

    1=1

    2×2=5

    ∃xx>3

    ∀y∀zy×z>y+ z

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

    x=0

    2x2=x

    ∃yx+y>x

itd. Drugim riječima, FSP-ovi su ekvivalentni funkcijama prirodnog argumenta s Booleovom vrijednošću.

Označimo skup svih FSP-ova slovom F. Jasno je da se može poredati (na primjer, prvo ispisujemo jednoslovne formule poredane po abecednom redu, zatim formule od dva slova, itd.; to nije fundamentalno za nas koje pismo će se naručiti). Dakle, bilo koji FSP odgovara svom broju k u uređenoj listi, a mi ćemo ga označiti sa Fk.

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

Za propozicioni jezik formalne aritmetike ne postoji potpuna konzistentna dedukcija.

Dokazaćemo kontradikcijom.

Dakle, pretpostavimo da takav deduktiv postoji. Opišimo sljedeći pomoćni algoritam A, koji povezuje prirodni broj k s Booleovom vrijednošću na sljedeći način:

1. Pronađite k-tu formulu na listi F.

2. Zamijenite broj k u njega kao argument.

3. Na primljeni iskaz primjenjujemo naš algoritam dokazivanja (prema našoj pretpostavci, on postoji), koji ga prevodi u TRUE ili FALSE.

4. Primijenite logičku negaciju na rezultat.

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

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

Očigledno, pod gornjom pretpostavkom, bilo koji FSP iz F može biti povezan s algoritmom koji sadrži prirodni broj na ulazu i Booleovu vrijednost na izlazu.

Manje očigledno je suprotno:

Lema: Svaki algoritam koji pretvara prirodni broj u Booleovu vrijednost odgovara nekom FSP-u iz skupa F.

Dokaz ove leme zahtijevao bi barem formalnu, a ne intuitivnu definiciju pojma algoritma. Međutim, ako malo razmislite, prilično je 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 formalnih aritmetičkih formula koji smo opisali pokazao lošijim - iako, bez sumnje, nije baš pogodan za obično programiranje.

Nakon prolaska ovog klizavog mjesta, brzo dolazimo do kraja.

Dakle, gore smo opisali algoritam A. Prema lemi u koju sam vas zamolio da vjerujete, postoji ekvivalentni FSP. Ima neki broj u listi F - recimo n. Zapitajmo se čemu je jednako Fn(n)? Neka bude ISTINA. Zatim, konstrukcijom algoritma A (a samim tim i ekvivalentne funkcije Fn), to znači da je rezultat zamjene broja n u funkciju Fn FALSE.

Suprotno se provjerava na isti način: Fn(n)=FALSE implicira Fn(n)=TRUE. Došli smo do kontradikcije, što znači da je prvobitna pretpostavka pogrešna. Dakle, za formalnu aritmetiku ne postoji potpuna konzistentna dedukcija. Q.E.D.

Ovdje je prikladno prisjetiti se Epimenida, koji je, kao što znate, izjavio da su svi Krićani lažovi, budući da je i sam Krićanin. U sažetijoj formulaciji, njegova izjava (poznata kao "paradoks lažova") može se formulisati ovako: Ležim". Upravo takvu tvrdnju, koja sama proglašava svoju neistinitost, koristili smo za dokaz.

U zaključku, želim napomenuti da TGN ne tvrdi ništa posebno iznenađujuće. Uostalom, 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?).I korijeni polinoma s racionalnim koeficijentima takođe nisu svi brojevi . A sada se pokazalo da nisu sve funkcije prirodnog argumenta izračunljive.

Skica dokaza je bila za formalnu aritmetiku, ali nije teško vidjeti da se THN primjenjuje i na mnoge druge propozicione jezike. Naravno, nisu svi jezici takvi. Na primjer, definirajmo jezik ovako:

"Svaka fraza na kineskom jeziku je istinita ako je sadržana u citatniku druga Mao Tse Tunga, a netačna je ako nije sadržana."

Tada odgovarajući kompletan i dosljedan algoritam dokazivanja (može se nazvati "dogmatski deduktivni") izgleda otprilike ovako:

“Prelistajte citate druga Mao Tse Tunga dok ne pronađete izjavu koju tražite. Ako se nađe, onda je tačno, a ako je citatnik gotov, a izjava nije pronađena, onda je lažna.

Ovdje nas spašava činjenica da je svaki citat očigledno konačan, pa će se proces "dokazivanja" neminovno završiti. Stoga je TGN neprimjenjiv na jezik dogmatskih izjava. Ali pričali smo o složenim jezicima, zar ne? objavljeno