Bukti dengan kontradiksi

Bukti dengan kontradiksi adalah teknik pembuktian yang populer. Jika kita ingin membuktikan bahwa suatu pernyataan benar, kita bentuk negasinya, kita anggap negasinya benar, lalu kita berusaha sampai pada suatu kontradiksi. Tujuannya adalah membuktikan bahwa pengandaian yang kita pilih mengarah pada sesuatu yang mustahil.

Contoh trivial

Misalkan diberikan pernyataan “tidak ada bilangan rasional positif terkecil”. Pernyataan ini kita buktikan dengan kontradiksi. Pertama, kita bentuk negasinya: “ada bilangan rasional positif terkecil”. Bilangan ini kita sebut q. Jika q adalah bilangan rasional positif terkecil, kita tidak mungkin menemukan bilangan rasional positif yang lebih kecil, sebab jika ada, bilangan q bukan yang terkecil.

Hal ini kita manfaatkan untuk mencari kontradiksi. Jika kita ternyata menemukan bilangan yang lebih kecil daripada q, yang boleh kita pilih sembarang, kita telah sampai pada kontradiksi, dan pernyataan yang dinegasikan itu salah. Jika sebagai bilangan terkecil kita pilih, misalnya, 0,1, terlihat bahwa 0,01 lebih kecil. Lalu 0,001 lebih kecil lagi, 0,0001 lebih kecil lagi, dan seterusnya. Cukup bagi bilangan q dengan sepuluh, dan kita memperoleh bilangan yang lebih kecil. Pada dasarnya, cukup membaginya dengan bilangan apa pun yang lebih besar daripada satu, misalnya dua: setengah dari bilangan q pasti lebih kecil daripada q itu sendiri.

Jadi, bilangan q/2 pasti lebih kecil daripada q dan sekaligus merupakan bilangan rasional positif. Dengan demikian, kita sampai pada kontradiksi dengan pernyataan yang dinegasikan. Jadi, pernyataan yang dinegasikan itu salah, sehingga pernyataan semula benar.

Bilangan menarik

Bukti jenaka klasik yang menggambarkan prinsip kontradiksi adalah contoh berikut. Anggaplah ada bilangan-bilangan asli yang dalam arti tertentu menarik. Misalnya, bilangan 2 menarik karena 2 · 2 = 2 + 2, sifat yang cukup tidak lazim. Bilangan 42 menarik karena merupakan jawaban atas segalanya. Dan seterusnya. Pertanyaannya: apakah ada tak berhingga banyaknya bilangan yang menarik?

Kita andaikan sebaliknya, yaitu hanya ada berhingga banyaknya bilangan yang menarik, dan ada bilangan-bilangan yang tidak menarik. Bilangan-bilangan asli yang tidak menarik ini kita kumpulkan dalam himpunan bilangan yang tidak menarik. Sekarang kita pilih bilangan tidak menarik yang terkecil. Tunggu, bilangan tidak menarik yang terkecil? Kedengarannya cukup menarik, bukan? :-)

Dengan demikian, kita sampai pada kontradiksi, karena bilangan tidak menarik yang terkecil sebenarnya cukup menarik. Jadi, tidak mungkin ada bilangan tidak menarik yang terkecil, sehingga himpunan bilangan yang tidak menarik pasti kosong.

Tentu saja ini tidak masuk akal, karena kita tidak mendefinisikan dengan baik apa itu bilangan yang menarik. Namun, langkah-langkah pembuktiannya sendiri sudah benar.

Bukti bahwa bilangan prima tak berhingga banyaknya

Dalam contoh ini, kita akan melihat cara yang mirip dengan bagian sebelumnya, tetapi kali ini benar dari segala sisi.

Bilangan prima adalah bilangan yang hanya habis dibagi oleh dua bilangan yang berbeda, yaitu bilangan itu sendiri dan 1. Perhatikan bahwa 1 tidak memenuhi definisi ini, sedangkan 2 memenuhinya.

Faktorisasi prima adalah penguraian bilangan asli selain 1 menjadi hasil kali bilangan-bilangan prima. Ini sifat bilangan asli yang cukup menarik. Bilangan asli apa pun yang kamu ambil (kecuali 1) dapat diuraikan menjadi hasil kali beberapa bilangan prima (boleh ada yang sama). Contoh:

$$\begin{array}{rcl}8& =& 2\cdot 2\cdot 2\\ 15& =& 3\cdot 5\\ 26& =& 2\cdot 13\\ 1800& =& 2^3\cdot 3^2\cdot 5^2\end{array}$$

Pernyataan tentang faktorisasi prima disebut teorema dasar aritmetika. Antara lain, teorema ini menyatakan bahwa faktorisasi seperti itu tunggal, yaitu kita tidak akan menemukan dua faktorisasi prima yang berbeda untuk satu bilangan asli. Selain itu, hanya bilangan prima yang faktorisasi primanya terdiri atas satu bilangan saja, yaitu bilangan itu sendiri. Jadi, faktorisasi prima dari tujuh adalah bilangan tujuh. Fakta-fakta ini akan kita manfaatkan untuk menyusun bukti pernyataan berikut.

Sekarang kita akan membuktikan pernyataan “bilangan prima ada tak berhingga banyaknya”. Sekali lagi, kita bentuk negasi pernyataan ini: “bilangan prima ada berhingga banyaknya”. Kita andaikan bahwa barisan bilangan

$$a_1,a_2,a_3,\dots ,a_n$$

memuat semua bilangan prima yang ada. Jika barisan ini memuat semua bilangan prima, kita pasti tidak akan dapat menemukan bilangan yang merupakan bilangan prima, tetapi tidak termuat dalam barisan ini. Semua bilangan prima ada dalam barisan, dan di luar barisan tidak boleh ada bilangan prima lagi.

Jadi, untuk sampai pada kontradiksi, kita harus menyusun suatu bilangan prima yang tidak termuat dalam barisan ini. Untuk itu, kita memakai bilangan q. Bilangan ini kita susun dengan mengalikan semua bilangan prima dalam barisan, lalu menambahkan 1:

$$q=a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1$$

Sekarang kita harus menunjukkan bahwa bilangan ini adalah bilangan prima atau entah bagaimana menghasilkan bilangan prima. Kita tahu bahwa q bilangan asli dan setiap bilangan asli dapat dinyatakan sebagai hasil kali bilangan-bilangan prima. Namun, tidak ada bilangan prima a_i yang membagi habis bilangan q; setelah pembagian, selalu bersisa 1. Jika kita mencoba membagi bilangan q, misalnya, dengan bilangan prima a₂, hasilnya seperti ini:

$$\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n+1}{a_2}=\frac{a_1\cdot a_2\cdot a_3\cdot \dots \cdot a_n}{a_2}+\frac{1}{a_2}=$$

$$=a_1\cdot a_3\cdot a_4\cdot \dots \cdot a_n+\frac{1}{a_2}$$

Pertama, pecahan kita pisahkan menjadi dua. Pada pecahan pertama, kita coret a₂, sehingga tersisa suatu hasil kali bilangan prima, yaitu suatu bilangan bulat lain yang tidak penting. Pada pecahan kedua, tidak ada yang bisa dicoret. Pecahan ini selalu berupa bilangan yang tidak bulat (karena penyebutnya tidak mungkin 1, sebab 1 bukan bilangan prima). Jadi, jumlahnya adalah bilangan yang tidak bulat, sehingga bilangan prima a₂ tidak membagi habis bilangan q.

Dengan demikian, terbukti bahwa tidak ada bilangan prima dalam barisan a_n yang membagi habis bilangan q. (Catatan: kita memang hanya menunjukkannya untuk a₂, tetapi hal ini mudah diperumum jika a₂ kita ganti dengan a_i sembarang.) Namun, karena setiap bilangan asli dapat diuraikan menjadi hasil kali bilangan-bilangan prima, pasti ada bilangan prima lain yang tidak termuat dalam barisan a_n, tetapi termuat dalam faktorisasi bilangan q. Bilangan q sendiri bisa saja merupakan bilangan prima, dan faktorisasi primanya hanya memuat bilangan q. Jadi, sekali lagi, alur pemikiran terakhirnya:

1. Setiap bilangan asli dapat dinyatakan sebagai suatu hasil kali bilangan-bilangan prima.
2. Menurut pengandaian, barisan a_n memuat semua bilangan prima yang ada.
3. Pernyataan pertama kita ubah menjadi: setiap bilangan asli dapat dinyatakan sebagai hasil kali beberapa suku pilihan barisan a_n, karena barisan itu memuat semua bilangan prima.
4. Kita telah membuktikan bahwa tidak ada bilangan dalam barisan a_n yang membagi habis bilangan q.
5. Dengan demikian, timbul kontradiksi dengan pengandaian → jika setiap bilangan asli harus dapat diuraikan menjadi hasil kali bilangan-bilangan prima, sedangkan barisan a_n tidak memuat satu pun bilangan yang membagi q, pasti ada bilangan prima lain yang membagi q dan membentuk faktorisasi prima bilangan q.

Dengan begitu, kita sampai pada kontradiksi. Faktorisasi prima bilangan q memuat bilangan-bilangan prima yang tidak termuat dalam barisan yang kita andaikan memuat semua bilangan prima. Jadi, pernyataan yang dinegasikan salah, dan pernyataan semula benar. Bilangan prima ada tak berhingga banyaknya.