Pernyataan-pernyataan yang tak dapat dibuktikan benar maupun salah

Sistem mengungu yang kita bahas sebelumnya adalah sistem yang komplet. Artinya, semua pernyataan yang dibuat dalam sistem itu bisa dibuktikan benar (proven) maupun salah (disproven).

Namun ada sistem-sistem yang tidak bersifat seperti itu. Sistem-sistem ini memungkinkan untuk kita membuat pernyataan yang tak dapat dibuktikan benar maupun salah. Istilah yang digunakan oleh matematikawan adalah undecidable statements.

Contoh: Sistem V

Sebagai contoh, sistem sederhana berikut ini, yang kita namakan sistem V. Dalam sistem V terkandung relasi v(x, y) terhadap domain D = {0, 1, 2}.

Berdasarkan informasi-informasi awal tersebut, kita dapat memperoleh sejumlah teorema. Buktinya tidak dituliskan di sini, supaya gurumu bisa menjadikannya PR untukmu.

Sistem di atas akan membentuk graf:

Sekarang kita akan mencoba menjawab pertanyaan berikut ini: Apakah v(1,2)?

Percobaan pembuktian pertama

Pertama-tama mari kita coba pembuktian langsung. Jadi kita setidaknya memerlukan instansiasi universal (IU) terhadap R1 untuk mendapatkan v(2,1) \implies \neg v(1,2).

Seandainya kita tahu v(2,1), kita dapat menyimpulkannya secara langsung menggunakan modus ponens (MP).

Namun kita harus bisa menjawab terlebih dahulu pertanyaan apakah v(2, 1). Mari kita coba menjawabnya. Kita juga hanya dapat memakai R1 karena itu satu-satunya aturan yang kita punya.

Nah! Ternyata agar kita dapat menjawab apakah v(2, 1) kita memerlukan informasi mengenai v(1, 2). Seandainya saja kita memiliki informasi mengenai v(1,2), kita akan bisa menarik kesimpulan darinya.

Namun ternyata, sekarang kita kembali lagi membutuhkan v(2,1)!

Lho! Ini kan sudah? Ternyata dari tadi kita hanya berputar-putar saja! Kalau begitu, mari kita coba dari aksioma atau teorema lainnya.

Percobaan pembuktian kedua

Kita hanya mendapat kesimpulan \neg v(1,0), dan tidak dapat melanjutkannya hingga mendapat v(1,2) maupun v(2,1).

Jadi bagaimana kita dapat membuktikannya? Sepertinya kita hanya terus menerus berputar-putar saja. Sampai tahap ini, ada baiknya kamu sedikit curiga: Jangan-jangan ini memang tak dapat dibuktikan?

Tampaknya ini tak dapat dibuktikan

Kadang-kadang ada pernyataan yang tak dapat ditarik sebagai kesimpulan informasi-informasi yang sudah tersedia, karena tidak ada jalur yang menuju ke sana.

Teknik pembuktian yang telah kita pelajari sebelumnya adalah pembuktian di dalam sistem. Masih ingatkah kamu akan Sistem-MIU (Bab Hakikat Matematika)? Dalam sistem tersebut kita bisa berusaha menjawab pertanyaan, Apakah MU bisa diperoleh dari MI? dan kita berputar-putar dengan deduksinya.

Alih-alih melihat sistem dari dalam sistem itu sendiri, kita dapat melihat dari luar sistem. Pada dasarnya kita akan bertanya pertanyaan ini: Apakah yang akan terjadi jika v(1,2) benar? dan, Apakah yang akan terjadi jika v(1,2) salah? Dua pertanyaan ini diwakili oleh hipotesis H_0 dan H_A di bawah ini.

Berarti kita perlu membuat dua variasi sistem kita. Yang pertama mengasumsikan bahwa v(1,2) benar (H_0), dan yang kedua mengasumsikan bahwa v(1,2) salah (H_A).

Setelah kita membuat dua variasi sistem ini, kita akan mencoba menarik kesimpulan sebanyak mungkin dan melihat apakah kedua sistem yang dihasilkan tetap konsisten atau tidak. Pembuktian seperti ini disebut sebagai pembuktian independensi (independence proof).

Berikutnya: Pembuktian Independensi