Slavni teorem Alfreda Tarskog o nedefinabilnosti istine tvrdi da istinite rečenice nekog formalnog jezika nije moguće definirati u samom tom jeziku (njegov ne manje slavni teorem o definabilnosti istine tvrdi da je to moguće u odgovarajućem metajeziku). Evo dokaza tog teorema koji može pratiti i netko bez posebnog znanja matematičke logike.

Formalni jezik izgrađen je od osnovnih elemenata koje zovemo simbolima (možete misliti o slovima abecede). Konačni nizovi simbola su izrazi (npr. „abvagad“). Izrazi se mogu spajati, tj. ako su X i Y izrazi „edfzes“ i „msaneko“ onda je i XY izraz „edfzesmsaneko“.

Neki izrazi su opća imena koja imenuju skupove izraza (kao što opće ime „glagol“ imenuje skup svih glagola). Skup izraza je imenovan ako postoji opće ime koje ga imenuje.

Rečenica je izraz oblika JX u kojem je J opće ime, a X bilo koji izraz. Ta rečenica izriče da izraz X pripada skupu koji imenuje opće ime J, tj. ona je istinita ako i samo ako izraz X pripada skupu kojeg imenuje J.

Rečenice su uvijek različite od općih imena, tj. ako je J opće ime onda JX nije opće ime, koji god izraz bio X.

Dvije rečenice su ekvivalentne ako su obje istinite ili su obje neistinite.

Teorem Tarskog:
Pretpostavimo da formalni jezik sadrži simbole D i N takve da vrijedi:

(D) Za svako opće ime J, izraz DJ također je opće ime, a rečenica DJO ekvivalentna je rečenici JOO za svako opće ime O (možemo reći da D „duplira“ jer O pripada skupu J ako i samo ako OO pripada skupu DJ).

(N) Za svako opće ime J, izraz NJ također je opće ime, a rečanica NJR je istinita ako je i samo ako je rečenica JR neistinita, za svaku rečenicu R (možemo reći da N „negira“).

Ukratko, jezik sadrži „duplikaciju“ i „negaciju“.

U takvom formalnom jeziku skup istinitih rečenica nije moguće imenovati.

Prije dokaza samog teorema dokazat ćemo jednu lemu iz koje će teorem lako slijediti.

Lema o fiksnoj točki:
Fiksna točka općeg imena J je rečenica R takva da su rečenice R i JR ekvivalentne. Svako opće ime formalnog jezika koji sadrži „duplikaciju“ ima fiksnu točku.

Dokaz leme:
Rečenica DJO ekvivalentna je rečenici JOO, za svako opće ime O (to je definicija od D), pa stoga i za O=DJ. Dakle, rečenica DJDJ ekvivalentna je s rečenicom JDJDJ. No, to znači da je DJDJ fiksna točka od J.

Dokaz teorema:
Ako opće ime T imenuje skup svih istinitih rečenica, onda je rečenica TR ekvivalentna s R, za svaku rečenicu R (naime, „istina je da je snijeg bijel“ ako i samo ako „snijeg jest bijel“).

Drugim riječima, sve bi rečenice R trebale biti fiksne točke od T.

No, to je u suprotnosti s lemom o fiksnoj točki jer tada nijedna rečenica ne bi mogla biti fiksna točka od NT, budući da fiksna točka od NT nikada ne može biti fiksna točka od T (u protivnom bi rečenice TR i NTR bile ekvivalentne, jer bi obje bile ekvivalentne sa zajedničkom fiksnom točkom R, a one, po definiciji od N, nisu ekvivalentne ni za jedan R).

P.S. (za matematičare i logičare)

Primjena ovog rezultata na matematičke formalne sustave je sljedeća. U formalnoj aritmetici su „opća imena“ formule s jednom slobodnom varijablom (kraće: predikati), ali ne skupova izraza nego skupova brojeva.

Veza s gornjim teoremom se postiže tako da se svi izrazi formalne aritmetike numeriraju tzv. Gödelovim brojevima (što je relativno lako), pa naš JX postaje J(n) gdje je n Gödelov broj izraza X.

Svaki formalni sustav aritmetike sadrži negaciju, pa (N) uvijek vrijedi.

Što se tiče (D) Gödel je ingeniozno dokazao da za svaki predikat J(x) postoji predikat J(x) takav da je za svaki Gödelov broj k predikata K(x) rečenica J(k) ekvivalentna s rečenicom J(k*). Ovdje J(k) ima ulogu gornjeg DJR, a J(k*) ima ulogu gornjeg JRR, tj. formalni sustav aritmetike sadrži duplikaciju.

Sada iz gornjeg teorema lako slijedi:

Teorem Tarskoga za formalnu aritmetiku:
Ne postoji aritmetički predikat T(x) takav da je T(n) istinito ako je i samo ako je n Gödelov broj istinite aritmetičke rečenice.

Osim toga Gödel je pokazao (što je relativno lako) kako se skup dokazivih rečenica formalne aritmetike može imenovati u formalnoj aritmetici. No, to znači da se skup dokazivih rečenica ne poklapa sa skupom istinitih rečenica, tj. vrijedi:

Gödelov teorem o nepotpunosti:
U formalnim sustavima aritmetike koji su korektni uvijek postoji rečenica koja je istinita ali u njima nije dokaziva.

Naime, sustav je korektan ako je svaka u njemu dokaziva rečenica istinita, tj. skup dokazivih rečenica sadržan je u skupu istinitih rečenica. Budući da se ta dva skupa ne poklapaju, uvijek mora postojatii rečenica koja je istinita ali nije dokaziva.

Lako je naći i konkretnu takvu rečenicu, koja se tada zove Gödelovom.
Naime, svaka fiksna točka F predikata NP (gdje P imenuje skup dokazivih rečenica) takva je istinita ali nedokaziva rečenica, jer je F istinita akko je NPF istinita akko je PF neistinita akko F nije dokaziva, tj. F je istinita i nije dokaziva ili je dokaziva i nije istinita, a drugi slučaj nije moguć zbog korektnosti našeg formalnog sustava aritmetike.

Iz leme o fiksnoj točki sada slijedi da je DNPDNP takva fiksna točka, tj. DNPDNP je jedna konkretna Gödelova rečenica (naravno treba je na gore opisani način prevesti u rečenicu formalne aritmetike).

Korolar:                                                                                                            

U formalnim sustavima aritmetike koji su korektni uvijek postoji rečenica koja je neodlučiva, tj. niti ona niti njezina negacija nisu dokazive u sustavu.

Nedokaziva rečenica iz Gödelovog teorema je stinita, pa je zbog korektnosti i njezina negacija nedokaziva.

Gödel je zapravo dokazao ovaj korolar, ali bez poziva na pojam istinitosti, što je bitno teže od ovdje prikazanog dokaza koji se poziva na pojam istinitosti.(To je njegov dokaz činilo prihvatljivim i intuicionistima za koje je istinitost intuicionistička dokazivost.)

Odgovori

Please log in using one of these methods to post your comment:

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