Bukti secara percanggahan

Bukti secara percanggahan ialah teknik pembuktian yang popular. Jika kita ingin membuktikan bahawa sesuatu pernyataan benar, kita nafikan pernyataan itu, andaikan penafiannya benar, dan cuba sampai kepada suatu percanggahan. Matlamatnya ialah membuktikan bahawa andaian yang kita pilih membawa kepada sesuatu yang mustahil.

Contoh remeh

Katakan kita mempunyai pernyataan “tidak wujud nombor nisbah positif yang terkecil”. Kita buktikan pernyataan ini secara percanggahan. Mula-mula kita nafikan pernyataan itu: “wujud nombor nisbah positif yang terkecil”, dan kita tandakan nombor ini dengan q. Jika q ialah nombor nisbah positif yang terkecil, kita tidak akan dapat mencari nombor nisbah positif yang lebih kecil, kerana jika ada, nombor q bukan lagi yang terkecil.

Kita gunakan fakta ini untuk mencari percanggahan. Jika kita dapat juga mencari nombor yang lebih kecil daripada q (nombor terkecil itu boleh dipilih sesuka hati), kita sampai kepada percanggahan, dan pernyataan yang dinafikan itu tidak benar. Jika kita memilih, misalnya, 0.1 sebagai nombor terkecil, kita lihat bahawa nombor 0.01 lebih kecil. Seterusnya, 0.001 lebih kecil lagi, 0.0001 lebih kecil lagi, dan seterusnya. Kita hanya perlu membahagikan nombor q dengan sepuluh untuk memperoleh nombor yang lebih kecil. Sebenarnya, kita boleh membahagikannya dengan sebarang nombor yang lebih besar daripada satu, misalnya dengan dua. Separuh daripada nombor q sudah tentu lebih kecil daripada nombor q itu sendiri.

Jadi, nombor q/2 sudah tentu lebih kecil daripada q, dan nombor itu juga ialah nombor nisbah positif. Dengan itu, kita sampai kepada percanggahan dengan pernyataan yang dinafikan. Maka, pernyataan yang dinafikan itu tidak benar, dan oleh itu pernyataan asal (yang belum dinafikan) itu benar.

Nombor yang menarik

Contoh berikut ialah bukti jenaka klasik yang menggambarkan prinsip percanggahan. Andaikan terdapat nombor asli yang menarik dalam suatu cara. Contohnya, nombor 2 menarik kerana 2 · 2 = 2 + 2, iaitu sifat yang agak luar biasa. Nombor 42 menarik kerana nombor itu ialah jawapan kepada segala-galanya. Dan seterusnya. Soalannya: adakah terdapat tak terhingga banyaknya nombor yang menarik?

Andaikan sebaliknya, iaitu hanya terdapat terhingga banyaknya nombor yang menarik, dan sesetengah nombor tidak menarik. Kita kumpulkan nombor asli yang tidak menarik ini dalam set nombor yang tidak menarik. Sekarang kita pilih nombor yang tidak menarik yang terkecil. Tunggu dulu, nombor tidak menarik yang terkecil? Bunyinya agak menarik, bukan? :-)

Dengan itu, kita sampai kepada percanggahan, kerana nombor tidak menarik yang terkecil sebenarnya agak menarik. Jadi, nombor tidak menarik yang terkecil tidak mungkin wujud, maka set nombor yang tidak menarik semestinya kosong.

Sudah tentu bukti ini tidak masuk akal, kerana kita tidak mentakrifkan dengan betul apa itu nombor yang menarik. Tetapi cara pembuktiannya sendiri tidak salah.

Bukti bahawa nombor perdana tak terhingga banyaknya

Dalam contoh ini, kita akan menggunakan kaedah yang serupa dengan bahagian sebelumnya, tetapi kali ini bukti itu betul dari semua segi.

Nombor perdana ialah nombor yang boleh dibahagi tepat dengan dua nombor yang berbeza sahaja, iaitu dengan nombor itu sendiri dan dengan satu. Perhatikan bahawa nombor satu tidak memenuhi takrif ini, tetapi nombor dua memenuhinya.

Pemfaktoran perdana ialah penguraian nombor asli, kecuali satu, kepada hasil darab nombor perdana. Hal ini ialah sifat nombor asli yang agak menarik. Ambil sebarang nombor asli (kecuali satu), maka nombor itu boleh diuraikan kepada hasil darab beberapa nombor perdana (yang mungkin 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 pemfaktoran perdana dipanggil teorem asas aritmetik. Antara lain, teorem ini menyatakan bahawa pemfaktoran itu unik, iaitu kita tidak akan menemui dua pemfaktoran perdana yang berbeza bagi satu nombor asli. Selain itu, hanya nombor perdana yang mempunyai pemfaktoran perdana yang terdiri daripada satu nombor sahaja, iaitu nombor itu sendiri. Jadi, pemfaktoran perdana bagi tujuh ialah nombor tujuh. Kita akan menggunakan fakta-fakta ini untuk membina bukti bagi pernyataan berikut.

Sekarang kita akan membuktikan pernyataan bahawa “nombor perdana tak terhingga banyaknya”. Sekali lagi kita nafikan pernyataan itu: “bilangan nombor perdana terhingga”. Andaikan jujukan nombor

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

mewakili semua nombor perdana yang wujud. Jika jujukan ini mengandungi semua nombor perdana, maka sudah tentu kita tidak akan dapat mencari nombor yang merupakan nombor perdana tetapi tidak terdapat dalam jujukan ini. Semua nombor perdana ada dalam jujukan itu, dan tiada nombor perdana boleh wujud di luarnya.

Untuk sampai kepada percanggahan, kita perlu membina suatu nombor perdana yang tidak terdapat dalam jujukan ini. Untuk tujuan ini, kita menggunakan nombor q. Kita bina nombor ini dengan mendarab semua nombor perdana dalam jujukan itu dan menambah satu:

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

Sekarang kita perlu menunjukkan bahawa nombor ini sama ada nombor perdana atau menghasilkan nombor perdana dengan suatu cara. Kita tahu bahawa q ialah nombor asli dan setiap nombor asli boleh diungkapkan sebagai hasil darab nombor perdana. Walau bagaimanapun, tiada nombor perdana a_i yang dapat membahagi tepat nombor q, kerana bakinya sentiasa satu. Jika kita cuba membahagikan nombor q, misalnya, dengan nombor perdana a₂, kita memperoleh:

$$\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}$$

Mula-mula kita pecahkan pecahan itu kepada dua. Dalam pecahan pertama, kita batalkan a₂, dan yang tinggal ialah hasil darab beberapa nombor perdana, iaitu suatu integer lain yang tidak penting. Dalam pecahan kedua, tiada apa-apa yang dapat dibatalkan. Pecahan ini sentiasa bukan integer (kerana penyebutnya tidak boleh satu, sebab satu bukan nombor perdana). Jadi, hasil tambahnya ialah nombor yang bukan integer. Maka, nombor perdana a₂ tidak membahagi nombor q.

Dengan itu, kita telah membuktikan bahawa tiada nombor perdana dalam jujukan a_n yang membahagi nombor q. (Nota: kita hanya menunjukkannya bagi a₂, tetapi hal ini mudah diitlakkan jika kita menggantikan a₂ dengan a_i yang am.) Tetapi oleh sebab setiap nombor asli boleh diuraikan kepada hasil darab nombor perdana, mesti wujud nombor perdana lain yang tidak terdapat dalam jujukan a_n, tetapi merupakan faktor perdana bagi nombor q. Nombor q itu sendiri mungkin juga nombor perdana, dan dalam kes ini, pemfaktoran perdananya hanya mengandungi nombor q. Jadi, sekali lagi, mari kita ulang aliran pemikiran ini buat kali terakhir:

1. Setiap nombor asli boleh diungkapkan sebagai hasil darab nombor perdana.
2. Menurut andaian, jujukan a_n mengandungi semua nombor perdana yang wujud.
3. Kita ubah pernyataan pertama: setiap nombor asli boleh diungkapkan sebagai hasil darab sebutan-sebutan tertentu dalam jujukan a_n, kerana jujukan itu mengandungi semua nombor perdana.
4. Kita telah membuktikan bahawa tiada nombor dalam jujukan a_n yang membahagi nombor q.
5. Dengan itu, timbul percanggahan dengan andaian → jika setiap nombor asli mesti boleh diuraikan kepada hasil darab nombor perdana, dan jujukan a_n tidak mengandungi sebarang nombor yang membahagi q, maka mesti wujud nombor perdana lain yang membahagi q dan membentuk pemfaktoran perdana bagi nombor q.

Dengan itu, kita sampai kepada percanggahan. Pemfaktoran perdana bagi nombor q mengandungi nombor perdana yang tidak terdapat dalam jujukan yang kita andaikan mengandungi semua nombor perdana. Jadi, pernyataan yang dinafikan itu tidak benar, dan pernyataan asal (yang belum dinafikan) itu benar. Nombor perdana tak terhingga banyaknya.