Zanimljive činjenice i korisni savjeti. Pitanje postojanja Boga i Gödelova teorema

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 popularnoj interpretaciji, Ajnštajnova teorija, kao što je poznato, “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 čitatelju za razumijevanje sljedećeg „crta dokaza o TGN-u“ biti potrebno samo znanje školske matematike/informatike, vještine logičko razmišljanje 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 pokušavajući 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 dobro poznatim pravilima. Prijelaz iz 4. formule u 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 dokazivanja” (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 matematiku u školi, ponekad imamo pogrešan utisak da su fraze „teorema je istinita“ i „teorema se može dokazati ili verificirati“ gotovo potpuno identične. 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 s 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 poznatim 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). 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 koristeći beskonačan niz, 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.

Za daljnje svrhe, opisat ćemo „jezik formalne aritmetike“. Razmotrimo klasu tekstualnih linija konačne dužine koja se sastoji od arapski brojevi, varijable (slova latinice) koje uzimaju prirodne vrijednosti, razmake, znakove aritmetičkih operacija, jednakost i nejednakost, kvantifikatore („postoji“) i („za bilo koje“) i, možda, neke druge simbole (njihov tačan broj i sastav nam je nebitan). 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. Sada nazovimo "formulu sa slobodnim parametrom" (FSP) nizom koji postaje izraz ako ga zamijenimo kao ovaj parametar 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 važno kojim će se pismom redoslijediti). Dakle, bilo koji FSP odgovara svom broju na 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, 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 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 formalna aritmetika, ali nije teško razumjeti 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 je sadržana u citatniku druga Mao Zedonga, a netačna ako nije sadržana.”

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, pa ć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?

Ideja dokaza je da se konstruiše izraz koji bi ukazao na to

vlastitu nedokazivost. Ova konstrukcija se može izvesti u tri faze:

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

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 umjesto x određenog cijelog broja povezanog sa samim sobom, tj. zamjena svih ovim brojevima

Prva faza. Gedelizacija formalne aritmetike

Formalna aritmetika se može aritmetizirati (tj. Godelizirati) na sljedeći način: svaka njena teorema povezana je s određenim brojem. Međutim, pošto je svaki broj i teorema, onda se svaka teorema može smatrati, s jedne strane, teoremom formalne aritmetike, as druge, 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 ćemo konkretnije i detaljnije predstaviti dobijene rezultate.

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

Drugo, svaki niz simbola povezujemo s istim Gödelovim brojem koristeći neku funkciju kompozicije gdje predstavlja nizove simbola koji se formiraju

Treće (i ovo je bitno), svaki dokaz niza aksioma i pravila zamjene (ili pravila zamjene) povezan je s brojem gdje označava niz teorema korištenih u dokazu

Dakle, svaki dokaz u formalnoj aritmetici odgovara određenom broju – njegovom Gödelovom broju.

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

izračunavanja na skupu cijelih brojeva. Bilo koji izraz kao, na primjer, sljedeći: "dokazivo u formalnoj aritmetici" sada odgovara određeni broj, koje ćemo označiti kao

Hajde da formulišemo sledeću poziciju.

Formalna metaaritmetika sadržana je u skupu prirodnih brojeva, koji je i sam sadržan 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 nedvosmislen prijelaz iz A u, tj. dodjeljivanje dva različita broja dvama različitim dokazima. Na primjer, mogu se odabrati Gedelovi brojevi tako 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 znakova koji variraju od 1 do je zauzvrat kodirana nizom koji se sastoji od prvog primarni brojevi, odnosno broj

gdje je prost broj.

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

I obrnuto, zahvaljujući ovoj metodi konstruisanja brojeva, postaje moguće, počevši od određenog broja, razlaganjem na primarni faktori(zbog jedinstvenosti dekompozicije prirodnih brojeva na proizvode stepena prostih brojeva) vraćaju se u dva koraka na eksponente, odnosno na primitivne simbole formalne aritmetike. Naravno, ovo je uglavnom samo teoretski, jer brojevi brzo postaju preveliki

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:

Ovo proširenje znači da dokaz teoreme sadrži dvije faze: jednu koja odgovara broju 1981027125 253, a drugu broju 1981027125 211. Faktoringom svakog od ovih brojeva ponovo u proste faktore, dobijamo

Iz abecedne tablice kodiranja formalne aritmetike (tabela 3.2) nalazimo da naši Gedelovi brojevi za ova dva broja

će odgovarati sljedeći dokaz:

Iz formule slijedi formula

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. “Goedelizirana” 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ć sistematskog testa moguće utvrditi da li dati broj T dokaz neke teoreme Brojevi T u ovom slučaju formiraju par konjugiranih brojeva. Izraz i su konjugirani” Prezentativni unutar same aritmetizirane formalne aritmetike. To znači da postoji Gödelov broj koji digitalno izražava 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 zamijeniti neki termin. Konkretno, možete zamijeniti izraz A samim izrazom A. U ovom slučaju, broj-izraz A istovremeno obavlja dvije različite uloge (pogledajte konstrukciju iznad

Cantor i Richard): to je i pravi izraz za zamjenu i rezultirajući termin. Ovu specijalnu supstituciju ćemo označiti sa Dakle formula znači da je broj Gedelov broj dobijen izvođenjem zamene - u izraz 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 digitalnom obliku. Neka je E njegov Gedelov 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. Dajemo tumačenja 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 ista transformacija kao i ostali, on je reprezentativan u terminima i u njihovim kodnim oznakama - Gödelovi brojevi i, prema tome, takav broj postoji. Onda možda T broj 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 on sam po sebi nije teorema. Ovo dovodi do trećeg tumačenja.

Treće tumačenje. Izraz za koji je Gödelov broj -supstitucija E nije teorema aritmetizirane formalne aritmetike. Ali tu leži kontradikcija, jer je po konstrukciji to upravo -zamjena E, a broj po konstrukciji nije ništa drugo do sam broj E. Odavde slijedi konačna interpretacija e.

Dugo me zanima šta je senzacionalna Gödelova teorema. I koliko je to korisno za život. I konačno sam to mogao shvatiti.

Najpopularnija formulacija teoreme zvuči ovako:
"Svaki sistem matematičkih aksioma, počevši od određenog nivoa složenosti, je ili interno kontradiktoran ili nepotpun."

Ja bih to preveo na ljudski nematematički jezik na sljedeći način (aksiom je početna pozicija teorije, prihvaćena kao istinita u okviru ove teorije bez zahtjeva za dokazivanjem i korištena kao osnova za dokaz drugih njenih odredbi) . U životu, aksiom su principi koje slijede osoba, društvo, naučni pravac i države. Predstavnici religije aksiome nazivaju dogmama. Shodno tome, bilo koji naš princip, bilo koji sistem pogleda, počevši od određenog nivoa, postaje interno kontradiktoran ili nepotpun. Da biste se uvjerili u istinitost određene izjave, morat ćete izaći iz okvira ovog sistema vjerovanja i izgraditi novi. Ali će takođe biti nesavršen. Odnosno, PROCES SPOZNAVANJA JE BESKRAJAN. Svijet se ne može u potpunosti razumjeti dok ne dođemo do izvornog izvora.

"...ako sposobnost logičkog rasuđivanja smatramo glavnom karakteristikom ljudskog uma, ili barem njegovim glavnim oruđem, onda Gedelova teorema direktno ukazuje na ograničene mogućnosti našeg mozga. Složite se da je čovjeku vrlo teško odgojen da vjeruje u beskonačnu moć misli tezu o granicama njene moći... Mnogi stručnjaci smatraju da formalno-računarski, “aristotelovski” procesi koji su u osnovi logičkog mišljenja čine samo dio ljudske svijesti, dok druga oblast on je, u osnovi „ne-kompjuterski“, odgovoran za takve manifestacije kao što su intuicija, kreativni uvidi i razumevanje. otišao je još dalje. On je sugerisao postojanje nekih kvantnih efekata ne-računarske prirode koji obezbeđuju sprovođenje kreativnih činova svesti. nemoguće je stvoriti umjetnu inteligenciju zasnovanu na modernim računarskim uređajima, čak i ako pojava kvantnih kompjutera dovede do velikog proboja u oblasti računarstva. Činjenica je da bilo koji kompjuter može samo sve detaljnije modelirati rad formalno-logičke, "računarske" aktivnosti ljudske svijesti, ali su mu "neračunarske" sposobnosti intelekta nedostupne.

Jedna od važnih posljedica Gödelove teoreme je zaključak da se ne može razmišljati u ekstremima. U okviru postojeće teorije uvijek će postojati izjava koja se ne može ni dokazati ni opovrgnuti. Ili, drugim riječima, za neku izjavu uvijek će se naći par koji je opovrgava.

Sledeći zaključak. Dobro i zlo su samo dvije strane istog novčića, bez kojih ne može postojati. A dolazi iz principa da u Univerzumu postoji samo jedan izvor svega: dobra i zla, ljubavi i mržnje, života i smrti.

Svaka izjava o kompletnosti sistema je lažna. Ne možete se osloniti na dogme, jer će one prije ili kasnije biti opovrgnute.

U tom smislu, moderne religije su u kritičnoj situaciji: crkvene dogme opiru se razvoju naših ideja o svijetu. Pokušavaju sve stisnuti u okvire krutih koncepata. Ali to dovodi do činjenice da iz monoteizma, iz jedinstvenog izvora svih prirodnih procesa, prelaze u paganizam, gdje postoje sile dobra i sile zla, postoji bog dobra negdje daleko u nebesima, i postoji đavo (bog zla), koji je odavno položio svoju šapu na sve što je na Zemlji. Ovakav pristup dovodi do podjele svih ljudi na prijatelje i neprijatelje, na pravednike i grešnike, na vjernike i jeretike, na prijatelje i neprijatelje.

Evo još jednog kratkog teksta koji popularno otkriva suštinu koja proizlazi iz Gödelove teoreme:
„Čini mi se da ova teorema nosi važnu filozofsko značenje. Postoje samo dvije opcije:

a) Teorija je nepotpuna, tj. u smislu teorije, moguće je formulisati pitanje na koje se iz aksioma/postulata teorije ne može izvesti ni pozitivan ni negativan odgovor. Štaviše, odgovori na sva ovakva pitanja mogu se dati u okviru jedne sveobuhvatnije teorije, u kojoj će stara biti poseban slučaj. Ali ovaj nova teorija imaće svoja „pitanja bez odgovora“ i tako dalje do beskonačnosti.

b) Potpuna, ali kontradiktorna. Na bilo koje pitanje se može odgovoriti, ali na neka se može odgovoriti i pozitivno i negativno u isto vrijeme.

Naučne teorije pripadaju prvom tipu. Oni su dosljedni, ali to znači da ne pokrivaju sve. Ne može biti "finala" naučna teorija. Svaka teorija je nekompletna i ne opisuje nešto, čak i ako još ne znamo šta tačno. Može se samo stvarati sve obuhvatnije teorije. Za mene lično, ovo je razlog za optimizam, jer to znači da kretanje nauke napred nikada neće stati.

"Svemogući Bog" pripada drugoj vrsti. Svemogući Bog je odgovor na svako pitanje. A to automatski znači da vodi u logički apsurd. Paradoksi kao što je "ogroman kamen" mogu se izmisliti u serijama.

Općenito, naučno znanje je tačno (konzistentno), ali ne opisuje sve u bilo kojem trenutku. Istovremeno, ništa nas ne sprečava da pomeramo granice poznatog u beskonačnost, i pre ili kasnije, svako nepoznato postaje poznato. Religija tvrdi da jeste Puni opis svijet "trenutno", ali u isto vrijeme automatski netačan (apsurdan)."

Jedno vrijeme, kada sam tek počinjao svoj odrasli život, bavio sam se programiranjem. I postojao je takav princip: ako se napravi mnogo ispravki u programu, mora se ponovo napisati. Ovaj princip, po mom mišljenju, odgovara Gödelovoj teoremi. Ako program postane složeniji, postaje nedosljedan. I neće raditi kako treba.

Još jedan primjer iz života. Živimo u eri kada zvaničnici izjavljuju da glavni princip postojanja treba da bude zakon. Odnosno, pravni sistem. Ali čim zakonodavstvo počne da postaje složenije i donošenje pravila počne da cveta, zakoni počinju da su u suprotnosti jedni s drugima. To je ono što sada vidimo. Nikada nije moguće stvoriti pravni sistem koji bi regulisao sve aspekte života. A s druge strane, bilo bi fer za sve. Zato što će ograničenja našeg razumijevanja svijeta uvijek izaći na vidjelo. I ljudski zakoni će u jednom trenutku početi da se sukobljavaju sa zakonima Univerzuma. Mnoge stvari razumijemo intuitivno. Takođe moramo intuitivno suditi o postupcima drugih ljudi. Dovoljno je da država ima ustav. I na osnovu članova ovog ustava urediti odnose u društvu. Ali prije ili kasnije, ustav će se morati promijeniti.

Jedinstveni državni ispit je još jedan primjer pogrešnosti naših ideja o ljudskim sposobnostima. Pokušavamo testirati računske sposobnosti mozga na ispitu. Ali intuitivne sposobnosti više se nisu razvijale u školi. Ali osoba nije biorobot. Nemoguće je stvoriti sistem bodovanja koji bi mogao da identifikuje sve mogućnosti koje su inherentne čoveku, njegovoj svesti, njegovoj podsvesti i njegovoj psihi.

Prije skoro 100 godina, Gödel je napravio nevjerovatne korake u razumijevanju zakona univerzuma. Ali još uvijek nismo bili u mogućnosti to iskoristiti, smatrajući ovu teoremu visokospecijaliziranim matematičkim problemom za uski krug ljudi koji se bave nekim apstraktnim temama u svom krugu. Zajedno s kvantnom teorijom i Kristovim učenjem, Gödelov teorem nam omogućava da se izvučemo iz zatočeništva lažnih dogmi, da prevladamo krizu koja još uvijek postoji u našem svjetonazoru. A vremena ostaje sve manje.

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 nesvodljivu i neoborivu formulu.

Druga teorema kaže da ako je formalna aritmetika konzistentna, onda ona sadrži određenu formulu koja smisleno potvrđuje konzistentnost ove teorije.

Gödelov prvi teorem o nepotpunosti

Izjava 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 se ni G ni njegova negacija ¬G ne mogu izvesti u S .

Prilikom dokazivanja teoreme, Gödel je konstruirao formulu G eksplicitno, ponekad se naziva i Gödelova neodlučiva formula. U standardnom tumačenju, rečenica G potvrđuje sopstvenu nesvodljivost u S. Prema tome, prema Gödelovom teoremu, ako je teorija S konzistentna, onda je ova formula zaista nesvodiva 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 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ödelian neodluč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 izlazni broj formule sa brojem m Ovakvo poređenje formula i prirodnih brojeva naziva se aritmetizacija matematike i prvi put je izveo Gödel. Ova ideja je kasnije postala ključ za rješavanje mnogih važnih problema matematičke logike.

Skica dokaza

Hajde da popravimo neki formalni PM sistem u kojem se mogu predstaviti elementarni matematički koncepti.

Izrazi formalnog sistema su, posmatrano 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 više od konačnih nizova formula (sa strogo definisanim svojstvima). Za matematičko razmatranje, nije važno koje objekte uzimamo kao primitivne simbole i odlučujemo se za korištenje prirodnih brojeva u ove svrhe. Prema tome, formula je konačan niz prirodnih brojeva, zaključak 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 moguće je vratiti npr. formulu F(v) u PM sa jednom slobodnom varijablom v(čija je vrsta numerički niz) takav da F(v), u intuitivnom tumačenju, znači: v- izvedena formula. Sada konstruirajmo neodlučivu rečenicu PM sistema, odnosno rečenicu A, za koje ni jedno ni drugo A, niti ne-A neizvodljivo, 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 uredimo izraze klase u niz na neki način, označimo n-e kroz R(n), i napominjemo da je koncept "klasa-izraz", kao i odnos narudžbe R može se odrediti u PM sistemu. Neka je α proizvoljan izraz klase; 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- izvedena formula). Budući da se svi koncepti koji se nalaze u ovoj definiciji mogu izraziti u PM, isto vrijedi i za koncept K, koji je konstruisan od njih, odnosno postoji takva klasa izraza S, da je formula [ S;n], intuitivno protumačeno, znači da je prirodan broj n pripada K. Kao klasa izraza, S identično nekim specifičnim R(q) u našoj numeraciji, tj

S = R(q)

važi za neki određeni prirodni broj q. Sada ćemo pokazati da rečenica [ R(q);q] 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 u skladu sa (*), ¬Bew[ R(q);q] će biti izvršena, što je u suprotnosti s našom pretpostavkom. S druge strane, ako je negacija [ R(q);q] se moglo zaključiti, onda ¬ n ∈ K, odnosno Bew[ R(q);q] će biti istina. Dakle, [ R(q);q] zajedno sa svojom negacijom biće deducibilno, što je opet nemoguće.

Polinomski oblik

Za svaku konzistentnu teoriju T može se specificirati cjelobrojna vrijednost parametra K tako 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 nesvodljivu formulu koja smisleno potvrđuje konzistentnost S .

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

Skica dokaza

Prvo se gradi formula Con, što smisleno izražava 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. Sva razmišljanja za dokazivanje prve teoreme mogu se izraziti i provesti pomoću S, to jest, formula je deducibilna u S Con ⊃ G. Dakle, ako je u S izvodljivo Con, onda je odvodljivo i G. Međutim, prema Gödelovom prvom teoremu, ako je S konzistentan, onda G nije izvodljivo u njemu. Prema tome, ako je S konzistentan, onda je i formula u njemu nesvodiva Con.

Bilješke

vidi takođe

Linkovi

V. A. Uspensky Gedelov teorem o nepotpunosti. - M.: Nauka, 1982. - 110 str. - (Popularna predavanja iz matematike).
akademik Yu. L. Ershov "Dokaz iz matematike", A. Gordon program od 16. juna 2003
A. B. Sosinsky Gödelov teorem // ljetna škola"Moderna matematika". - Dubna: 2006.
P. J. Cohen Na temeljima teorije skupova // Napredak u matematičkim naukama. - 1974. - T. 29. - br. 5 (179). - str. 169–176.
M. Kordonsky Kraj istine. - ISBN 5-946448-001-04
V. A. Uspensky Gödelov teorem o nepotpunosti i četiri puta koji vode do nje // Ljetnja škola "Savremena matematika". - Dubna: 2007.
Zenkin A. A. Princip vremenske podjele i analiza jedne klase kvazi-konačnih vjerodostojnih razmišljanja (na primjeru G. Cantorove teoreme o nebrojivosti) // DAN. - 1997. - T. 356. - Br. 6. - P. 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-seminara po imenu akademika E.V. Zolotova. - Habarovsk, Rusija: 2009. - P. 60-61.

Wikimedia Foundation. 2010.

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

Ovaj izraz ima druga značenja, vidi Gedelovu teoremu. Gödelova teorema o nepotpunosti i Gödelova druga teorema [1] 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 termin ima druga značenja, vidi Gedelovu teoremu. Gedelova teorema o potpunosti predikatskog računa jedna je od temeljnih teorema matematičke logike: uspostavlja nedvosmislenu vezu između logičke istine... ... Wikipedia

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

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 u dovoljno složenim jezicima postoje nedokazive izjave. Ali u ovoj frazi gotovo svaka riječ treba objašnjenje.

Za 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.