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.

U formulaciji Gedelove teoreme o potpunosti, riječ dokaziva je sintaktičke prirode: ona označava da postoji formalno izvođenje formule u teoriji u pitanju, u ovom slučaju u predikatskom računu prvog reda. Takvo izvođenje–dokaz je konačan spisak koraka u kojem se svaki korak ili poziva na aksiomu teorije ili se dobija iz prethodnih koraka primjenom osnovnih pravila zaključivanja. Kada je takvo izvođenje dato, ispravnost svakog od koraka se može provjeriti algoritamski (na primjer, pomoću računara, ili ručno). Pojam valjane formule, pak, je semantički: formula je valjana ako je tačna u svakom modelu jezika formule (odnosno svaka takva interpretacija je i jedan njen model).

Gedelova teorema o potpunosti pokazuje da su aksiome i pravila zaključivanja predikatskog računa prvog reda „potpuni“ u smislu da nikakve dodatne aksiome ili pravila zaključivanja nisu potrebni kako bi se izvele sve logički valjane formule. Komplementarno svojstvo je ispravnost (semantička konzistentnost ili neprotivurečnost). Teorema o ispravnosti tvrdi da je predikatski račun prvog reda semantički ispravan, odnosno da se u njemu mogu izvesti jedino logički valjana tvrđenja. Ponekad se teorema o ispravnosti tretira kao deo jednog, sveobuhvatnog iskaza o potpunosti, poput formulacije samog Gedela iz 1929., koja u osnovi glasi:

Postoji račun predikatske logike prvog reda takav da za svaki skup formula Γ i svaku formulu φ važi: φ slijedi iz Γ ako i samo ako se φ može izvesti iz Γ u ovom računu.

Teorema o potpunosti ustanovljava temeljnu vezu između semantike (teorije modela, koja izučava šta je tačno u različitim interpretacijama) i sintakse (teorije dokaza, koja izučava šta se može dokazati u pojedinačnim formalnim sistemima). Ako  označava semantičku posljedicu i  izvedivost u računu, gornja Gedelova teorema glasi

Ovdje, smjer zdesna na lijevo odgovara ispravnosti, a slijeva na desno potpunosti računa. Slabiji iskaz Gedelove teoreme o potpunosti citiran na početku članka, odgovara slučaju kada je Γ prazan skup formula (zapravo se može dokazati da su „slabiji“ i „jači“ iskaz ekvivalentni). Ova teorema, međutim, ne ukida niti marginalizuje razliku između ova dva pristupa. U stvari, drugi rezultat koji je proslavio Gedela, njegova teorema o nepotpunosti, pokazuje da postoje suštinska ograničenja u pogledu toga šta se u matematici može postići formalnim dokazima: konkretno, da se unutar dovoljno bogatih teorija ne može svaka dokazati svaki valjan iskaz. (Pažnja: ime Gedelove teoreme o nepotpunosti se odnosi na drugo značenje riječi „potpun“. Vidi članak Teorija modela.)

Gedelova teorema o potpunosti uspostavlja teorijsku osnovu automatskih dokazivača, dakle izradi i proveri dokaza pomoću računarskih programa. Isprva je činila i prvi korak u okviru Hilbertovog programa (izrada potpunog i neprotivurečnog računa za cijelu matematiku), sve dok program nije dotučen upravo Gedelovom teoremom o nepotpunosti.

Gedelov matematički dokaz o postojanju Boga

Mnogi matematičari, fizičari i astronomi su religiozni, biolozi mnogo ređe, a ekonomisti i psiholozi retko. Izgleda da, što su pitanja kojima se stričnjaci bave bliža samom čoveku, slabije su njihove sklonosti ka veri. Gedel je bio matematički genije opsednut Bogom i zagrobnim životom (slični su bili Isak Njutn i Blez Paskal). Mislio je da je pomoću logike moguće dokazati i takve nedoumice kao što je pitanje života posle smrti i postojanje Boga. U četiri duga pisma majci naveo je razloge svog verovanja u drugi svet. Negde oko 1970. godine ovaj matematički dokaz o postojanju Boga počeo je da kruži i među njegovim kolegama. Bio je napisan na samo jednoj stranici hartije.

Aksiom 1 (Dihotomija) Osobina je pozitivna ako i samo ako je njena negacija negativna.

Aksiom 2 (Zaključak) Osobina je pozitivna ako nužno sadrži pozitivnu osobinu.

Teorema 1 Pozitivna osobina je logično konzistentna (to jest, moguće je da za nju postoji neki primer).

Definicija Nešto je nalik Bogu ako i samo ako poseduje sve pozitivne osobine.

Aksiom 3 Biti nalik Bogu je pozitivna osobina.

Aksiom 4 Biti pozitivna osobina je nužno.

Definicija Osobina P je suština od x ako i samo ako x sadrži P a P je nužno minimalno.

Teorema 2 Ako je x nalik Bogu, onda je biti nalik Bogu suština x.

Definicija NE(x): x nužno postoji ako ima suštinsku osobinu.

Aksiom 5 Biti NE znači biti nalik Bogu.

Teorema 3 Nužno postoji neko x takvo da je x nalik Bogu.

Community content is available under CC-BY-SA unless otherwise noted.