U prošlom sam postu objasnio da je svaka deduktivna teorija zapravo stroj za geneiranje teorema. Ako je takav stroj korektan i dovoljno jak onda je on faktički nepotpun, iako je logički potpun. Zašto je to tako pokazat će nam jedan jednostavni primjer faktički nepotpunog stroja (koji je tipičan).

Zamislimo stroj koji printa nizove simbola -, P i d, koje ćemo zvati izrazima. Na primjer, Pd-, d, –d i P-  su izrazi. Stroj ih printa u diskretnim vremenskim razmacima, koje ćemo zvati trenucima. Dakle, ako stroj u 1. trenutku printa izraz Pd-, u 2. trenutku izraz d, u 3. trenutku izraz   –d i u 4. izraz P-, onda rezultat njegovoga rada nakon prva četiri trenutka izgleda ovako:

….      4         3           2          1

….      P-      –d         d        Pd-

Izrazi oblika

(1)       PX,                                         (2)       -PX,

(3)       PdX,                                       (4)       -PdX,

(gdje je X bilo koji izraz u (3), (4) i bilo koji izraz koji ne poćinje s d u (1), (2) ), imaju sljedeća značenja:

(1)      Izraz oblika PX znači da  stroj  printa ( printao je, printati će ) izraz X.

(2)       Izraz oblika -PX znači da  stroj ne printa (nije printao, neće printati) izraz X.

Prije nego što definiramo značenja izraza koji su oblika (3) i (4) potrebno je definirati značenje dijagonalizacije d. Dijagonalizacija dX izraza X je izraz XX. Na primjer, dijagonalizacija  d-Pd izraza -Pd je izraz –Pd-Pd.

(3)       Izraz oblika PdX znači da  stroj  printa dijagonalizaciju  izraza X, tj. da printa XX.

(4)       Izraz oblika -PdX znači da  stroj ne printa dijagonalizaciju  izraza X, tj. da ne printa XX.

Izraze oblika (1) – (4) zvati ćemo  rečenicama.

Dakle, stroj (između ostalog) printa rečenice koje govore o tome što on printa, tj. stroj je samoreferirajuć.

Postavlja se pitanje, je li moguće konstruirati stroj koji bi bio korektan, tj. ne bi printao neistinite rečenice, i koji bi uz to bio faktički potpun, tj. prije ili kasnije otprintao bi sve istinite rečenice. Odgovor je negativan:

Ako je stroj korektan onda je nepotpun.

 Razmotrimo, naime, rečenicu -Pd-Pd. Budući da je ona dijagonalizacija od -Pd, lako se vidi da su sljedeće tri tvrdnje ekvivalentne:

Rečenica -Pd-Pd je istinita.

 Stroj ne printa dijagonalizaciju od -Pd.

Stroj ne printa rečenicu -Pd-Pd.

Zbog ekvivalencije prve i treće tvrdnje, imamo dvije mogućnosti:

  1. Rečenica  -Pd-Pd je istinita i stroj je ne printa.
  2. Rečenica  -Pd-Pd nije istinita i stroj je printa.

Ako je stroj korektan, onda druga mogućnost ne dolazi u obzir, pa preostaje samo prva mogućnost, tj. stroj je faktički nepotpun. (Ključna rečenica ovoga dokaza, -Pd-Pd, sama o sebi govori da nije printana, kao što paradoksalna rečenica (2) iz Lažljivog Epimenida sama o sebi govori da nije istinita. Gödelova će rečenica sama o sebi govoriti da nije dokaziva.)

 Ovakav dokaz faktičke nepotpunosti možemo ponoviti za svaku deduktivnu teoriju (stroj), ako je ona korektna i dovoljno jaka u sljedećem smislu:

I.         Teorija sadrži rečenice koje govore o dokazivosti njezinih rečenica.

II.        Teorija sadrži funkciju dijagonaliziranja koja omogućuje izgradnju konkretne  Gödelove rečenice G, koja sama o sebi govori da nije dokaziva.

Naime, sada “printan” postaje “dokaziv”, rečenice o printanju postaju rečenice o dokazivosti, konkretna rečenica  -Pd-Pd (koja sama o sebi govori da nije printana) postaje konkretna Gödelova rečenica G (koja sama o sebi govori da nije dokaziva).

Gödel je zapravo dokazao da deduktivna teorija koja sadrži elementarnu aritmetiku ima svojstva I. i II. i to je bio najteži dio posla. Nakon toga se dokaz nepotpunosti može provesti analogno dokazu faktičke nepotpunosti ranije opisanog stroja.

(Gödelov 2. teorem o nepotpunosti može se dokazati tako da se dokaz 1. teorema, koji je dokaz jedne tvrdnje o deduktivnoj teoriji, reproducira u samoj toj teoriji. Naime, može se dokazati da je u samoj teoriji dokazivo da iz konzistentnosti teorije slijedi njezina nepotpunost, tj. nedokazivost Gödelove rečenice G. Dakle, ako bi se konzistentnost teorije mogla dokazati u samoj teoriji onda bi u njoj bilo dokazivo da je G nedokaziva. Ali to je u suprotnosti s 1. teoremom o nepotpunosti. To znači da je pretpostavka o dokazivosti konzistentnosti bila pogrešna. Dakle, konzistentnost teorije nije dokaziva u samoj teoriji.)

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