„Gedelov dokaz“ sastoji se zapravo od dve teoreme. U prvoj se dokazuje da je nekompletna bilo koja teorija koja uključuje prirodne brojeve (1, 2, 3, 4, ... ). U drugoj teoremi Gedel tvrdi da se takve teorije ne mogu dokazati unutar istog sistema aksioma. Za dokazivanja ovakvih teorema polazni aksiomi su nedovoljni, potrebno je izaći u neki veći sistem aksioma. Ali, dokazivanje u većoj teoriji takođe zahteva jos veću teoriju – i tako u nedogled.
Njegova teorema kaze da je u nekim slučajevima nemoguće naći dovoljno aksioma da bi moglo da se odgovori na sva pitanja. Matematičko saznanje predodređeno je da zauvek ostane delimično nepotpuno (nekompletno). Zato se njegova teorema izvorno zvala „teoreme nekompletnosti“. Čak i gore od toga, on je pokazao da je jedno od pitanja na koje ne može da se odgovori i to da li je izabrana grupa aksioma za neki dokaz pravilno odabrana ili se u njoj krije neka protivrečnost. Pre Gedelove teoreme svi su verovali da je matematika, vazna alatka prirodnih nauka, jedina nauka koja može da pruži apsolutnu istinu i da je matematički postupak jedini put do savršenog saznanja. Na neki način, to i jeste tako. Pitagorina teorema vazi i danas u nepromenjenom obliku kakav je imala pre 3000 godina i takva će ostati. Suprotno drugim naukama, gde se teorije vremenom menjaju ili čak odbacuju, kad matematika jednom utvrdi da je nešto tačno, to zauvek ostaje tako. Gedel je, u stvari, otkrio da ni matematika nije savršena nauka i da nije imuna na pitanja na koja ne može tačno da odgovori. Njihova tačnost samo je pitanje uverenja.
Gedelova teorema ne tvrdi da je sama matematika nepotpuna, već svaki sistem koji pokušava da obuhvata sve istine u matematici u vidu konačnog skupa aksioma i pravila. Međutim, za vodeće matematičare iz tridesetih godina proslog veka i ovo saznanje je bilo pravi šok jer je oborilo njihovo poimanje matematike i sveta.
Gedelov tekst iz 1931. godine proizveo je još nešto: teoriju takozvanih rekurzivnih funkcija koje su danas osnova moćne računske teorije. Jer u srži njegovog rada bio je računski program za proizvodnju M. P. brojeva, na koji veoma podseća programski jezik Lisp, osmišljen skoro tri decenije kasnije.
Gedelova teorema o potpunosti je teorema matematičke logike koju je dokazao Kurt Gedel u svojoj doktorskoj disertaciji 1929. i kasnije u radu objavljenom 1930.
U svom najpoznatijem obliku, ona tvrdi da je u predikatskom računu prvog reda svaka logički valjana formula dokaziva. Ovo je jedna od najvažnijih teorema matematičke logike, jer pokazuje da klasičan predikatski račun "sadrži" sve zakone logike koji se mogu iskazati predikatskim formulama. Gedelova teorema o potpunosti u osnovi glasi:
Citat:
Postoji račun predikatske logike prvog reda takav da za svaki skup formula Γ i svaku formulu φ važi: φ sledi iz Γ ako i samo ako se φ može izvesti iz Γ u ovom računu
U matematičkoj logici, Gedelove teoreme o nepotpunosti su dve čuvene teoreme o ograničenjima formalnog sistema, koje je dokazao Kurt Gedel, 1931 godine.
Gedelova prva teorema o nepotpunosti je verovatno najslavniji rezultat u matematičkoj logici. Ona tvrdi da:
Citat:
Za bilo koju formalnu teoriju koja potvrđuje osnovne aritmetičke istine, može se konstruisati aritmetičko tvrđenje koje je istinito ali nije i dokazivo unutar same te teorije. To znači, da bilo koja teorija koja je sposobna da izrazi elementarnu aritmetiku ne može biti u isto vreme i konzistentna i potpuna.
Dokaz =)
Zamislimo da se na nekoj udaljenoj planeti (Marsu, na primer), takođe pišu udzbenici matematike. Pretpostavimo da, nekom čudnom slučajnošću, svi simboli koje Marsovci koriste da bi napisali matematičke knjige izgledaju kao naši brojevi od 0 do 9. Zato kada Marsovci u svojim udzbenicima razmateraju neko od čuvenih otkrića, recimo aksiom koji mi pripisujemo Euklidu i koji glasi : „Postoji beskonačno mnogo prostih brojeva“, oni ga mozda iskazuju ovako : 84453298445302152010024887950234. Ono što nama izgleda kao jedan veliki tridesetdvocifreni broj, za Marsovce uopšte nije broj, nego iskaz. On Marsovcima govori da postoji beskonačnost prostih brojeva, isto tako jasno kao i nama pomenutih pet reči.
Sada zamislimo da želimo da pričamo o prirodi svih matematičkih teorema. Ako pogledamo u marsovske udzbenike, sve te teoreme izgledaće nam kao brojevi. Znači da možemo da razvijemo i jednu podrobnu teoriju o tome koji brojevi mogu da se pojave u marsovskim udzbenicima, a koji se nikada neće pojaviti. Naravno, ne mora doslovno da se radi o našim brojevima, već o nizu simbola koji nama izgledaju kao brojevi.
Na temelju ovako izokrenutog gledišta Gedel je izgradio pravu čaroliju. Njegov trik sastoji se u tome da sada zamislimo da u marsovskim udzbenicima proučavamo brojeve koji zu zapravo teoreme. Nazovimo ih skraćeno „M. P.“ brojevima (od Martian – Producible numbers). Onda možemo da postavimo pitanja : „da li je neki broj 8030974, M. P. broj, ili nije? To jest, da li će izraz 8030974 ikada da se pojavi u marsovskim udzbenicima matematike jer je teorema? Razmišljajući veoma pažljivo o ovom sasvim nerealnom scenariju, Gedel je shvatio da se osobine M. P. brojeva ne razlikuju od tako uobičajenih predstava kao što su „prost broj“, „neparan broj“ i tako dalje. To je značilo da zemaljski teoretičari, koristeći svoje uobičajene postupke, mogu da razmatraju i takva pitanja kao što je „Koji brojevi su M. P. brojevi, a koji nisu?“ i slično.
I tako, u jednom od najoštroumnijjih zaključivanja u istoriji matematike, Gedel je osmislio izvanredan iskaz koji jednostavno glasi : „X nije M. P. broj“, gde je X broj koji vidimo kada je izraz „X nije M. P. broj“ preveden na marsovski matematički jezik. Kada se izraz „X nije M. P. broj“ prevede na marsovski sistem znakova izgledaće nam samo kao dugački niz cifara, to jest, vrlo veliki broj. Ali taj niz marsovskih znakova je i naš zapis za broj X, o kome i sam iskaz govori. Ovo znači da nije moguće potvrditi tačnost iskaza u datom sistemu. =)
Gedelov rad ostavio je dubok trag ne samo u matematici. Čitavog života beležio je svoje matematičke misli. Neki od njegovih radova toliko su složeni da se veruje da će proći vekovi pre nego što se odgonetnu, potvrde ili ospore. Pre njega matematičari, kao uostalom i naučnici u nekim drugim oblastima, smatrali su da stoje na samim vratima konačne istine. Gedel je doneo otrežnjenje: pokazao je da nismo Bogovi, već samo ljudska bića sa ograničenim saznajnim mogućnostima.