Self reference lagi

Sekarang bagaimana menuliskan kalimat berikut ini dalam notasi aritmetika?

Kalimat ini benar tetapi tidak dapat dibuktikan.

Perhatikan kalimat berikut ini.

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:

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:

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.

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

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

Dengan demikian, G dapat dituliskan ulang dalam bentuk lain.

Atau dapat kita terjemahkan sebagai:

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.

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)