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. x1, y1, z1… za varijable prvog tipa (varijable koje se javljaju u uobičajenim aritmetičkim jednadžbama i predstavljaju brojeve). Zatim x2, y2, z2… za varijable drugog tipa (tj. „rečenične“ varijable, npr. x2 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: (x1 = y1) =def ∀x2(¬(¬x2 (x1) ∨ ¬x2 (y1)) ∨ ¬(x2 (y1) ∨ x2 (x1)))). Ova nečitljiva formula ustvari kaže: ako svako brojevno svojstvo koje vrijedi o x1 također vrijedi i o y1, i obratno, onda su x1 i y1 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 pn, 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 = 152. 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 y2. 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                      26 * 35 * 56

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

6 misli o “Gödelov dokaz

  1. S obzirom da nisam autor, pretpostavljam da nije neprimjereno da na svom blogu iskažem sve pohvale jednome zapisu. Naravno, ne mogu doista ocijeniti u kolikoj je mjeri Luka uspio prenijeti sve aspekte Gödelovog dokaza, jer spadam u golemu većinu običnih smrtnika koji se ne usude ništa više nego tek zaviriti u taj zastrašujući članak. Ali mogu, u usporedbi s nekoliko ”popularnih” prikaza koje jesam čitao, reći da je tijek dokaza ovdje iznesen egzaktnije i jasnije. Čestitke! 🙂

    Naravno, nama koji bismo htjeli ”nauke bez muke (dokazivanja)” najzanimljivije su ”moguće metafizičke posljedice” odustajanja od poimanja matematike kao neke ”slagalice” (poput npr. šaha), a što bi značilo da ”ono simboličko” nadilazi mehanički ”intelekt”. Obje su preostale metafizičke mogućnosti, čini mi se, suprotstavljene uobičajenim scientističkim predočbama: i ”vitalistička” o umu kao nečemu što bitno nadilazi stroj (npr. računalo), i ”platonistička” o postojanju ne-tvarne matematičke stvarnosti.

    Liked by 1 person

  2. Ok, ne mogu reći da sam baš sve skužio (:D), ali da skratimo priču: da li bi se moglo ikako reći da je Gödel dokazao da je aritmetika konzistentna, ali nije kompletna (potpuna)? Ili?
    Laički, u četiri pet rečenica (može i jedna), što je Gödel na kraju zapravo dokazao kod aritmetike? Da aritmetički sustav ne može u isto vrijeme biti konzistentan i potpun? Ako je konzistentan, ne može se unutar njega sve dokazati (npr. p i ne-p) pa onda nije potpun? A ako je potpun, jel može biti konzistentan? Ne kužim baš, ali me najviše zanima odgovor na moje prvo pitanje, odmah iza prve dvotočke. Hvala. 🙂

    Sviđa mi se

    • Ovo: “Da aritmetički sustav ne može u isto vrijeme biti konzistentan i potpun”. Najkraće, dokazao je da je svaka formalizirana aritmetika nepotpuna i da tome nema lijeka. Nije dokazao konzistentnost aritmetike, ali je dokazao da se konzistentnost aritmetike ne može dokazati koristeći se samo aritmetikom. Postoje dokazi konzistentnosti aritmetike koji se služe metodama koje nisu obuhvaćene običnom aritmetikom; nedavno je na forum.hr jedan forumaš pričao o tome, no ne znam gotovo ništa o tim dokazima osim da su se pojavili negdje kad i ovaj Gödelov dokaz. Nagađam da njihova vrijednost nije osobito velika jer su korištene metode koje su same po sebi kontroverznije od cijele aritmetike, te se ne drže ograničenja originalnog Hilbertovog programa.

      Da, ako je sustav konzistentan, to znači da se unutar njega nužno ne može svaki iskaz dokazati (za svaki iskaz p, bilo se p ne može dokazati, bilo ne-p, jer kad bi se mogla oba, sustav ne bi više bio konzistentan). No potpunost sustava ne znači da se unutar sustava može dokazati svaki iskaz uopće, već da se unutar sustava može dokazati svaki istinit iskaz. Ako je sustav potpun, je li konzistentan? Nisam siguran. Naišao sam do sada na raznim mjestima razne definicije potpunosti. Prema najblažem shvaćanju potpunosti, svaki nekonzistentan sustav je potpun, jer, doista, svaka istina je dokaziva, premda je i svaka neistina dokaziva. No takva potpunost nije osobito zanimljiva. Mislim da se u većini slučajeva uzima da ima smisla govoriti o potpunosti tek onda kad je sustav konzistentan.

      Za prvu dvotočku, ne može se ipak tako formulirati, ali ta formulacija nije jako daleko od Gödelovog rezultata; dakle za Gödelov teorem (onaj koji povezuje konz. i potp. sustava) bi se moglo reći da dokazuje da je jedno od sljedećeg istinito o ma kojoj aritmetici bilo riječ:
      – nekonzistentna je i potpuna/nepotpuna (ovisno kako shvatimo potpunost, ali to je obična formalnost, čim je sustav nekonzistentan, blagodati potpunosti otpadaju, te nije bitno hoćemo li ga nazvati potpunim ili nepotpunim)
      – konzistentna je i nepotpuna

      Naša intuicija govori da je aritmetika konzistentna (to je isto što i reći da nam intuicija govori kako je iskaz “1 je veće od 2″ lažan), pa ako joj popustimo, jedino rješenje po Gödelu je ustvrditi kako je aritmetika nepotpuna. Ako se pokaže da je aritmetika nekim čudom ipak nekonzistentna, onda nam Gödelov dokaz kaže kako će nakon eventualnog “popravljanja” aritmetike ta aritmetika biti nepotpuna.

      Usput, sve se to može izraziti i na (barem meni) puno simpatičniji način: istinito =/= dokazivo u svakoj aritmetici.

      Sviđa mi se

  3. Mogao bih sad dosta toga odgovoriti, ali idemo polako i redom da ne bude previše “kaotično”. Reda mora biti, kod ovakvih tema pogotovo :). Hehe.

    Jedna stvar mi nije baš jasna. Zašto bi aritmetika, ukoliko bi bila konzistentna, morala biti nepotpuna?

    Ono što je svakako točno (a što si napisao) je da je ako je aksiomatski sustav inkonzistentan, on je NUŽNO potpun. Zato što u njemu možemo dokazati teorem i njegovu negaciju što je kontradikcija, a iz kontradikcije možemo izvesti sve. Ti si rekao da takva ideja “potpunosti” i nije nešto, ali je to svakako potpunost.

    Dakle kod Gödela se radi da aritmetika ili je jedno ili je drugo, a nikada oboje? Dakle on nije dokazao da je aritmetika konzistentna ali je dokazao da AKO PRETPOSTAVIMO da je konzistentna, ona ne može biti potpuna?
    Ako je to točno, zašto je tomu tako?

    Sviđa mi se

    • To je ono što je Gödel dokazao. Pokazao je da za svaku aritmetiku postoji barem jedna istinita i nedokaziva rečenica, koja se obično označava kao “rečenica G”. Kako je uvjet potpunosti mogućnost dokazivanja svih istinitih rečenica, a on je pronašao istinitu nedokazivu rečenicu, zaključio je da je svaka aritmetika nepotpuna. No, sve je radio pod jednom pretpostavkom, a to je pretpostavka da je artimetika konzistentna. Ako ona nije konzistentna, onda se svaka rečenica uopće može dokazati, pa tako i rečenica G. Zbog te pretpostavke o konzistentnosti (koja nije prethodno dokazana), morao je i nju ubaciti u teorem, u obliku ako-onda rečenice (ako je aritmetika konz., nije potp.).

      Ok. 🙂

      “Dakle kod Gödela se radi da aritmetika ili je jedno ili je drugo, a nikada oboje?” – Da, ako se potpunost shvati u onom jačem smislu u kojem zahtjeva konzistentnost (dakle ne u ovom smislu na koji si mislio u “svakako potpunost”, a koje je tehnički ispravnije od jačeg smisla). Ako ti je to bitno, imaš neki udžbenik/skriptu/nešto da pogledaš točnu definiciju potpunosti? Potražih sad na netu, mislim da je blaža verzija službena. 😀 Ali provjeri ako nisi siguran…

      “Dakle on nije dokazao da je aritmetika konzistentna ali je dokazao da AKO PRETPOSTAVIMO da je konzistentna, ona ne može biti potpuna?” – Tako je. Možda te buni to na koji način konzistentnost utječe na nepotpunost? Gödel nije doslovno iz konzistentnosti izveo nepotpunost, radije on je dokazao nepotpunost (na način kako je opisano u postu (i u prvom odlomku ovog komentara)), a prije svega toga je pretpostavio da je aritmetika konzistentna. Ako aritmetika nije konzistentna, svaka aritm. rečenica je i istinita i neistinita, a u takvoj situaciji je bespotrebno išta istraživati. Taj dio o konzistentosti bi se mogao u svaki aritm. teorem uopće ubaciti, npr. umjesto “0 = 0″ reći “ako je aritmetika konzistentna, tada je 0 = 0″. Ako-onda ni u slučaju “0 = 0″ ni u slučaju Gödela (vjerojatno) nije ono što bismo mogli nazvati uzročnom vezom.

      Sviđa mi se

  4. Povratni ping: zašto matematika ne može zahvatiti istinu? | nagovor na filosofiju

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava / Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava / Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava / Izmijeni )

Google+ photo

Ovaj komentar pišete koristeći vaš Google+ račun. Odjava / Izmijeni )

Spajanje na %s