Mengapa teorema ketidaklengkapan Gödel sulit untuk dibuktikan: masalahnya ada dalam formulasi, dan bukan hanya pada dasarnya

Secara kasar, teorema ketidaklengkapan Gödel menyatakan bahwa ada pernyataan matematika yang benar yang tidak dapat dibuktikan. Ketika saya berada di kelas 11, kami bertiga bersama-sama dengan guru geometri Mr. Olsen dan teman saya Uma Roy menghabiskan lima minggu membaca bukti asli Gödel. Kenapa begitu lama? Sebagian karena kami masih anak sekolah. Sebagian karena Gödel, 24, bukan penulis paling berbakat. Tetapi terutama karena buktinya sebenarnya cukup sulit.

Ini mungkin tampak mengejutkan, karena semua bukti sebenarnya dapat masuk ke dalam satu paragraf. Gödel mulai dengan membangun pernyataan matematika yang pada dasarnya setara dengan kalimat,

Pernyataan ini tidak dapat dibuktikan.

Godel kemudian mempertimbangkan apa yang akan terjadi jika pernyataan ini salah. Itu kalau pernyataan ini bisa dibuktikan. Tetapi setiap pernyataan yang dapat dibuktikan harus benar - ini adalah kontradiksi. Dari sini, Gödel menyimpulkan bahwa pernyataan itu harus benar. Tetapi, karena pernyataan itu benar, maka dari sini pernyataan itu tidak dapat dibuktikan. Harap dicatat bahwa pernyataan akhir ini bukan kontradiksi. Sebaliknya, ini adalah bukti teorema Gödel.

Jadi mengapa bukti nyata begitu rumit? Kuncinya adalah bahwa apa yang mungkin terdengar seperti pernyataan matematika yang valid dalam bahasa Inggris seringkali tidak demikian (terutama ketika kalimat merujuk pada dirinya sendiri). Pertimbangkan, misalnya, kalimat berikut:

Kalimat ini salah.

Sebuah kalimat tidak ada artinya: tidak mungkin salah (karena itu akan membuatnya benar) dan itu tidak bisa benar (karena itu akan membuatnya salah). Dan itu, tentu saja, tidak dapat ditulis dalam bentuk pernyataan matematis formal.

Berikut adalah contoh lain (dikenal sebagai paradoks Berry):

Tetapkan {x} sebagai bilangan bulat positif terkecil yang tidak dapat dijelaskan dalam kurang dari 100 kata.

Ini mungkin terlihat seperti definisi matematika yang valid. Tetapi sekali lagi, itu tidak masuk akal. Dan, yang penting untuk kewarasan matematika, tidak ada pernyataan serupa yang dapat ditulis secara formal, yaitu secara matematis.

Bahkan pernyataan dalam bahasa matematika dapat menjadi tidak berarti:

$$

$$S = \ {A \ mid A \ tidak \ di A \}$$

(mis. $$$S$Apakah banyak set $$$A$yang bukan elemen dari diri mereka sendiri).

Sekali lagi ini adalah definisi yang tidak berarti (dikenal sebagai paradoks Russell). Secara khusus, setelah kami mengidentifikasi $$$S$kita dapat bertanya apakah $$$S$dirimu sendiri? Jika demikian, maka $$$S$tidak bisa menjadi anggota $$$S$- sebuah kontradiksi; dan jika tidak, maka $$$S$akan menjadi anggota $$$S$- lagi kontradiksi.

Arti dari tiga contoh ini adalah bahwa jika Anda ingin membuktikan teorema tentang pernyataan matematika, Anda harus sangat berhati - hati tentang fakta bahwa Anda benar-benar beroperasi dengan pernyataan matematika. Memang, dari 46 definisi di awal hingga bukti kuat yang mengejutkan di akhir, artikel asli Gödel tidak lebih dari latihan besar-besaran dengan hati-hati.