Gödelov dokaz

Od (gotovo drevnog) pojavka ideje aksiomatskih („formalnih“) sustava – sustava dokazivanja koji kreću od jednostavnih i očitih tvrdnji te unaprijed definiranim pravilima izvode složenije tvrdnje – postojala je prešutna pretpostavka među matematičarima koja glasi „dokazivo je sinonim za istinito“. Ako možemo unutar nekog opće-prihvaćenog sustava dokazati primjerice Pitagorin poučak (a možemo), onda je on istinit. Taj poučak je istinit, čini se, upravo stoga što je dokaziv. Pitanje je – vrijedi li doista identitet istinitosti i dokazivosti?

Osim matematičke važnosti tog problema, odgovor na to pitanje tijesno je vezan uz naše (filozofijsko) poimanje matematike. Primjerice, ako je ono što zovemo matematičkim istinama odraz platoničke matematičke realnosti (Kurt Gödel, koji je prvi razjasnio neke dvojbe oko spomenutog identiteta,  je inače i sam bio zagriženi platonist) koja sadrži vrlo veliku ili beskonačnu količinu međusobno neovisnih istina, tj. istina koje su međusobno nepovezane bilo kakvom logikom koja bi omogućavala dokazivanje s jedne istine na drugu, onda identitet ne mora vrijediti (osim možda na „kratke staze“). No, mnogi matematiku promatraju upravo kao sinonim za neku vrstu znakovne slagalice, gdje su osnovni znakovi matematičke formule, te se slaganjem (koje je analogija dokazivanju) dolazi do novih istina. Aksiomatizirana matematika prema tom slagalačkom poimanju nije samo lijepa i uredna, već je to i prava matematika. Pokazat će se da je slagalačka slika naravi matematike pogrešna ili barem vjerojatno pogrešna.

Ako identitet dokazivog i istinitog vrijedi, kaže se da je sustav potpun. U potpunom sustavu vrijedi da se sve što se (unutar njega) uopće može izraziti, u tom istom sustavu mora moći dokazati ili kao istinito ili kao neistinito. Još se kaže: svaki je iskaz u sustavu odluč(lj)iv.

Najobuhvatniji dosad postavljeni  formalni sustavi [aritmetike] jesu sustav u Principia Mathematica, s jedne strane, i Zermelo-Fraenkelov sustav aksioma za teoriju skupova … Oba ta sustava su takva da su u njima formalizirane sve metode dokazivanja koje se danas upotrebljavaju u matematici, tj. one su tamo svedene na svega nekoliko aksioma i pravila zaključivanja. Stoga se može naslućivati da su ti aksiomi i pravila zaključivanja i dovoljni  za to da bi se sva matematička pitanja koja se uopće daju formalno izraziti u dotičnim sustavima bila također i odlučiva. U onom što slijedi pokazat ću da to nije slučaj. [Gödel, str. 89.]

Osim što je šokirao javnost (barem onu logičko-filozofsku) zaključcima koji su uslijedili, Gödelov dokaz osobit je po svojoj formi odnosno metodi kojom se služio.

Jedna od ključnih ideja iza Gödelova dokaza je razlikovanje matematike i metamatematike. Općenito, tvrdnja o (ne)identitetu dokazivosti i istinitosti metamatematičke je prirode. Ona ne govori (barem ne neposredno) o odnosima između brojeva ili drugih matematičkih objekata. Ona govori nešto o odnosima između samih matematičkih odnosa; ili jednostavnije, o matematici.

… Moramo primijetiti da takvi izrazi sa značenjem o matematičkom sustavu bez značenja (odnosno formaliziranom) očito ne pripadaju tome sustavu. Oni pripadaju onome što je Hilbert nazvao „metamatematikom“. (…)

Razmotrimo izraz

2 + 3 = 5

Taj izraz pripada matematici (aritmetici) i u potpunosti je izgrađen iz elementarnih aritmetičkih znakova. S druge strane, iskaz

                ‘2 + 3 = 5’ je aritmetička formula.

tvrdi nešto o prikazanom izrazu. Taj iskaz ne izražava neku aritmetičku činjenicu i ne pripada formaliziranom jeziku aritmetike. (…)

Napokon, sljedeći iskaz također pripada metamatematici:

Aritmetika je konzistentna.

[Nagel, str. 24.]

Gödel je metamatematiku zrcalio u matematici. Naime, pronašao je način da svaku metamatematičku tvrdnju prikaže kao neku matematičku tvrdnju, dakle kao neki odnos između brojeva, gdje su brojevi igrali ulogu matematičkih tvrdnji, a odnosi između brojeva odnose između matematičkih tvrdnji (ili, odnose između odnosa između brojeva).

Gödel je je najprije pokazao da je svakom elementarnom znaku, svakoj formuli (nizu znakova) i svakom dokazu (konačnom nizu formula) moguće pridružiti jedinstveni broj. Taj broj, koji služi kao razlikovna oznaka, naziva se „Gödelov broj“ znaka, formule ili dokaza. [Nagel, str. 54.]

Postupak pridruživanja Gödelovih brojeva formula često se naziva „aritmetizacijom“ aritmetike. Korisno je, zbog bolje predodžbe o sadržaju Gödelova dokaza, dati jedan primjer takvog pridruživanja (inače je više mogućih pridruživanja). Prije toga, što se sve podrazumijeva kao elementarni znak:

1. Bilo koji skup znakova koji je (uz dodatak odgovarajućih znakova za varijable) sposoban izraziti bilo koju aritmetičku istinu – npr. „4 je veći od 3“ i „ne postoji najveći prost broj“. Jedan takav moguć skup osnovnih znakova je {0, s, ¬, ∨, ∀, (, )} (znakovi varijable će biti naknadno dodani). Brojevi se kodiraju kombinacijom znakova „s“ i „0“: „0“ za 0, „s0“ za 1, „ss0“ za 2 itd.
   Sljedeća 3 znaka u danom skupu znakova su logički operatori koji govore o istinitosti jedne tvrdnje, ili odnosu istinitosti više tvrdnji (npr. „¬X“ je u značenju „X je neistinito“).
   Zagrade imaju uobičajenu ulogu određivanja slijeda operacija.
2. Uz te znakove, koriste se još i znakovi za varijable. x₁, y₁, z₁… za varijable prvog tipa (varijable koje se javljaju u uobičajenim aritmetičkim jednadžbama i predstavljaju brojeve). Zatim x₂, y₂, z₂… za varijable drugog tipa (tj. „rečenične“ varijable, npr. x₂ može stajati za cijelu formulu „s0 + s0 = ss0“). Na isti način se mogu imenovati i varijable viših tipova (koje će sadržavati odnose između odnosa između brojeva itd.)
3. Neki drugi često korišteni znakovi (=, +, * itd.) se mogu, a i ne moraju, ubaciti u taj skup, jer su svi ionako izvodljivi iz skupa koji je već dan. Znak jednakosti koji se koristi za odnos jednakosti između brojeva se može definirati na ovaj način: (x₁ = y₁) =_def ∀x₂(¬(¬x₂ (x₁) ∨ ¬x₂ (y₁)) ∨ ¬(x₂ (y₁) ∨ x₂ (x₁)))). Ova nečitljiva formula ustvari kaže: ako svako brojevno svojstvo koje vrijedi o x₁ također vrijedi i o y₁, i obratno, onda su x₁ i y₁ jedno te isto.

Gödel je, dakle, svim tim znakovima pridružio određen broj („Gödelov broj“). Prvom dijelu elementarnih znakova su redom pridruženi brojevi 1, 3, 5, 7, 9, 11, 13. Drugom dijelu (varijablama) su pridruženi brojevi pⁿ, gdje je p prost broj veći od 13, a n tip varijable (n = 1 za brojeve, n = 2 za formule itd.). Vrlo je lako za svaki takav (Gödelov) broj otkriti koju varijablu predstavlja. Npr. 225 = 15². Radi se dakle o varijabli (jer se 225 može zapisati u obliku potencije kojoj je baza prost broj) drugog tipa (jer je eksponent broj 2); možemo ju zapisati kao y₂. Iako je abeceda u stvarnosti ograničena, pretpostavlja se da je beskonačna, tako da primjerice i prost broj 6461333093 predstavlja neku varijablu prvog tipa, iako ne postoji njen abecedni prijevod.

Time je moguće „aritmetizirati“ svaku aritmetičku formulu – pretvoriti ju u skup brojeva. Štoviše, moguće je i taj skup vrlo lako predstaviti kao jedan broj:

[u ovom primjeru u osnovne znakove je ubačen i znak jednakosti te mu je pridružen G. broj 5, a znaku ‘0’ je pridružen G. broj 6]

Aritmetička formula ‘nula je jednako nula’ ima Gödelov broj 243 milijuna. Čitamo li je prema dolje od A do E, ilustracija pokazuje kako se broj prevodi u izraz koji predstavlja. Čitamo li je prema gore, ona pokazuje kako se izvodi Gödelov broj za formulu.

A                      243 000 000

B                      64 * 243 * 15 625

C                      2⁶ * 3⁵ * 5⁶

D                      6      5      6

↓      ↓      ↓

0      =     0

E                             0 = 0

[Nagel, str. 58.]

Na potpuno jednak način moguće je kodirati nizove formula – npr. matematičke dokaze (svaki dokaz je ustvari niz formula).

Gödel je izgradio iskaz G (nazovimo ga tako), koji, metamatematički čitan, govori o sebi da je nedokažljiv i koji je u sustavu P neodlučljiv … Neodlučljiv je, pokazuje Gödel, i aritmetički stavak, nazovimo ga C, koji, metamatematički razumljen, kaže da je aritmetički sustav u kojem je C izgrađen (sustav P), suvisao. Nadalje, kako je G istinit, pokazuje se da je pojam aritmetičke istine nesvedljiv na pojam aritmetičke dokažljivosti.

Tamo gdje se očekivala najveća moguća egzaktnost (u aritmetici i matematičkoj logici), neočekivano se, i to na najprecizniji način, otvorio rascjep, kako u samome sustavu, tako i između istine i sustava. [Kovač, str. 33.]

Ono što Kovač naziva iskazima G i C ustvari su ključne formule u dokazu. Važnost iskaza C tehničkije je naravi, zanimljiv matematičarima više no filozofima. Taj dio Gödelovog dokaza ustvari je pokušaj rješavanja tzv. Hilbertovog drugog problema. Problem se sastojao u pronalaženju dokaza da je aritmetika konzistentna. Gödel je pokazao da je aritmetika ili protuslovna samoj sebi, ili dokaz konzistentnosti aritmetike ne postoji. To je isto što i reći: ako je aritmetika konzistentna, dokaz same te činjenice ne postoji. No, valja napomenuti da je Gödel dokazao „samo“ nepostojanje dokaza konzistentnosti aritmetike unutar izražajne moći aritmetike (njegov dokaz temelji se na zrcaljenju metamatematike u matematici, točnije u aritmetici). Time nije isključeno da postoji uvjerljiv dokaz (po Hilbertovim kriterijima pri postavljanju problema: u kojemu se ne koriste metode koje na ovaj ili onaj način barataju beskonačnim skupovima objekata) koji je iz nekog razloga nemoguće predstaviti jezikom aritmetike. Ipak: teško je zamisliti takav ne-aritmetički finitistički dokaz (teško je zamisliti već i kako bi bilo kakav dokaz takve vrste – „finitistički“ a ujedno nepredstavljiv u jeziku aritmetike – uopće trebao izgledati), i svaki dosadašnji pokušaj za stvaranjem takvog dokaza je propao. Stoga bi se za taj (2. po redu) Gödelov zaključak moglo reći da dokazuje kako vjerojatno ne postoji dokaz konzistentnosti aritmetike.

Iskaz G je donekle zanimljiviji (zbog svoje strukture i pomalo paradoksalne naravi) pa se obično samo o njemu i govori kad se govori o Gödelovom dokazu. Što dakle kaže iskaz G? Zanimljivo je da G sam po sebi i nije osobito koristan. G metamatematički kaže otprilike „Neizvodiv sam“ (što zvuči vrlo intrigantno, ali je nažalost nedovoljno opširno), dok je u matematičkom pogledu to posve nečitljiv zbir matematičko/logičkog znakovlja (kad bi se krenula ispisivati u svom „izvornom“ čisto-matematičkom obliku koji sadrži samo elementarne znakove, zauzela bi značajno veći prostor od onog što ga nude sve bilježnice na svijetu zajedno). G je stoga najzanimljivje promatrati u miješanom matematičko-metamatematičkom obliku. Gödel je na samom početku svog članka dao skicu dokaza u kojoj se javlja takav oblik (u nastavku taj dio nije izravno prepisan jer se u toj skici javljaju neki tehnički pojmovi koje se može izbjeći).

Posebnu vrstu aritmetičkih tvrdnji čine tvrdnje koje u sebi sadrže točno jednu slobodnu brojevnu nepoznanicu (sve brojevne nepoznanice za koje ima smisla uvrstiti neku vrijednost), i u kojima je ta nepoznanica prvog tipa (tj. obična varijabla koja mijenja broj). Primjer takve formule je „x = 5“, također i „x * x = x“ (i bilo koja druga jednadžba s jednom nepoznanicom, ali i ne samo one). Ovisno o vrijednosti nepoznanice, te formule mogu biti istinite ili neistinite. Npr. za x = 5, formula „x = 5“ će očito biti istinita, dok „x * x = x“ neće. Bez uvrštavanja, te formule su „otvorene“ i kako nemaju istinitosnu vrijednost, ne smatraju se iskazima.

Zamislimo sad da sve moguće formule s točno jednom slobodnom brojevnom nepoznanicom poredamo po nekom kriteriju. Npr. po broju osnovnih znakova koji koriste, a za one koje imaju jednak broj osnovnih znakova, po dogovorenoj abecedi. Na 1. mjestu bi se mogla naći primjerice formula „0 = x“. Oznakom R(n) označimo n-tu formulu u tom poretku. Označimo zatim sa [R(n), c] formulu koju dobijemo kad u formuli R(n) nepoznanicu zamijenimo s brojem c. Primjerice, ako je R(1) kao u gornjem primjeru formula „0 = x“, onda će [R(1), 5] dati formulu „0 = 5“. Ta formula je „zatvorena“ jer se u njoj ne javljaju slobodne nepoznanice, stoga je ona ili istinita ili neistinita.

Odredimo potom jedan podskup (moguće je da se radi o nepravom podskupu) prirodnih brojeva K tako što ćemo odrediti uvjet pod kojim je prirodan broj n unutar K:

n je unutar K ako i samo ako formula [R(n), n] nije dokaziva.

Nazovimo ovu rečenicu A. Zasad je ključno napomenuti da je svaki pojam i svojstvo spomenuto u A („biti unutar“, „ako i samo ako“, „formula“, „R(n)“, „[R(n), n]“, „nije dokaziva“ …) takvo da ga je moguće predstaviti pomoću neke kombinacije logičkih veznika, brojeva i brojevnih odnosa. Npr. „x je formula“ je vrlo duga formula koja provjerava ima li x (pritom je x izražen u obliku kodirane formule, tj. x je neki Gödelov broj) neko svojstvo koje samo formule mogu imati. Početak takve provjere bi mogao biti primjerice je li x prost broj ili ne; naime nijedna formula nije izraziva pomoću samo jednog prostog broja (što je očito iz načina na koji je aritmetika aritmetizirana), pa ako je x prost broj, onda x sigurno nije neka formula. Iako je teško umno obujmiti A u ovom „polovičnom“ matematičko-metamatematičkom obliku, on ipak najbolje izražava njenu srž (puno jasnije nego čisto-matematički oblik, ili čisto metamatematički (ako takav uopće postoji)). Srećom, u praksi nije previše teško baratati s njom, primjerice: Je li 1 unutar K? Ako u rečenici A svaku pojavu nepoznanice (n) zamijenimo s 1 i dobivena rečenica A’ tada bude istinita, 1 je unutar K.

1 je unutar K ako i samo ako formula [R(1), 1] nije dokaziva.

=

1 je unutar K ako i samo ako formula „0 = 1“ nije dokaziva.

Pod pretpostavkom da je aritmetika konzistentna, „0 = 1“ svakako nije dokaziva i stoga je broj ‘1’ doista unutar K (to naravno vrijedi samo pod pretpostavkom da je aritmetika doista konzistentna; ako aritmetika nije konzistentna, ne samo da ‘1’ nije unutar K, već je K prazan skup!). Nije doista bitno je li ‘1’ unutar K ili ne (to ionako ovisi o principu po kojem su formule poredane), bitno je „samo“ imati na umu da A ima neki, barem maglovit, smisao.

Primijetimo potom kako je i sam A jedna formula. Možda je korisno primijetiti da A u tom obliku nema slobodnih nepoznanica, tj. iako sadrži nepoznanicu  n, ta nepoznanica je „vezana“ u formuli, i možemo pretpostaviti da je A istinita (to i radimo jer je ona ustvari definicija, doslovno odlučujemo da bude istinita). Zanima nas posebno jedan dio formule A, nazovimo ga U:

formula [R(n), n] nije dokaziva

Primijetimo još i da je U također formula, i to formula s točno jednom slobodnom brojevnom nepoznanicom (!). Zbog te osobitosti, nužno je da se U nalazi negdje u našem prethodno dogovorenom poretku formula s jednom slobodnom brojevnom nepoznanicom, na nekom točno određenom mjestu. Označimo to mjesto s brojevnom konstantom q (nije bitno čemu je konkretno jednak q (npr. je li on = 1000), dovoljno je znati da on nužno postoji). Dakle, vrijedi U = R(q).

Konačno, rečenica G glasi:

[R(q), q]

Pretpostavimo prvo da vrijedi identitet istinitosti i dokazivosti.  Pitamo se je li G dokaziv. Pretpostavimo da jest. Pogledajmo što sve vrijedi pod tom pretpostavkom (za početak, uvrštavanjem q u A):

 q je unutar K ako i samo ako formula [R(q), q] nije dokaziva.

Ako je [R(q), q] dokaziva formula (a jest, jer je to netom pretpostavljeno), onda q nije unutar K (uvjet da formula bude unutar K je nedokazivost formule).

No, pogledajmo što G tvrdi na sadržajnoj razini. Ako je G dokaziv, G je po identitetu i istinit. Evo što se događa kad u R(q), odnosno u U, ubacimo q.

formula [R(q), q] nije dokaziva

Podebljani dio nije ništa drugo doli sam G! Tj. dobili smo sljedeći rezultat:

formula G nije dokaziva

Ako je to istina, onda je q sigurno unutar K, jer je dani iskaz ništa drugo doli ispunjen uvjet za biti unutar K. No to je u proturječju s prvim izvedenim zaključkom po kojem je q izvan K! Drugim riječima, ako prihvatimo da je G dokaziva, slijedi da je q izvan K, a također i da je q unutar K. Stoga zaključujemo da je neka od pretpostavki kriva: ili ne vrijedi identitet istinitosti i dokazivosti ili G nije istinita.

Pretpostavimo sada opet da vrijedi identitet istinitosti i dokazivosti, ali ovaj put da G nije istinita (što je zbog identiteta isto što i pretpostaviti da je G nedokaziva). Tada je q, kao i svi redni brojevi nedokazivih formula, unutar K. No, ako je q unutar K, onda je G istinita (!), jer G upravo izražava da je q unutar K. Dakle, ako je G neistinita, G je istinita. To je nemoguće, pa zaključujemo da G nije niti istinita (dokaziva) niti neistinita (nedokaziva).

Što se sada sve dogodilo? Evo shematski prikaz („ne-“ ispred formule označava formulu koja tvrdi upravo protuslovnu tvrdnju od početne):

Pretpostavka (0): iskaz A, „n je unutar K ako i samo ako formula [R(n), n] nije dokaziva.“

       Pretpostavka (1): „istinito“ = „dokazivo“

       Posljedica (2): ili formula G ili formula ne-G je dokaziva /zbog (1)

             Pretpostavka (3): G, tj. [R(q), q], je dokaziva formula.

             Posljedica (4): q nije unutar K                               /zbog (0)

             Posljedica (5): G je istinita                                    /zbog (1) i (3)

             Posljedica (6): formula G nije dokaziva                   /zbog (5) i sadržaja od G

             Posljedica (7): q je unutar K                                  /zbog (0) i (6)

             (4) i (7) su u protuslovlju, stoga je (3) neodrživa pod trenutnim pretpostavkama

             Pretpostavka (8):  ne-G, tj. ne-[R(q), q], je dokaziva formula

             Posljedica (9): q je unutar K                                  /zbog (0) i (8)

             Posljedica (10): G je neistinita                               /zbog (1) i (8)

             Posljedica (11): G je dokaziva formula                   /zbog (10) i sadržaja od G

             Posljedica (12): q nije unutar K                             /zbog (0) i (11)

             (9) i (12) su u protuslovlju, stoga je (8) neodrživa pod trenutnim pretpostavkama

       Posljedica (13): niti je G dokaziva, niti je ne-G dokaziva

       (2) i (13) su u protuslovlju, stoga je (1) neodrživa pod trenutnim pretpostavkama.

Stoga: „istinito“ ≠ „dokazivo“.

Upravo predstavljenim dokazom nije se dokazala samo nepotpunost sustava „P“, već bilo koje dovoljno snažne aritmetike uopće. Rečenice A, U i G su, u svom sadržajnom (metamatematičkom) smislu, dovoljne za stvoriti „paradoksalnu“ situaciju na kojoj počiva Gödelov dokaz. Stoga je bilo koji sustav u kojem se može izraziti metamatematički smisao rečenica A, U i G nužno nepotpun.

No, ono što je još zanimljivije od općenitosti metode korištene u dokazu je da se sustavi ne mogu zakrpati. Tj. dodavanjem rečenice G među aksiome (ili dodavanjem rečenice ne-G) sustav će i dalje imati dokazne rupe. Dodavanje zakrpe bilo gdje u sustavu ima neželjenu posljedicu da se negdje drugdje u sustavu otvara nova rupa. Imamo li, primjerice, sustav P, te mu dodamo aksiom G, i time dobijemo novi sustav P’, otvorit će se „rupa“ koju nismo pokrili. Razlog se krije u tome što G ne govori o P’ već o P, tj. o starom sustavu, a ne o onom trenutno zanimljivom. Dakle, iako će u sustavu P’ formula G biti dokaziva, postojat će jedna druga formula, formula koju možemo označiti sa G’, koja će biti nedokaziva – i ona će kompromitirati potpunost sustava P’ (na isti način su nepotpuni i P”, P”’ itd.)

Prema tome je matematika nepotpuna u dva smisla (koji se međusobno ne isključuju), oba puta s mogućim metafizičkim posljedicama:

1. ili se svi matematički očiti aksiomi i njihove posljedice ne mogu obuhvatiti  dobro definiranim sustavom, te naš matematički um nadilazi svaki konačan stroj (u tom se slučaju čini da se rad ljudskoga uma ne može svesti na (mehanički) rad mozga (stajalište koje Gödel nazivlje „vitalizmom“),

2. ili opstoje apsolutno neodlučljivi matematički stavci (u tom slučaju s praktičnom sigurnošću slijedi da su matematički predmeti (skupovi) neovisni o našim umskim činima i odlukama („pojmovni realizam“ ili „platonizam“); inače bismo, kao stvaratelji matematičkih predmeta, nužno poznavali sva svojstva tih predmeta. [Kovač, str. 35.]

Literatura:

• Kurt Godel, O formalno neodlučivim stavcima Principia Mathematica i srodnih sustava I, u Ernest Nagel/James R. Newman, Gödelov dokaz, Zagreb 2001.
• Ernest Nagel/James R. Newman, Gödelov dokaz, Zagreb 2001.
• Srećko Kovač, Logičko-filozofijski ogledi, Zagreb 2005.