Pembuktian Teorema - Bukti dengan Kontradiksi

Pada pos ini akan dibahas pembuktian dengan kontradiksi.

Hallo lagi sahabat matematika!

Sebelumnya kita membahas beberapa metode pembuktian yaitu bukti langsung dan bukti tak langsung (bukti dengan kontraposisi). Kali ini kita akan membahas bukti tak langsung yang lain, yaitu bukti dengan kontradiksi. Well, sebenernya ini metode pembuktian kesukaan saya.

Dalam bukti dengan kontradiksi, kita mulai dengan mengasumsikan bahwa teorema (atau proposisi) tersebut salah. Lalu dengan langkah yang matematis, akan diperoleh keganjilan, keganjalan, dan ketidakmungkinan (sejenis itu lah pokoknya) yang berlawanan dengan yang telah kita ketahui (misalnya 2 adalah bilangan ganjil, 1 adalah bilangan negatif, dan sebagainya). Akibatnya, asumsi kita salah, sehingga teorema tersebut benar.

Contoh penggunaan bukti dengan kontradiksi

Kita mulai dengan beberapa contoh berikut.

Contoh 1

Proposisi. Untuk $n$ bilangan bulat, jika $n^2$ genap maka $n$ genap.

Bukti.
Asumsikan $n^2$ genap namun $n$ ganjil. Karena $n$ ganjil, maka $n = 2k + 1$ untuk suatu bilangan bulat $k$. Dengan menguadratkan diperoleh

$$\begin{align*} n^2 &= (2k + 1)^2 \\ &= 4k^2 + 4k + 1 \\&= 2(2k^2 + 2k) + 1 \end{align*}$$ sehingga $n^2 = 2t + 1$ dengan $t = 2k^2 + 2k$. Dengan kata lain, $n^2$ ganjil. Akibatnya $n^2$ genap sekaligus ganjil. Tidak mungkin bilangan bulat genap sekaligus ganjil. Kontradiksi.

Contoh 2

Saat membahas sistem bilangan real, kita mengatakan $\sqrt 2$ adalah bilangan irasional tanpa bukti. Dalam contoh 2 ini kita akan buktikan bahwa $\sqrt 2$ adalah bilangan irasional. Untuk definisi bilangan irasional bisa dilihat di sini . Bukti lain dari pernyataan ini akan kita tambahkan nanti, yaitu bukti dengan menggunakan Well-Ordering Property pada bilangan bulat positif.

Proposisi. $\sqrt 2$ adalah bilangan irasional

Bukti
Asumsikan $\sqrt 2$ bukan bilangan irasional, yakni $\sqrt 2$ merupakan bilangan rasional. Maka $\sqrt 2$ dapat dinyatakan sebagai perbandingan dua bilangan bulat paling sederhana, yaitu

$$\sqrt 2 = \frac{a}{b}$$ dengan $b \neq 0$  dan GCD(a,b) = 1. Dengan menguadratkan kedua ruas diperoleh $$2 = \frac{a^2}{b^2}$$ maka $$2b^2 = a^2$$ ruas kiri genap. Akibatnya $a^2$ juga genap. Berdasarkan bukti sebelumnya, $a$ juga genap. Misalkan $a = 2k$. Maka persamaan tadi menjadi $$\begin{align*} 2b^2 &= a^2 \\ 2b^2 &= (2k)^2 \\ 2b^2 &= 4k^2 \end{align*}$$ dengan membagi kedua ruas dengan 2 diperoleh $$b^2 = 2k^2$$ akibatnya $b^2$ genap dan $b$ genap.

Karena $a$ genap dan $b$ genap maka $\frac{a}{b}$ dapat disederhanakan lagi. Kontradiksi dengan $\frac{a}{b}$ telah dalam bentuk paling sederhana.

Contoh 3

Dalam contoh ini kita akan.... Well langsung aja deh

Proposisi Sedikitnya 10 dari 64 hari yang dipilih jatuh pada hari yang sama dalam seminggu.

Bukti
Asumsikan paling banyak 9 hari yang jatuh pada hari yang sama. Karena dalam seminggu ada 7 hari, maka paling banyak ada 63 hari yang dapat dipilih. Ini kontradiksi dengan kita harus memilih 64 hari.

Contoh 3 merupakan salah satu penerapan dari Pigeonhole Principle (Prinsip sarang merpati).

Kayanya 3 contoh itu aja. Selanjutnya ke bagian latihan. Buktikan proposisi atau teorema berikut. Anda bisa gunakan bukti langsung, bukti dengan kontraposisi, atau bukti dengan kontradiksi.

Latihan

1. Jumlah bilangan rasional dan irasional adalah bilangan irasional.
2. Jika kita mengambil 3 kaos kaki dari lemari berisi hanya kaos kaki hitam dan biru, kita pasti mendapatkan sepasang kaos kaki hitam atau sepasang kaos kaki biru.
3. Paling tidak 3 dari 25 hari yang kita pilih jatuh pada bulan yang sama dalam setahun
4. Tidak ada bilangan rasional $r$ sedemikian sehingga $r^3 + r + 1 = 0$
5. Jika $0 \leq x \leq \frac{\pi}{2}$ maka $\sin x + \cos x \geq 1$
6. Untuk $a,b$ dan $c$ bilangan bulat, jika $a^2 + b^2 = c^2$ maka $a$ atau $b$ genap.
7. Jika $a$ dan $b$ bilangan bulat maka $a^2 - 4b \neq 2$
8. Jika $n$ adalah bilangan bulat maka $n^2 \geq n$
9. Jika $m$ dan $n$ adalah bilangan bulat dan $mn$ genap maka $m$ genap atau $n$ genap.
10. $^2 \log 3$ adalah bilangan irasional.
11. Suatu bilangan bulat $n$ dikatakan bilangan kuadrat sempurna jika terdapat bilangan bulat $a$ sedemikian sehingga $n = a^2$. Contoh bilangan kuadrat sempurna adalah $0,1,4,9,$ dan seterusnya.
    Buktikan bahwa jika $n$ bilangan kuadrat sempurna maka $n + 2$ bukan kuadrat sempurna.

---

Nikmati pembuktiannya. Untuk selanjutnya akan lebih banyak bukti lagi dan strategi pembuktian.

Itu aja kayanya
See you next Illusion ~