Self reference lagi

Sekarang bagaimana menuliskan kalimat berikut ini dalam notasi aritmetika?

Kalimat ini benar tetapi tidak dapat dibuktikan.

Perhatikan kalimat berikut ini.

\neg \exist x: \exist y: (\text{substitusi } z \text{ ke } z = y) \land (x \text{ membuktikan } y)

Kalimat di atas dapat dibaca sebagai:

Tidak terdapat bilangan x, yang memiliki bilangan y padanannya sedemikian hingga: Substitusi z ke dirinya sendiri menghasilkan y, dan x membuktikan y.

Atau secara lebih ringkas:

Tidak terdapat bilangan yang dapat membuktikan hasil substitusi z dengan z.

Kalimat tersebut jika ditulis dengan bilangan Gödel akan berbentuk:

3542134342131443...31...

Dengan bagian titik-titik adalah bilangan Gödel untuk dua ungkapan yang dibahas sebelumnya. Dengan menyebut bilangan Gödel ini sebagai m, kita dapat menuliskan penarikan kesimpulannya sebagai berikut:

m

Tidak terdapat bilangan yang dapat membuktikan hasil substitusi z dengan z.

Sekarang kita memiliki bilangan Gödel m untuk menyebut, Tidak terdapat bilangan yang dapat membuktikan hasil substitusi z dengan z.

z adalah variabel yang dapat diganti dengan bilangan. m adalah bilangan. Jadi bilangan m bisa disubstitusikan pada z. Mari kita mensubstitusi z dengan m.

IU(m, z = m)
= Tidak terdapat bilangan yang dapat membuktikan hasil substitusi m dengan m.

Catatan

IU(m, z=m) di sini berarti substitusi variabel z dengan m.

Kalimat tersebut pasti juga memiliki bilangan Gödel untuk menomori teoremanya. Mari kita sebut bilangan Gödelnya sebagai G.

m

Tidak terdapat bilangan yang dapat membuktikan hasil substitusi z dengan z.

G

IU(m, z = m)

G

Tidak terdapat bilangan yang dapat membuktikan hasil substitusi m dengan m.

Apakah yang dimaksud dengan hasil substitusi m dengan m? Hasil substitusi m dengan m tidak lain adalah G, bukan?

G

IU(m, z = m)

Substitusi m dengan m adalah G.

Dengan demikian, G dapat dituliskan ulang dalam bentuk lain.

G

Tidak terdapat bilangan yang dapat membuktikan hasil substitusi m dengan m.

G

Tidak terdapat bilangan yang dapat membuktikan G.

Atau dapat kita terjemahkan sebagai:

G

Tidak terdapat bilangan yang dapat membuktikan kalimat ini.

Kita telah sukses menerjemahkan kalimat Kalimat ini benar tetapi tidak dapat dibuktikan, dalam notasi aritmetika.

Kalau begitu, dapatkah G dibuktikan dari aksioma-aksioma dalam sistem? Jika dapat, berarti ada kontradiksi di sini. Jika tidak dapat, berarti kalimat ini benar.

Dapatkah G dibuktikan?
Dapat Berarti G benar dan G salah: kontradiksi.
Tidak dapat Berarti G benar.

Nah, sampai di sini kita terpaksa menyimpulkan bahwa kalimat G benar. Sekaligus, karena G menyatakan bahwa dirinya tak dapat dibuktikan, berarti kalimat G benar tapi tak dapat dibuktikan dari aksioma-aksioma dalam sistem aritmetika.

Dengan demikian Gödel telah menunjukkan pada kita suatu hal yang penting: Terdapat pernyataan yang benar dalam aritmetika yang tak dapat dibuktikan. Ternyata dengan aritmetika, kita telah membuktikan bahwa hal yang benar tidak selalu dapat dibuktikan. Wow!

Beberapa pembuktian mengenai ini dengan menggunakan pendekatan berbeda juga dapat kamu lihat dalam video-video berikut ini:

Math’s Existential Crisis (Gödel Incompleteness Theorems) - Undefined Behavior

Gödel’s First Incompleteness Theorem, Proof Sketch - Undefined Behavior

Gödel’s Second Incompleteness Theorem, Proof Sketch - Undefined Behavior

Gödel’s Incompleteness Theorem Explained Part 1 - BestThingWorstThing

Berikutnya: Alan Turing (1912-1954)

Ditulis oleh
Pak Ari
Ditulis pada
Terakhir diupdate
Dipublikasikan
Frase kunci
sejarah pemikiran tokoh