Posljednja Gödelova teorema. Ispovest velikog logičara

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, in 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 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 poznata pravila. 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.

Da bismo nastavili dalje, trebat će nam 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 u primjeni 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"), što je 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 tvrdnja.

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 svaka teorija sadrži probleme koji se ne mogu riješiti unutar 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 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.

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. Sada nazovimo "formulu sa slobodnim parametrom" (FSP) stringom koji postaje izjava 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, 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 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, 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?

Oznake: Dodaj oznake

Ekologija života. Nauka i otkriće: Gedelova teorema o nepotpunosti, jedna od najpoznatijih teorema matematičke logike, 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 matematičke logike, 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. S druge strane, u popularnoj 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».

I tako neki pokušavaju da to prilagode kao argument protiv psovki 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 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.

Da malo pojednostavim, TGN tvrdi da u dovoljno složenim jezicima 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, pretpostavimo da trebate dokazati ispravnost sljedeće jednostavne formule: “∀x(x−1)(x−2)−2=x(x−3)” (da vas podsjetim da se simbol ∀ čita “za bilo koji” i naziva se “univerzalni kvantifikator”). To možete 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 - 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. Neka imamo skup koji se sastoji od nizova znakova neke abecede, a postoje pravila po kojima iz tih nizova možemo odabrati podskup S 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 funkcije P od >S do B - "jezik izjava". Imajte na umu da je u svakodnevnom smislu pojam jezika nešto širi. Na primjer, ruski izraz " Dođi ovamo!„nije ni istinit ni lažan, odnosno, sa stanovišta matematičke logike, 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 početne podatke u rezultat.

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 P postoji “algoritam za dokazivanje” (ili, ukratko, “ deduktivan"), što je ekvivalentno ovoj funkciji, odnosno pretvaranje svake izjave u potpuno istu Booleovu vrijednost kao i ona? Isto pitanje se može sažetije formulirati: Da li je svaka funkcija preko skupa iskaza izračunljiva?

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 svaka tačna izjava dokazati.

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 X je istinita“ i „Teorema X može se 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. Prisjetimo se, na primjer, čuvenog Velikog Fermatova teorema:

Nema takvih prirodni x,y,z i n>2, 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 Mora se razlikovati između istinitosti izjave i njene dokazivosti. 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, nailazite 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 to odbitak će ostati nepotpun. 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 da je dedukcija kontradiktorna. Dakle, druga formulacija TGN-a zvuči ovako: “ Postoje propozicioni jezici za koje je nemoguć potpuni konzistentan deduktivni proces.“ – otuda i naziv teoreme.

Ponekad se naziva "Gödelov teorem", izjava je da svaka teorija sadrži probleme koji se ne mogu riješiti unutar 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).

Kurt Gödel

Svaki školarac zna da, recimo, u slučaju sin⁡x funkcije, morate imati veliku sreću s argumentom kako bi se proces izračunavanja tač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 ovaj proračun nikada neće dovesti do tačnog rezultata, iako se može približiti koliko god želite - jednostavno zato što je sinusna vrijednost 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 imaju potpuno drugačiju strukturu.

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“) a možda i neki drugi simboli (njihov tačan broj i sastav za nas su nebitni).

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 sa stanovišta 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 izjava ako se u njega kao ovaj parametar unese prirodni broj. Primjeri FSP-a (sa parametrom x):

x=0

2×2=x

∃yx+y>x

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

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

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 A, koji dodeljuje Booleovu vrednost prirodnom broju k na sledeći način:

1. Pronađite kth formula na listi F.

2. Zamijenite broj k u njega kao argument.

3. Primjenjujemo naš algoritam dokazivanja na rezultirajuću izjavu (prema našoj pretpostavci, ona postoji), što je prevodi u TAČNO ili LAŽNO.

4. Primijenite logičku negaciju na dobiveni rezultat.

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, pod pretpostavkom gore napravljenom, bilo koji FSP iz F može biti povezan sa algoritmom koji sadrži prirodni broj na ulazu i Booleovu vrijednost na izlazu.

Obrnuto je manje očigledno:

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

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 A. Prema lemi u koju sam vas zamolio da vjerujete, postoji ekvivalentni FSP. Ima neki broj na listi F - recimo, n. Zapitajmo se šta je Fn(n)? Neka ovo bude ISTINA. Zatim, prema konstrukciji algoritma A (a samim tim i ekvivalentne funkcije Fn), to znači da je rezultat zamjene broja n u funkciju Fn FALSE.

Obrnuto se provjerava na isti način: iz Fn(n)=FALSE slijedi da je Fn(n)=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 Epimenida, 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 njegove izjave (poznatoj kao "paradoks lažova") može se formulisati na sljedeći način: “ Ležim" 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. 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 nisu ni svi brojevi . 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:

“Svaka fraza na kineskom jeziku je istinita 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? objavljeno

Uspensky V.A.

Gödelov teorem o nepotpunosti.1994.

Theoretical Computer Science 130, 1994, str.273-238.

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 je

direktna posledica rezultata koji je Tarski dobio kombinovanjem

Gedelova teorema neodlučnosti s njegovom vlastitom teorijom istine, prema

za koje ne može postojati univerzalni kriterijum istine čak ni za relativno

usko polje teorije brojeva, pa samim tim i za svaku nauku koja koristi

aritmetika. Naravno, ovaj rezultat se a fortiori primjenjuje na koncept istine

u bilo kojoj nematematičkoj oblasti znanja u kojoj je široko rasprostranjena

koristi se aritmetika.

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.

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 - cijeli brojevi u decimalnom zapisu su 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čne velika slova. 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 izjava" (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 su izrazi 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 izraz "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šati dati precizna definicija ovaj istovremeno “naivan” i “apsolutni” koncept dokaza, ili – što je ekvivalentno – definirati odgovarajući podskup od P?. Umjesto toga, razmotrit ćemo formalni analog ovog nejasnog koncepta, za koji ćemo u budućnosti i dalje koristiti termin „dokaz“. Ovaj analogni ima dva vrlo važne karakteristike, što ga razlikuje 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? . Zatim ćemo zahtijevati da za svaki takav koncept dokaza postoji efikasan metod, 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.

Trostruki zadovoljavajući uvjeti (1)-(3) naziva se deduktivni sistem nad alfabetom 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 postojanje se zahtijeva u dijelu 1.3.2. definicije se lako mogu konstruisati kada precizno definišemo bilo koju od njih prihvaćene vrijednosti riječ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 nad L, uvijek postoji riječ u T koja nema dokaza.” Ova opcija još uvijek izgleda nejasno. Konkretno, lako bismo mogli smisliti onoliko deduktivnih sistema koliko želimo koji imaju vrlo malo riječi koje se mogu dokazati. Na primjer, u praznom deduktivnom sistemu (gdje je P = ?) uopće ne postoje riječ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 (kroz koji 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 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 potpun 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, ne postoji deduktivni sistem nad L koji je i potpun i relativno konzistentan.

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 se tvrdnja A može dokazati, onda se izjava ne-A može dokazati.”

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 drugog Hilbertovog problema, ako je sistem aksioma potpun (to jest, bilo koja izjava u njemu se može dokazati), onda je kontradiktoran.

Jedini izlaz iz ove situacije je prihvatanje nekompletan sistem aksiom. Odnosno, morate se pomiriti sa činjenicom da u kontekstu bilo kojeg logički sistem ostat će nam izjave tipa A, za koje se zna da su istinite ili netačne - i možemo samo suditi o njihovoj istinitosti vani okvir aksiomatike koju smo usvojili. Ako takvih tvrdnji nema, onda je naša aksiomatika kontradiktorna, au njenom okviru će se neminovno 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 razumjeti punu dubinu istine sadržane u Gödelovim 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 kao 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 prošao 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 izdržala i on je umro psihijatrijsku kliniku od gladi, odbijajući da jede, jer je bio ubeđen da nameravaju da ga otruju.

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 onih jednostavnih problema čiji se odgovor čini očiglednim dok ne zakopate malo dublje. U modernim terminima, ovo je bilo pitanje: da li je matematika sama sebi dovoljna? Hilbertov drugi zadatak se svodio na potrebu da se striktno dokaže da je sistem aksioma - osnovnih tvrdnji prihvaćenih u matematici kao osnova bez dokaza - savršen i potpun, odnosno da 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. U standardnoj euklidskoj planimetriji (geometrija na ravni) može se bez sumnje dokazati da je tvrdnja „zbir uglova trougla 180°“ tačna, a tvrdnja „zbir uglova trougla je 137 °” je netačan. 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 je 1931. neki bečki matematičar Kurt Gödel s naočarima objavio kratak članak koji je jednostavno uznemirio cijeli 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 zadivljujuće svojstvo bilo kojeg sistema aksioma:

“Ako se tvrdnja A može dokazati, onda se izjava ne-A može dokazati.”

Drugim riječima, ako se može dokazati istinitost tvrdnje „pretpostavka 247 je nedokaziva“, onda se može dokazati i istinitost tvrdnje „pretpostavka 247 je dokaziva“. 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 nekompletnog sistema aksioma. 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 netačni - a o njihovoj istinitosti možemo suditi samo izvan okvira aksiomatike koju imamo. prihvaćeno. Ako takvih tvrdnji nema, onda je naša aksiomatika kontradiktorna, au njenom okviru će se neminovno naći formulacije koje se mogu i dokazati i opovrgnuti.

Dakle, formulacija Gödelove prve, ili slabe, teoreme o nepotpunosti: “Svaki formalni sistem aksioma sadrži neriješene pretpostavke.” Ali Gödel se tu nije zaustavio, formulirajuć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 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 razumjeti punu dubinu istine sadržane u Gödelovim teoremama, ali kompjuterski mozak nikada ne može. Stoga je ljudski mozak sve samo ne kompjuter. On je sposoban da donosi odluke i položiće Turingov test.

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

Kurt GÖDEL
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 izdržala, te je umro na psihijatrijskoj klinici od gladi, odbijajući da jede, jer je bio uvjeren da će ga otrovati.

Kako se naučni model razvija u prirodne nauke? Svakodnevne stvari se nakupljaju ili naučno iskustvo, njegove prekretnice su uredno formulisane u obliku postulata i čine osnovu modela: skup izjava koje prihvataju svi koji rade u okviru ovog modela.

Anatoly Wasserman

Kurt Gödel je 1930. godine dokazao dvije teoreme koje, prevedene sa matematičkog jezika na ljudski jezik, znače otprilike sljedeće: Svaki sistem aksioma dovoljno bogat da se koristi za definiranje aritmetike bit će ili nepotpun ili kontradiktoran. Ne kompletan sistem- to znači da je u sistemu moguće formulisati tvrdnju koja se ne može ni dokazati ni opovrgnuti pomoću ovog sistema. Ali Bog je, po definiciji, konačni uzrok svih uzroka. Sa stanovišta matematike, to znači da uvođenje aksioma o Bogu čini kompletnom našu cjelokupnu aksiomatiku. Ako postoji Bog, onda se svaka izjava može ili dokazati ili opovrgnuti, upućujući, na ovaj ili onaj način, na Boga. Ali prema Gedelu, kompletan sistem aksioma je neizbežno kontradiktoran. To jest, ako vjerujemo da Bog postoji, onda smo prisiljeni doći do zaključka da su kontradikcije moguće u prirodi. A kako nema kontradiktornosti, inače bi se cijeli naš svijet raspao od tih suprotnosti, moramo doći do zaključka da je postojanje Boga nespojivo sa postojanjem prirode.

Sosinsky A. B.

Gödelov teorem, zajedno s otkrićima relativnosti, kvantne mehanike i DNK, općenito se smatra najvećim naučno dostignuće XX vijek. Zašto? Šta je njegova suština? Kakav je njen značaj? O ovim pitanjima se bavi u svom predavanju u okviru projekta „Javna predavanja „Polit.ru““ Aleksej Bronislavovič Sosinski, matematičar, profesor na Nezavisnom moskovskom univerzitetu, oficir Ordena akademskih palmi Francuske Republike, laureat Nagrada Vlade Rusije u oblasti obrazovanja 2012. Konkretno, dato je nekoliko različitih njegovih formulacija, opisana su tri pristupa njegovom dokazivanju (Kolmogorov, Chaitin i sam Gödel), a objašnjen je i njegov značaj za matematiku, fiziku, informatiku i filozofiju.

Uspensky V. A.

Predavanje je posvećeno sintaksičkoj verziji Gödelove teoreme o nepotpunosti. Sam Gödel je dokazao sintaksičku verziju koristeći jaču pretpostavku od konzistentnosti, odnosno takozvanu omega konzistentnost.

Uspensky V. A.

Predavanja u ljetnoj školi „Moderna matematika“, Dubna.