Bab 6: Teknik Pembuktian Matematika

Sebuah bukti dimulai dengan memahami persis apa yang dinyatakan: domain, kuantor, hipotesis, dan kesimpulannya. Bab ini menghubungkan pembacaan tersebut dengan bukti langsung, kontraposisi, kontradiksi, eksistensi, dan keunikan. Contoh yang gagal memperlihatkan letak syarat yang diperlukan, sedangkan kontra-contoh menguji klaim universal dengan memenuhi semua hipotesisnya. Aritmetika bilangan dipakai sebagai bahan kerja dengan prasyarat yang dinyatakan; konstruksi sistem bilangan dan induksi dibahas pada bab berikutnya.

6.1 Anatomi Teorema, Lemma, Korolari, dan Konjektur

Perhatikan tiga kalimat yang dapat muncul berdekatan pada satu halaman buku matematika.

1. "Bilangan bulat $n$ disebut genap jika $n = 2k$ untuk suatu bilangan bulat $k$."
2. "Jika $n$ genap, maka $n^2$ genap."
3. "Setiap bilangan bulat genap yang lebih besar dari $2$ adalah jumlah dua bilangan prima."

Ketiganya berbentuk kalimat deklaratif, tetapi perannya sangat berbeda. Kalimat pertama menetapkan makna sebuah kata. Kalimat kedua adalah klaim yang dapat dan harus dibuktikan. Kalimat ketiga adalah klaim yang, sejauh pembahasan ini, belum dibuktikan dan juga belum dibantah. Kalimat kedua juga menyembunyikan beberapa hal. Kalimat itu tidak menyebut dari mana $n$ diambil dan tidak menyebut apakah klaimnya berlaku untuk setiap $n$ atau hanya suatu $n$.

Sebelum mempelajari cara membuktikan pada Subbab 6.2 sampai 6.4, kita perlu dapat membaca dengan tepat apa yang hendak dibuktikan. Unit ini membahas tiga hal. Pertama, peran berbagai jenis pernyataan dalam teks matematika. Kedua, anatomi pernyataan universal bersyarat beserta negasinya. Ketiga, cara hasil-hasil yang terbukti saling bergantung, dan bagaimana ketergantungan itu dapat rusak oleh penalaran sirkular.

Prasyarat yang dipinjam pada unit ini. Unit ini memakai fakta berikut tanpa membuktikannya ulang:

• dari logika klasik pada bab-bab logika: tabel kebenaran implikasi, kesetaraan $\neg(P \Rightarrow Q) \equiv P \land \neg Q$, dan hukum De Morgan untuk kuantor;
• dari bab himpunan: notasi $\{x \in D : P(x)\}$ dan himpunan kosong $\varnothing$;
• dari aritmetika bilangan (pinjaman, bukan dikonstruksi di bab ini):
  • $\mathbb{Z}$ tertutup terhadap penjumlahan, pengurangan, dan perkalian;
  • $\mathbb{Z} \subseteq \mathbb{R}$, dengan operasi dan urutan pada $\mathbb{Z}$ sama dengan yang diwarisi dari $\mathbb{R}$;
  • $\mathbb{R}$ memenuhi sifat medan terurut;
  • $\mathbb{R}$ tidak mempunyai pembagi nol, yaitu $ab = 0$ mengakibatkan $a = 0$ atau $b = 0$;
  • $x^2 \ge 0$ untuk setiap $x \in \mathbb{R}$;
  • tidak ada bilangan bulat $k$ dengan $0 < k < 1$.

---

Peran pernyataan: definisi, aksioma, hipotesis, hasil, dan konjektur

Definisi 6.1.1 (Genap; pengingat keterbagian dari Definisi 4.3.5).

(a) Bilangan bulat $n$ disebut genap jika terdapat $k \in \mathbb{Z}$ sehingga $n = 2k$. Bilangan $k$ tersebut disebut saksi kegenapan $n$.

(b) Untuk $a, b \in \mathbb{Z}$, dikatakan $a$ membagi $b$, ditulis $a \mid b$, jika terdapat $k \in \mathbb{Z}$ sehingga $b = ak$.

Definisi menetapkan arti sebuah istilah; penetapan arti itu bukan teorema yang harus dibuktikan. Namun definisi wajib terdefinisi dengan baik. Jika suatu objek diperkenalkan sebagai satu-satunya objek yang memenuhi syarat, keberadaan dan ketunggalannya harus dibuktikan. Jika definisi memakai wakil kelas ekuivalensi, hasilnya harus bebas dari pilihan wakil, sebagaimana pada Bab 4. Definisi yang tampak bermakna pun dapat gagal memenuhi kewajiban tersebut. Kata "jika" dalam definisi, menurut konvensi yang lazim, berarti "tepat ketika". Jadi $n$ genap jika dan hanya jika ada saksi $k \in \mathbb{Z}$ dengan $n = 2k$.

Perhatikan bahwa Definisi 6.1.1(b) tidak memuat pembagian. Akibatnya $a = 0$ diperbolehkan, misalnya $0 \mid 0$ karena $0 = 0 \cdot 1$. Merumuskan keterbagian lewat saksi, bukan lewat pecahan $b/a$, menghindarkan kita dari masalah pembagi nol.

Peran-peran yang lain diringkas sebagai berikut.

Ada dua pembedaan yang sering kabur.

Aksioma dan prasyarat pinjaman. Sifat seperti $a + b = b + a$ untuk $a, b \in \mathbb{R}$ dipakai di unit ini tanpa bukti. Bagian lain buku ini menentukan apakah sifat itu kelak diturunkan dari suatu konstruksi bilangan real atau diambil sebagai aksioma. Di sini kita cukup menandainya sebagai pinjaman. Kita tidak boleh berpura-pura sudah membuktikannya.

Hipotesis dan fakta. Pada pernyataan "jika $n$ genap maka $n^2$ genap", bagian "$n$ genap" bukan pernyataan bahwa semua bilangan bulat adalah genap, dan bukan pernyataan bahwa suatu $n$ tertentu memang genap. Bagian itu adalah syarat. Di dalam bukti kita menulis "andaikan $n$ genap" dan memanfaatkannya. Setelah bukti selesai, yang kita peroleh adalah implikasi itu sendiri, bukan kebenaran "$n$ genap".

Label hasil tidak menyatakan derajat kepastian

Teorema, proposisi, lema, dan korolari memiliki standar kebenaran dan pembuktian yang sama. Masing-masing harus diturunkan secara lengkap dari definisi, aksioma atau prasyarat pinjaman yang ditandai, dan hasil yang sudah dibuktikan sebelumnya. Nama-nama itu hanya mencerminkan peran penyajian.

• Teorema dipakai untuk hasil yang oleh penulis dianggap pusat dalam suatu pembahasan.
• Proposisi dipakai untuk hasil yang layak dicatat tetapi kurang sentral. Konvensinya berbeda-beda antarbuku.
• Lema adalah hasil pembantu yang terutama dibuktikan untuk dipakai dalam bukti lain.
• Korolari adalah hasil yang diperoleh dari hasil sebelumnya dengan sedikit argumen tambahan.

Akibatnya:

• Sebuah lema tidak "kurang pasti" daripada teorema. Ada lema yang dipakai berulang kali dan lebih penting daripada teorema yang ditopangnya.
• Korolari tetap memerlukan bukti. Kata "akibatnya" bukan bukti. Penulis wajib menunjukkan bagaimana hipotesis hasil sebelumnya dipenuhi dan bagaimana kesimpulannya dipakai.
• Label adalah pilihan penulis. Hasil yang sama dapat disebut lema di satu buku dan teorema di buku lain.
• Label tidak menjamin kebenaran. Tulisan "Teorema" di atas suatu kalimat adalah klaim penulis bahwa kalimat itu telah dibuktikan. Pembaca yang cermat memeriksa buktinya. Pernyataan berlabel dengan bukti yang cacat belum terbukti, walaupun pernyataannya mungkin benar.

Konjektur: belum terbukti, bukan otomatis salah

Konjektur adalah klaim yang belum dibuktikan dan belum dibantah dalam pembahasan yang bersangkutan. Status ini dapat berubah ke dua arah:

• jika ditemukan bukti yang sah, konjektur menjadi hasil, misalnya teorema;
• jika ditemukan kontra-contoh yang sah, pernyataan itu terbukti salah dan berhenti menjadi konjektur.

Selama keduanya belum terjadi, konjektur tidak boleh dipakai sebagai langkah yang dianggap benar dalam bukti dan tidak boleh disebut salah. Konjektur boleh muncul sebagai hipotesis eksplisit suatu implikasi, misalnya "jika konjektur X benar, maka …". Hasil seperti itu terbukti sebagai implikasi; hasil itu tidak menetapkan kebenaran konjekturnya.

Pada contoh berikut, bilangan prima dipakai dalam arti lazim: bilangan bulat $p > 1$ yang pembagi positifnya hanya $1$ dan $p$.

Contoh 6.1.2 (Banyak kasus bukan bukti). Misalkan seseorang menghitung $f(n) = n^2 + n + 41$ untuk beberapa bilangan bulat tak negatif:

$$f(0) = 41,\quad f(1) = 43,\quad f(2) = 47,\quad f(3) = 53,\quad f(4) = 61.$$

Kelimanya prima. Ia lalu menduga: "untuk setiap bilangan bulat $n \ge 0$, $f(n)$ prima." Dugaan ini salah. Untuk $n = 40$,

$$f(40) = 1600 + 40 + 41 = 1681 = 41 \cdot 41.$$

Jadi $41$ adalah pembagi positif $1681$ dengan $1 < 41 < 1681$, sehingga $1681$ tidak prima. Satu nilai $n = 40$ yang berada dalam domain sudah cukup membantah klaim universal itu. Pelajaran dari contoh ini bukan bahwa semua dugaan salah. Pelajarannya adalah bahwa pemeriksaan sejumlah berhingga kasus, sebanyak apa pun, tidak membuktikan klaim tentang tak hingga banyak kasus.

Konjektur Goldbach. Kalimat ketiga di awal unit ini dikenal sebagai konjektur Goldbach. Deskripsi seminar Ben Green di Mathematical Institute, University of Oxford, tanggal 16 November 2018 menyebutnya sebagai masalah yang belum terselesaikan [R6-2]. Di sini pernyataan tersebut dipakai sebagai contoh konjektur, tanpa menjadikannya dasar bukti. Sekalipun sangat banyak kasus diperiksa dan semuanya cocok, hal itu tidak mengubah statusnya menjadi teorema. Bahwa konjektur ini belum terbukti juga tidak mengubahnya menjadi pernyataan salah.

---

Anatomi pernyataan universal bersyarat

Sebagian besar hasil dalam buku ini berbentuk

$$\forall x \in D,\ \bigl(P(x) \Rightarrow Q(x)\bigr).$$

Bagian-bagiannya adalah sebagai berikut.

• Domain $D$ adalah himpunan tempat $x$ diambil. Bentuk $\forall x \in D,\ \varphi(x)$ adalah singkatan dari $\forall x\,(x \in D \Rightarrow \varphi(x))$. Bentuk $\exists x \in D,\ \varphi(x)$ adalah singkatan dari $\exists x\,(x \in D \land \varphi(x))$.
• Variabel terikat $x$ terikat oleh kuantor $\forall$. Namanya tidak penting: $\forall x \in D\,(P(x) \Rightarrow Q(x))$ dan $\forall t \in D\,(P(t) \Rightarrow Q(t))$ menyatakan hal yang sama. Sebaliknya, kalimat yang memuat variabel bebas, seperti "$n^2$ genap" tanpa keterangan tentang $n$, belum merupakan pernyataan yang bernilai benar atau salah.
• Hipotesis $P(x)$ adalah syarat tambahan pada $x$, di samping syarat $x \in D$.
• Kesimpulan $Q(x)$ adalah hal yang harus diturunkan bagi setiap $x \in D$ yang memenuhi hipotesis.

Contoh 6.1.3 (Membedah sebuah klaim). Kalimat "Kuadrat bilangan genap adalah genap" ditulis lengkap sebagai

$$\forall n \in \mathbb{Z},\ \bigl(n \text{ genap} \Rightarrow n^2 \text{ genap}\bigr).$$

• Domainnya $\mathbb{Z}$. Kata "bilangan" dalam kalimat asal ditafsirkan sebagai bilangan bulat, karena "genap" hanya didefinisikan untuk bilangan bulat.
• Variabelnya $n$, terikat oleh $\forall$.
• Hipotesisnya "$n$ genap", yaitu $\exists k \in \mathbb{Z},\ n = 2k$.
• Kesimpulannya "$n^2$ genap", yaitu $\exists j \in \mathbb{Z},\ n^2 = 2j$.

Kuantor universal pada kalimat asal tersembunyi. Kalimat matematika sehari-hari sering tidak menulis "untuk setiap", tetapi kuantor itu tetap bagian dari klaim.

Membaca bentuk ini dengan tepat langsung memberi kerangka bukti:

Ambil $n \in \mathbb{Z}$ sebarang. Andaikan $n$ genap. Akan ditunjukkan bahwa terdapat $j \in \mathbb{Z}$ dengan $n^2 = 2j$.

Kerangka ini menuntut tiga disiplin.

1. Sebarang berarti sebarang. Setelah menulis "ambil $n$ sebarang", kita tidak boleh kemudian mengandaikan $n$ positif, $n = 4$, atau $n$ memiliki sifat lain yang tidak diberikan hipotesis. Yang boleh dipakai hanya $n \in \mathbb{Z}$ dan $P(n)$.
2. Semua syarat harus tertulis. Ini mencakup domain dan syarat agar setiap ungkapan bermakna, terutama syarat bahwa pembagi tidak nol.
3. Bukti harus berakhir pada kesimpulan yang tepat. Baris terakhir harus menyatakan $Q(n)$, yaitu "$n^2$ genap" lengkap dengan saksinya. Pernyataan yang mirip, atau konversnya ("jika $n^2$ genap maka $n$ genap"), tidak cukup.

Contoh 6.1.4 (Syarat pembagi yang hilang). Seseorang menulis: "Untuk setiap $x \in \mathbb{R}$, $\dfrac{x^2 - 1}{x - 1} = x + 1$." Pada $x = 1$, ruas kiri menjadi $\dfrac{0}{0}$, yang tidak terdefinisi. Jadi klaim itu tidak bermakna untuk seluruh domain yang disebutkan. Rumusan yang tepat adalah

$$\forall x \in \mathbb{R} \setminus \{1\},\quad \frac{x^2 - 1}{x - 1} = x + 1.$$

Bukti. Ambil $x \in \mathbb{R} \setminus \{1\}$ sebarang. Maka $x - 1 \neq 0$, sehingga $(x - 1)^{-1}$ ada. Karena $x^2 - 1 = (x - 1)(x + 1)$,

$$\frac{x^2 - 1}{x - 1} = (x - 1)(x + 1)(x - 1)^{-1} = (x + 1)\bigl((x - 1)(x - 1)^{-1}\bigr) = (x + 1) \cdot 1 = x + 1. \qquad \blacksquare$$

Syarat $x \neq 1$ dipakai tepat ketika invers $(x - 1)^{-1}$ diperlukan.

---

Negasi pernyataan berkuantor

Untuk membantah sebuah klaim kita perlu tahu persis bentuk negasinya. Bentuk negasi juga diperlukan untuk metode kontradiksi pada Subbab 6.3.

Fakta 6.1.5 (Aturan negasi; logika klasik, dipinjam dari bab logika). Untuk domain $D$, himpunan $A$ dan $B$, predikat $P$ dan $Q$, serta predikat dua-variabel $R$:

1. $\neg\,\forall x \in D,\ P(x) \;\equiv\; \exists x \in D,\ \neg P(x)$.
2. $\neg\,\exists x \in D,\ P(x) \;\equiv\; \forall x \in D,\ \neg P(x)$.
3. $\neg\,\forall x \in D,\ \bigl(P(x) \Rightarrow Q(x)\bigr) \;\equiv\; \exists x \in D,\ \bigl(P(x) \land \neg Q(x)\bigr)$.
4. $\neg\,\forall x \in A\ \exists y \in B,\ R(x, y) \;\equiv\; \exists x \in A\ \forall y \in B,\ \neg R(x, y)$.

Aturan 3 diperoleh dari aturan 1 bersama $\neg(P \Rightarrow Q) \equiv P \land \neg Q$. Aturan 4 diperoleh dengan menerapkan aturan 1 lalu aturan 2.

Ada tiga hal yang perlu diperhatikan.

Domain tidak ikut dinegasikan. Negasi dari "setiap $x \in D$ memenuhi $P$" adalah "ada $x \in D$ yang tidak memenuhi $P$". Negasinya bukan "ada $x \notin D$ …". Ini sesuai dengan singkatan pada bagian sebelumnya: $\neg \forall x\,(x \in D \Rightarrow P(x)) \equiv \exists x\,(x \in D \land \neg P(x))$.

Negasi implikasi bukan implikasi. Negasi dari "jika $P$ maka $Q$" bukan "jika $P$ maka tidak $Q$". Untuk proposisi $P$ dan $Q$, negasinya adalah $P\land\neg Q$. Jika yang dinegasikan ialah $\forall x\in D\,(P(x)\Rightarrow Q(x))$, barulah diperoleh $\exists x\in D\,(P(x)\land\neg Q(x))$: ada objek dalam domain yang memenuhi hipotesis tetapi menggagalkan kesimpulan.

Urutan kuantor dipertahankan, jenisnya ditukar. Pada aturan 4, $\forall\exists$ menjadi $\exists\forall$. Kuantor dalam $\forall y$ menuntut bahwa setiap $y$ gagal.

Contoh 6.1.6 (Negasi universal). Klaim: $\forall x \in \mathbb{R},\ x^2 \ge x$.

Negasinya adalah $\exists x \in \mathbb{R},\ x^2 < x$. Negasi ini benar dengan saksi $x = \tfrac12$:

$$x^2 = \tfrac14, \qquad x - x^2 = \tfrac12 - \tfrac14 = \tfrac14 > 0,$$

sehingga $x^2 < x$. Jadi klaim semula salah.

Perhatikan bahwa nilai seperti $x = 2$ (dengan $4 \ge 2$) atau $x = -1$ (dengan $1 \ge -1$) memenuhi klaim semula. Nilai-nilai itu tidak membuktikan klaim, dan juga tidak menghalangi bantahan oleh $x = \tfrac12$.

Contoh 6.1.7 (Negasi universal implikasi). Klaim: $\forall n \in \mathbb{Z},\ \bigl(n \text{ genap} \Rightarrow 4 \mid n\bigr)$.

Menurut aturan 3, negasinya adalah

$$\exists n \in \mathbb{Z},\ \bigl(n \text{ genap} \land 4 \nmid n\bigr).$$

Negasinya bukan "untuk setiap $n$, jika $n$ genap maka $4 \nmid n$". Kalimat itu pun salah, karena $n = 4$ genap dan $4 \mid 4$.

Saksi untuk negasi adalah $n = 2$. Bilangan $2$ genap karena $2 = 2 \cdot 1$ dengan $1 \in \mathbb{Z}$. Untuk menunjukkan $4 \nmid 2$, andaikan $2 = 4k$ untuk suatu $k \in \mathbb{Z}$. Karena tidak ada bilangan bulat di antara $0$ dan $1$ (pinjaman), berlaku $k \le 0$ atau $k \ge 1$.

• Jika $k \le 0$, maka $4k \le 0 < 2$.
• Jika $k \ge 1$, maka $4k \ge 4 > 2$.

Dalam kedua kasus $4k \neq 2$. Jadi tidak ada saksi, sehingga $4 \nmid 2$. Dengan demikian negasi benar dan klaim semula salah. Objek $n = 2$ memenuhi hipotesis "genap" dan menggagalkan kesimpulan "$4 \mid n$". Itulah bentuk kontra-contoh terhadap universal implikasi.

Contoh 6.1.8 (Pola $\forall\exists$: satu pasangan gagal tidak cukup).

(a) Klaim yang benar. Perhatikan $\forall x \in \mathbb{Z}\ \exists y \in \mathbb{Z},\ x + y = 0$. Klaim ini benar. Untuk $x$ sebarang, pilih $y = -x \in \mathbb{Z}$, sehingga $x + y = 0$.

Seseorang yang menunjuk $x = 3,\ y = 5$ dengan $3 + 5 = 8 \neq 0$ tidak membantah klaim ini. Klaim itu hanya menuntut adanya suatu $y$ yang cocok untuk setiap $x$. Klaim itu tidak menuntut bahwa setiap $y$ cocok.

(b) Klaim yang salah. Perhatikan $\forall x \in \mathbb{Z}\ \exists y \in \mathbb{Z},\ 2y = x$. Menurut aturan 4, negasinya adalah

$$\exists x \in \mathbb{Z}\ \forall y \in \mathbb{Z},\ 2y \neq x.$$

Kita buktikan negasi ini dengan saksi $x = 1$. Ambil $y \in \mathbb{Z}$ sebarang. Karena tidak ada bilangan bulat di antara $0$ dan $1$, berlaku $y \le 0$ atau $y \ge 1$.

• Jika $y \le 0$, maka $2y \le 0 < 1$.
• Jika $y \ge 1$, maka $2y \ge 2 > 1$.

Jadi $2y \neq 1$ untuk setiap $y \in \mathbb{Z}$, dan klaim semula salah.

Perhatikan bentuk bantahan ini. Satu nilai $x$ dipilih, lalu semua $y$ diperiksa. Memeriksa hanya $y = 0$ (dengan $2 \cdot 0 \neq 1$) tidak cukup.

Contoh 6.1.9 (Domain kosong). Misalkan $D = \{x \in \mathbb{R} : x^2 + 1 = 0\}$. Untuk setiap $x \in \mathbb{R}$ berlaku $x^2 \ge 0$ (pinjaman), sehingga $x^2 + 1 \ge 1 > 0$. Jadi $D = \varnothing$.

• "$\forall x \in D,\ x = 7$" benar. Negasinya, $\exists x \in D,\ x \neq 7$, menuntut adanya anggota $D$, dan $D$ tidak mempunyai anggota. Jadi negasinya salah. Dengan alasan yang sama, "$\forall x \in D,\ x \neq 7$" juga benar. Dua klaim universal ini tidak bertentangan, karena tidak ada objek yang harus memenuhi keduanya sekaligus.
• "$\exists x \in D,\ x = x$" salah, walaupun sifat $x = x$ dipenuhi oleh setiap objek. Klaim eksistensial memerlukan saksi di dalam $D$.
• Bentuk implikasi. Pernyataan $\forall x \in \mathbb{R},\ (x^2 + 1 = 0 \Rightarrow x = 7)$ benar, karena hipotesisnya salah untuk setiap $x \in \mathbb{R}$. Kebenaran implikasi ini sama sekali tidak menunjukkan bahwa $7^2 + 1 = 0$. Kebenaran itu juga tidak menunjukkan bahwa ada bilangan real yang memenuhi hipotesis.

Pelajarannya ada dua.

1. Klaim universal yang benar tidak menjamin adanya objek. Dari $\forall x \in D,\ P(x)$ kita boleh menyimpulkan $\exists x \in D,\ P(x)$ hanya jika $D \neq \varnothing$ sudah diketahui.
2. Hipotesis yang mustahil membuat implikasi benar secara vakum, tetapi tidak membuktikan kesimpulannya tanpa syarat.

---

Rantai lema, teorema, dan korolari

Bagian ini menyusun rantai kecil hasil yang benar-benar dibuktikan. Tujuannya memperlihatkan bagaimana sebuah hasil dipakai oleh hasil berikutnya.

Lema 6.1.10. Untuk setiap $a, b \in \mathbb{Z}$, jika $a$ dan $b$ genap, maka $a + b$ genap.

Strategi. Buka definisi genap untuk $a$ dan $b$ agar memperoleh dua saksi, lalu susun saksi untuk $a + b$.

Bukti. Ambil $a, b \in \mathbb{Z}$ sebarang, dan andaikan $a$ serta $b$ genap. Menurut Definisi 6.1.1(a), terdapat $k, l \in \mathbb{Z}$ dengan $a = 2k$ dan $b = 2l$. Maka

$$a + b = 2k + 2l = 2(k + l).$$

Karena $\mathbb{Z}$ tertutup terhadap penjumlahan, $k + l \in \mathbb{Z}$. Jadi $k + l$ adalah saksi bahwa $a + b$ genap. $\blacksquare$

Lema ini tidak mensyaratkan $a \neq b$. Variabel "sebarang" boleh bernilai sama, sehingga lema berlaku pula untuk $a = b$. Fakta ini dipakai pada bukti berikut.

Teorema 6.1.11. Untuk setiap $n \in \mathbb{Z}$, jika $n$ genap, maka $n^2$ genap.

Strategi. Tulis $n^2$ sebagai jumlah dua bilangan genap, lalu terapkan Lema 6.1.10.

Bukti. Ambil $n \in \mathbb{Z}$ sebarang, dan andaikan $n$ genap. Akan ditunjukkan bahwa $n^2$ genap.

Menurut Definisi 6.1.1(a), terdapat $k \in \mathbb{Z}$ dengan $n = 2k$. Maka

$$n^2 = (2k)(2k) = 4k^2 = 2k^2 + 2k^2.$$

Tulis $s = 2k^2$. Karena $\mathbb{Z}$ tertutup terhadap perkalian, $k^2 = k \cdot k \in \mathbb{Z}$ dan $s = 2(k^2) \in \mathbb{Z}$. Jadi $s$ genap dengan saksi $k^2$. Dengan demikian $n^2 = s + s$, dengan $s \in \mathbb{Z}$ genap.

Lema 6.1.10, dengan $a := s$ dan $b := s$, memberi bahwa $s + s = n^2$ genap. $\blacksquare$

Catatan. Teorema ini juga dapat dibuktikan tanpa lema: $n^2 = 2(2k^2)$ dengan saksi $2k^2 \in \mathbb{Z}$. Jadi label "teorema" tidak berarti bahwa buktinya lebih sulit daripada bukti lema. Label itu hanya menandai peran hasil ini dalam penyajian. Di sini lema dipakai agar rantai ketergantungan terlihat.

Perhatikan pula nama variabel. Pada Lema 6.1.10 huruf $a$ dan $b$ terikat oleh kuantor, sehingga kita bebas mengisinya dengan $s$. Seandainya lema ditulis dengan huruf $n$, kita tetap boleh mengisinya dengan objek lain asalkan penggantian ditulis jelas.

Korolari 6.1.12.

(a) Untuk setiap $m, n \in \mathbb{Z}$, jika $m$ dan $n$ genap, maka $m^2 + n^2$ genap.

(b) Untuk setiap $n \in \mathbb{Z}$, jika $n$ genap, maka $n^4$ genap.

Strategi. Terapkan Teorema 6.1.11 pada objek yang tepat, periksa hipotesisnya, lalu gabungkan dengan Lema 6.1.10 bila perlu.

Bukti.

(a) Ambil $m, n \in \mathbb{Z}$ sebarang yang keduanya genap. Teorema 6.1.11 diterapkan pada $m$, dan hipotesisnya ("$m$ genap") terpenuhi. Hasilnya, $m^2$ genap. Dengan cara yang sama, $n^2$ genap. Karena $m^2, n^2 \in \mathbb{Z}$ dan keduanya genap, Lema 6.1.10 dengan $a := m^2$ dan $b := n^2$ memberi bahwa $m^2 + n^2$ genap.

(b) Ambil $n \in \mathbb{Z}$ sebarang yang genap. Teorema 6.1.11 memberi bahwa $n^2$ genap. Bilangan $n^2$ adalah bilangan bulat yang genap, sehingga hipotesis Teorema 6.1.11 dipenuhi oleh $n^2$. Menerapkan teorema itu sekali lagi, kali ini pada objek $n^2$, memberi bahwa $(n^2)^2$ genap. Terakhir, $(n^2)^2 = n^4$ menurut sifat asosiatif perkalian. $\blacksquare$

Bukti korolari pendek, tetapi tetap merupakan bukti. Setiap penerapan hasil sebelumnya disertai pemeriksaan bahwa hipotesisnya terpenuhi oleh objek yang dimaksud.

Ketergantungan dalam rantai ini adalah

$$\text{Definisi 6.1.1} \;\to\; \text{Lema 6.1.10} \;\to\; \text{Teorema 6.1.11} \;\to\; \text{Korolari 6.1.12},$$

dengan Korolari 6.1.12(a) juga langsung memakai Lema 6.1.10. Tidak ada panah yang kembali ke hasil yang lebih awal. Syarat inilah yang dilanggar oleh bukti sirkular.

Konvers Teorema 6.1.11, yaitu "jika $n^2$ genap maka $n$ genap", tidak dibuktikan pada unit ini dan tidak boleh dipakai di sini. Konvers itu kebetulan benar dan akan dibuktikan di Subbab 6.3.

---

Bedah sebuah bukti sirkular

Sebuah bukti sirkular memakai kesimpulan yang hendak dibuktikan, atau sesuatu yang setara dengannya, sebagai alasan yang dianggap sudah benar tanpa diturunkan dari premis yang sah. Ini berbeda dari menuliskan sasaran sementara atau menyusun rantai ekuivalensi yang kemudian dibenarkan dari pernyataan yang telah diketahui benar. Bukti semacam ini sering tampak meyakinkan karena setiap langkah aljabarnya benar.

Contoh 6.1.13. Klaim: $\forall n \in \mathbb{Z},\ (n^2 \text{ genap} \Rightarrow n \text{ genap})$. Berikut sebuah "bukti":

(1) Ambil $n \in \mathbb{Z}$ sebarang dengan $n^2$ genap. (2) Karena $n$ genap, terdapat $k \in \mathbb{Z}$ dengan $n = 2k$. (3) Maka $n^2 = 4k^2 = 2(2k^2)$, dan $2k^2 \in \mathbb{Z}$, sehingga $n^2$ genap. (4) Jadi $n$ genap. $\blacksquare$

Titik kesalahan ada di langkah (2). Frasa "karena $n$ genap" tidak dibenarkan oleh apa pun sebelumnya. Hipotesis pada langkah (1) berbicara tentang $n^2$, bukan tentang $n$. "$n$ genap" adalah kesimpulan yang hendak dibuktikan. Langkah (2) mengandaikan kesimpulan itu.

Akibatnya:

• Langkah (3) menurunkan kembali hipotesis "$n^2$ genap", yang sudah kita miliki sejak langkah (1). Langkah (2) dan (3) bersama-sama hanyalah bukti Teorema 6.1.11, yaitu bukti konvers klaim yang dimaksud.
• Langkah (4) tidak mengikuti dari langkah (3). Langkah ini hanya mengulang asumsi langkah (2).

Jadi "bukti" ini sebenarnya menunjukkan $n \text{ genap} \Rightarrow n^2 \text{ genap}$, bukan $n^2 \text{ genap} \Rightarrow n \text{ genap}$.

Klaimnya sendiri benar; buktinya yang sah diberikan di Subbab 6.3 dan tidak dipakai di unit ini. Namun kebenaran klaim tidak menyelamatkan bukti yang tidak sah. Menilai apakah sebuah klaim benar dan menilai apakah sebuah bukti sah adalah dua pekerjaan berbeda.

Sirkularitas juga dapat tersebar di beberapa hasil. Misalkan Lema A dibuktikan dengan memakai Teorema B, sedangkan bukti Teorema B memakai Lema A. Masing-masing bukti tampak sah jika dibaca sendiri, tetapi tidak satu pun dari kedua hasil itu terbukti. Peta ketergantungan seperti yang ditulis untuk Korolari 6.1.12 membantu mendeteksi masalah ini.

---

Kesalahan umum

1. Menganggap label sebagai jaminan. Menganggap pernyataan berlabel "Teorema" pasti benar tanpa memeriksa buktinya, atau menganggap lema kurang pasti daripada teorema.
2. Menganggap konjektur salah, atau dugaan yang lolos uji sebagai benar. Konjektur belum terbukti. Pemeriksaan banyak kasus tidak menjadikannya teorema (Contoh 6.1.2).
3. Mengutip "akibatnya" tanpa memeriksa hipotesis. Korolari tetap harus menunjukkan bahwa hipotesis hasil sebelumnya dipenuhi oleh objek yang dimaksud.
4. Memperlakukan hipotesis sebagai fakta. "Andaikan $n$ genap" berlaku di dalam bukti saja, bukan untuk semua $n$.
5. Mempersempit variabel sebarang. Contohnya menulis "ambil $n$ sebarang", lalu diam-diam memakai $n > 0$ atau $n = 4$.
6. Menghilangkan domain atau syarat pembagi. Contohnya rumus pecahan yang ditulis "untuk setiap $x \in \mathbb{R}$" padahal penyebutnya bisa nol (Contoh 6.1.4).
7. Mengakhiri bukti pada pernyataan yang salah sasaran. Contohnya mengakhiri dengan konvers, atau dengan pernyataan yang hanya mirip dengan kesimpulan.
8. Menegasikan implikasi menjadi implikasi. Negasi dari $P \Rightarrow Q$ adalah $P \land \neg Q$, bukan $P \Rightarrow \neg Q$.
9. Menegasikan domain. Menulis "$\exists x \notin D$" sebagai negasi dari "$\forall x \in D$".
10. Membantah $\forall\exists$ dengan satu pasangan. Bantahan yang sah harus menunjukkan bahwa setiap $y$ gagal untuk suatu $x$ (Contoh 6.1.8).
11. Mengambil saksi dari domain kosong. Menyimpulkan adanya objek dari klaim universal, atau dari implikasi yang benar secara vakum.
12. Mengandaikan kesimpulan. Inilah bukti sirkular (Contoh 6.1.13).

---

Latihan

Tingkat 1

Latihan 6.1.14. Tulis setiap kalimat dalam bentuk berkuantor yang lengkap. Sebutkan domain, variabel terikat, serta hipotesis dan kesimpulan jika ada. Bagian (a) dan (c) tidak perlu dibuktikan; cukup lakukan anotasi.

(a) "Kuadrat bilangan bulat ganjil adalah ganjil." Di sini $n$ ganjil berarti terdapat $k \in \mathbb{Z}$ dengan $n = 2k + 1$.

(b) "Ada bilangan real yang kuadratnya sama dengan dirinya sendiri." Tentukan pula nilai kebenarannya.

(c) "Untuk bilangan bulat $a, b, c$, bila $a \mid b$ dan $a \mid c$, maka $a \mid (b + c)$."

Pembahasan.

(a) Bentuknya adalah $\forall n \in \mathbb{Z},\ (n \text{ ganjil} \Rightarrow n^2 \text{ ganjil})$.

• Domain: $\mathbb{Z}$.
• Variabel: $n$, terikat oleh $\forall$.
• Hipotesis: $\exists k \in \mathbb{Z},\ n = 2k + 1$.
• Kesimpulan: $\exists j \in \mathbb{Z},\ n^2 = 2j + 1$.

Kuantor universal tersembunyi dalam frasa generik "kuadrat bilangan bulat ganjil".

(b) Bentuknya adalah $\exists x \in \mathbb{R},\ x^2 = x$. Domainnya $\mathbb{R}$, dan variabelnya $x$, terikat oleh $\exists$. Pernyataan eksistensial ini tidak mempunyai bagian hipotesis–kesimpulan. Pernyataan ini benar dengan saksi $x = 1$: $1 \in \mathbb{R}$ dan $1^2 = 1$. Saksi $x = 0$ juga dapat dipakai.

(c) Bentuknya adalah $\forall a, b, c \in \mathbb{Z},\ \bigl((a \mid b \land a \mid c) \Rightarrow a \mid (b + c)\bigr)$.

• Domain: $\mathbb{Z}$ untuk ketiga variabel. Nilai $a = 0$ termasuk, karena Definisi 6.1.1(b) tidak memuat pembagian.
• Variabel terikat: $a, b, c$.
• Hipotesis: $a \mid b$ dan $a \mid c$. Ini sebuah konjungsi, sehingga keduanya harus dipenuhi.
• Kesimpulan: $a \mid (b + c)$.

Latihan 6.1.15. Klasifikasikan setiap butir sebagai definisi, aksioma/prasyarat pinjaman, hasil yang terbukti dalam unit ini, hipotesis di dalam sebuah bukti, konjektur, atau pernyataan yang telah dibantah. Beri alasan.

(a) "Bilangan bulat $n$ disebut ganjil jika terdapat $k \in \mathbb{Z}$ sehingga $n = 2k + 1$."

(b) "Untuk setiap $a, b \in \mathbb{R}$, $a + b = b + a$."

(c) "Untuk setiap $a, b \in \mathbb{Z}$, jika $a$ dan $b$ genap, maka $a + b$ genap."

(d) Kalimat "Andaikan $n$ genap" pada baris pertama bukti Teorema 6.1.11.

(e) "Setiap bilangan bulat genap yang lebih besar dari $2$ adalah jumlah dua bilangan prima."

(f) "Untuk setiap bilangan bulat $n \ge 0$, $n^2 + n + 41$ prima."

Pembahasan.

(a) Definisi. Butir ini menetapkan arti kata "ganjil" dan tidak perlu dibuktikan.

(b) Prasyarat pinjaman. Ini sifat medan bilangan real. Unit ini memakainya tanpa bukti. Apakah sifat itu berperan sebagai aksioma atau sebagai hasil konstruksi ditentukan di bagian lain buku.

(c) Hasil terbukti, yaitu Lema 6.1.10. Labelnya "lema", tetapi standar kebenarannya sama dengan teorema.

(d) Hipotesis yang diandaikan di dalam bukti. Kalimat itu bukan pernyataan bahwa semua bilangan bulat adalah genap, dan bukan pernyataan bahwa suatu $n$ tertentu memang genap. Kalimat itu adalah asumsi yang berlaku di dalam bukti.

(e) Konjektur (konjektur Goldbach). Dalam konteks deskripsi seminar yang dirujuk pada bagian konjektur [R6-2], pernyataan ini berstatus masalah terbuka. Statusnya bukan "salah", dan pemeriksaan banyak kasus tidak menjadikannya teorema.

(f) Pernyataan yang telah dibantah. Contoh 6.1.2 memakai $n = 40$. Saksi lain adalah $n = 41$:

$$41^2 + 41 + 41 = 41(41 + 1 + 1) = 41 \cdot 43.$$

Jadi $41$ adalah pembagi positif dengan $1 < 41 < 41 \cdot 43$, sehingga bilangan itu tidak prima. Setelah dibantah, butir ini bukan konjektur lagi.

Tingkat 2

Latihan 6.1.16. Tulis negasi setiap pernyataan dengan urutan kuantor yang benar. Kemudian tentukan mana yang benar, pernyataan asli atau negasinya, dan buktikan.

(a) $\forall x \in \mathbb{R}\ \exists y \in \mathbb{R},\ y > x$.

(b) $\exists y \in \mathbb{Z}\ \forall x \in \mathbb{Z},\ x \le y$.

(c) $\forall n \in \mathbb{Z},\ (n \text{ genap} \Rightarrow 4 \mid n^2)$.

Pembahasan.

(a) Negasinya adalah $\exists x \in \mathbb{R}\ \forall y \in \mathbb{R},\ y \le x$.

Pernyataan asli benar. Ambil $x \in \mathbb{R}$ sebarang, dan pilih $y = x + 1 \in \mathbb{R}$. Maka $y - x = 1 > 0$, sehingga $y > x$. Karena $x$ sebarang, pernyataan asli terbukti, dan negasinya salah.

(b) Negasinya adalah $\forall y \in \mathbb{Z}\ \exists x \in \mathbb{Z},\ x > y$.

Negasi ini benar. Ambil $y \in \mathbb{Z}$ sebarang, dan pilih $x = y + 1$. Maka $x \in \mathbb{Z}$ karena $\mathbb{Z}$ tertutup terhadap penjumlahan, dan $x - y = 1 > 0$. Jadi pernyataan asli, yang mengklaim ada bilangan bulat terbesar, salah.

Menukar urutan kuantor dapat mengubah makna. Pada $\mathbb{Z}$, pernyataan $\forall x\ \exists y,\ x \le y$ benar (pilih $y = x$), sedangkan $\exists y\ \forall x,\ x \le y$ salah menurut bagian (b). Pada pernyataan pertama $y$ boleh bergantung pada $x$; pada pernyataan kedua satu $y$ harus melayani semua $x$.

(c) Negasinya adalah $\exists n \in \mathbb{Z},\ (n \text{ genap} \land 4 \nmid n^2)$.

Pernyataan asli benar. Ambil $n \in \mathbb{Z}$ sebarang yang genap, sehingga $n = 2k$ dengan $k \in \mathbb{Z}$. Maka $n^2 = 4k^2 = 4 \cdot k^2$ dengan $k^2 \in \mathbb{Z}$. Menurut Definisi 6.1.1(b), $4 \mid n^2$ dengan saksi $k^2$. Jadi negasinya salah.

Latihan 6.1.17. Perhatikan klaim: "Untuk setiap $a, b, c \in \mathbb{R}$, jika $ab = ac$, maka $b = c$."

(a) Tunjukkan bahwa klaim ini salah dengan kontra-contoh yang memenuhi semua hipotesis.

(b) Tambahkan syarat yang hilang.

(c) Buktikan klaim yang telah diperbaiki.

Pembahasan.

(a) Ambil $a = 0$, $b = 1$, $c = 2$. Ketiganya berada dalam $\mathbb{R}$. Hipotesis dipenuhi karena $ab = 0 \cdot 1 = 0$ dan $ac = 0 \cdot 2 = 0$, sehingga $ab = ac$. Kesimpulan gagal karena $b = 1 \neq 2 = c$. Jadi klaim semula salah.

(b) Syarat yang hilang adalah $a \neq 0$. Klaim yang diperbaiki berbunyi: untuk setiap $a, b, c \in \mathbb{R}$, jika $a \neq 0$ dan $ab = ac$, maka $b = c$. "Mencoret $a$" pada kedua ruas secara diam-diam adalah membagi dengan $a$, dan langkah itu memerlukan $a \neq 0$.

(c) Bukti. Ambil $a, b, c \in \mathbb{R}$ sebarang dengan $a \neq 0$ dan $ab = ac$. Maka

$$ab - ac = 0, \quad\text{sehingga}\quad a(b - c) = 0$$

menurut sifat distributif. Karena $\mathbb{R}$ tidak mempunyai pembagi nol (pinjaman), berlaku $a = 0$ atau $b - c = 0$. Kemungkinan pertama bertentangan dengan hipotesis $a \neq 0$. Jadi $b - c = 0$, yaitu $b = c$. $\blacksquare$

Syarat $a \neq 0$ dipakai tepat satu kali, yaitu untuk menyingkirkan kemungkinan $a = 0$.

Latihan 6.1.18. Perhatikan kalimat "Untuk setiap $a, b \in \mathbb{R}$, $\dfrac{a}{b} \cdot b = a$."

(a) Jelaskan mengapa kalimat ini bermasalah pada domain yang disebutkan. Apakah masalahnya sama dengan masalah pada klaim yang dibantah oleh kontra-contoh di Latihan 6.1.17?

(b) Rumuskan domain yang tepat dan buktikan kalimatnya.

Pembahasan.

(a) Untuk $b = 0$, ungkapan $\dfrac{a}{0}$ tidak terdefinisi. Jadi ruas kiri tidak memiliki nilai, dan kalimat itu tidak bermakna untuk pasangan $(a, 0)$.

Masalah ini berbeda dari Latihan 6.1.17(a). Di sana kedua ruas bermakna dan dapat dihitung, lalu kesimpulannya ternyata gagal. Di sini, untuk $b = 0$, tidak ada nilai yang dapat dibandingkan sama sekali. Keduanya diperbaiki dengan menuliskan syarat $\neq 0$ secara eksplisit. Di Latihan 6.1.17 syarat itu menjadi hipotesis tambahan, sedangkan di sini syarat itu membatasi domain agar ruas kiri terdefinisi.

(b) Rumusan yang tepat adalah: untuk setiap $a \in \mathbb{R}$ dan setiap $b \in \mathbb{R} \setminus \{0\}$, $\dfrac{a}{b} \cdot b = a$.

Bukti. Ambil $a \in \mathbb{R}$ dan $b \in \mathbb{R} \setminus \{0\}$ sebarang. Karena $b \neq 0$, invers $b^{-1}$ ada, dan $\dfrac{a}{b}$ berarti $a b^{-1}$ (pinjaman sifat medan). Maka

$$\frac{a}{b} \cdot b = (a b^{-1}) b = a (b^{-1} b) = a \cdot 1 = a. \qquad \blacksquare$$

Latihan 6.1.19. Misalkan $D = \{x \in \mathbb{R} : x^2 < 0\}$.

(a) Tunjukkan bahwa $D = \varnothing$.

(b) Tentukan nilai kebenaran "$\forall x \in D,\ x > 100$" dan "$\exists x \in D,\ x > 100$". Beri alasan.

(c) Seorang mahasiswa menulis: "Karena $\forall x \in D,\ x > 100$ benar, ambil $x \in D$. Maka $x > 100$. Jadi ada bilangan dalam $D$ yang lebih besar dari $100$." Di mana kesalahannya?

(d) Apakah "$\forall x \in D,\ x > 100$" dan "$\forall x \in D,\ x < 0$" saling bertentangan?

Pembahasan.

(a) Untuk setiap $x \in \mathbb{R}$ berlaku $x^2 \ge 0$ (pinjaman). Jadi tidak ada $x \in \mathbb{R}$ dengan $x^2 < 0$, sehingga $D = \varnothing$.

(b) Pernyataan "$\forall x \in D,\ x > 100$" benar secara vakum. Negasinya, $\exists x \in D,\ x \le 100$, memerlukan anggota $D$, padahal $D$ kosong. Jadi negasinya salah.

Pernyataan "$\exists x \in D,\ x > 100$" salah, karena tidak ada saksi di dalam $D$.

(c) Kesalahannya ada pada langkah "ambil $x \in D$". Langkah itu mengandaikan bahwa $D$ mempunyai anggota. Kebenaran klaim universal tidak memberi informasi tentang adanya anggota. Untuk menyimpulkan $\exists x \in D,\ x > 100$ dari $\forall x \in D,\ x > 100$, kita memerlukan fakta tambahan $D \neq \varnothing$, dan fakta itu salah di sini.

(d) Keduanya tidak bertentangan. Keduanya benar secara vakum, karena tidak ada anggota $D$ yang harus memenuhi $x > 100$ dan $x < 0$ sekaligus.

Seandainya $D$ mempunyai suatu anggota $x_0$, kedua pernyataan akan memberi $x_0 > 100$ dan $x_0 < 0$. Hal ini mustahil karena $100 > 0$. Jadi kedua klaim universal itu dapat benar bersamaan hanya ketika domainnya kosong.

Latihan 6.1.20. Seorang mahasiswa membantah klaim $\forall x \in \mathbb{Z}\ \exists y \in \mathbb{Z},\ x + y = 0$ dengan menulis: "Ambil $x = 2$ dan $y = 3$. Maka $x + y = 5 \neq 0$, jadi klaim itu salah."

(a) Jelaskan kesalahannya, lalu tulis negasi klaim tersebut.

(b) Perhatikan klaim yang sama dengan domain bilangan bulat positif $\mathbb{Z}^{+} = \{n \in \mathbb{Z} : n > 0\}$, yaitu $\forall x \in \mathbb{Z}^{+}\ \exists y \in \mathbb{Z}^{+},\ x + y = 0$. Tentukan nilai kebenarannya dan buktikan.

Pembahasan.

(a) Klaim itu hanya menuntut adanya suatu $y$ untuk setiap $x$. Untuk $x = 2$, nilai $y = -2$ memenuhi $x + y = 0$. Kegagalan $y = 3$ tidak relevan. Negasi klaim tersebut adalah

$$\exists x \in \mathbb{Z}\ \forall y \in \mathbb{Z},\ x + y \neq 0.$$

Negasi ini salah, karena untuk setiap $x \in \mathbb{Z}$, pilihan $y = -x \in \mathbb{Z}$ memberi $x + y = 0$ (Contoh 6.1.8(a)). Jadi klaim semula benar.

(b) Klaim ini salah. Negasinya adalah

$$\exists x \in \mathbb{Z}^{+}\ \forall y \in \mathbb{Z}^{+},\ x + y \neq 0.$$

Pilih $x = 1 \in \mathbb{Z}^{+}$. Ambil $y \in \mathbb{Z}^{+}$ sebarang. Karena $y > 0$ dan tidak ada bilangan bulat di antara $0$ dan $1$, berlaku $y \ge 1$. Maka $1 + y \ge 2 > 0$, sehingga $1 + y \neq 0$. Karena $y$ sebarang, negasi terbukti.

Domain mengubah status klaim. Saksi $y = -x$ yang bekerja pada $\mathbb{Z}$ tidak berada di $\mathbb{Z}^{+}$, sehingga tidak dapat dipakai.

Tingkat 3

Latihan 6.1.21. Bagian ini menyusun rantai baru dari lema ke korolari.

(a) Buktikan lema: untuk setiap $m, n \in \mathbb{Z}$, jika $n$ genap, maka $mn$ genap.

(b) Turunkan korolari: untuk setiap $n \in \mathbb{Z}$, jika $n$ genap, maka $n^3$ genap. Tuliskan secara eksplisit bagaimana hipotesis lema dipenuhi.

(c) Jelaskan mengapa Teorema 6.1.11 merupakan kasus khusus dari lema (a). Apa yang ditunjukkan hal ini tentang label "lema" dan "teorema"?

Pembahasan.

(a) Bukti. Ambil $m, n \in \mathbb{Z}$ sebarang, dan andaikan $n$ genap. Maka $n = 2k$ untuk suatu $k \in \mathbb{Z}$, sehingga

$$mn = m(2k) = 2(mk).$$

Karena $\mathbb{Z}$ tertutup terhadap perkalian, $mk \in \mathbb{Z}$. Jadi $mk$ adalah saksi bahwa $mn$ genap. $\blacksquare$

Perhatikan bahwa lema ini tidak memberi syarat apa pun pada $m$.

(b) Bukti. Ambil $n \in \mathbb{Z}$ sebarang yang genap. Korolari diturunkan dengan dua kali menerapkan lema (a).

• Penerapan pertama. Ambil $m := n$. Hipotesis lema, yaitu "$n$ genap", terpenuhi. Hasilnya, $n \cdot n = n^2$ genap.
• Penerapan kedua. Ambil $m := n^2$, yang berada dalam $\mathbb{Z}$ karena $\mathbb{Z}$ tertutup terhadap perkalian. Hipotesis lema kembali terpenuhi oleh $n$, karena $n$ genap. Hasilnya, $n^2 \cdot n$ genap.

Menurut sifat asosiatif perkalian, $n^2 \cdot n = n^3$. Jadi $n^3$ genap. $\blacksquare$

Penerapan pertama sebenarnya tidak diperlukan. Lema hanya menuntut bahwa faktor $n$ genap, sedangkan $n^2 \in \mathbb{Z}$ sudah cukup sebagai faktor $m$ tanpa perlu diketahui genap. Mengenali hipotesis mana yang benar-benar dipakai adalah bagian dari membaca anatomi sebuah hasil.

(c) Dengan mengambil $m := n$ pada lema (a), kita memperoleh: jika $n$ genap, maka $n \cdot n = n^2$ genap. Ini persis Teorema 6.1.11.

Jadi dalam penyajian ini sebuah "lema" lebih umum daripada sebuah "teorema". Label menyatakan peran yang dipilih penulis, bukan kekuatan logis atau tingkat kesulitan.

Latihan 6.1.22. Perhatikan klaim: "Untuk setiap $m, n \in \mathbb{Z}$, jika $m + n$ genap dan $m$ genap, maka $n$ genap." Berikut sebuah "bukti":

(1) Ambil $m, n \in \mathbb{Z}$ dengan $m + n$ genap dan $m$ genap. (2) Karena $m$ dan $n$ genap, Lema 6.1.10 memberi bahwa $m + n$ genap, sesuai dengan hipotesis. (3) Jadi $n$ genap. $\blacksquare$

(a) Tunjukkan baris yang memuat kesalahan dan jelaskan jenis kesalahannya.

(b) Tulis bukti yang sah.

Pembahasan.

(a) Kesalahan ada di baris (2). Frasa "$m$ dan $n$ genap" memakai "$n$ genap", padahal itulah kesimpulan yang hendak dibuktikan. Hipotesis hanya memberi "$m + n$ genap" dan "$m$ genap". Jadi ini bukti sirkular.

Penerapan Lema 6.1.10 di baris (2) hanya menurunkan kembali hipotesis "$m + n$ genap", sehingga tidak menghasilkan informasi baru. Baris (3) tidak mengikuti dari baris (2). Baris (3) hanya mengulang asumsi yang diselundupkan di baris (2).

(b) Strategi. Nyatakan $n$ sebagai selisih dua bilangan yang diketahui genap, lalu susun saksinya.

Bukti. Ambil $m, n \in \mathbb{Z}$ sebarang dengan $m + n$ genap dan $m$ genap. Maka terdapat $j, k \in \mathbb{Z}$ dengan $m + n = 2j$ dan $m = 2k$. Akibatnya

$$n = (m + n) - m = 2j - 2k = 2(j - k).$$

Karena $\mathbb{Z}$ tertutup terhadap pengurangan, $j - k \in \mathbb{Z}$. Jadi $j - k$ adalah saksi bahwa $n$ genap. $\blacksquare$

Latihan 6.1.23. Perhatikan klaim: "Untuk setiap $n \in \mathbb{Z}$, jika $4 \mid n$, maka $n$ genap." Berikut sebuah draf bukti:

Ambil $n \in \mathbb{Z}$ genap, sehingga $n = 2k$ dengan $k \in \mathbb{Z}$. Maka $n = 2k$, … sehingga $4 \mid n$. $\blacksquare$

(a) Jelaskan apa yang sebenarnya hendak dibuktikan oleh draf ini, dan mengapa draf ini tidak membuktikan klaim.

(b) Tunjukkan bahwa pernyataan yang hendak dibuktikan oleh draf itu sebenarnya salah.

(c) Tulis bukti klaim yang sah.

Pembahasan.

(a) Draf ini mengandaikan "$n$ genap" dan berupaya berakhir pada "$4 \mid n$". Jadi draf ini menyasar konvers klaim, yaitu $\forall n \in \mathbb{Z},\ (n \text{ genap} \Rightarrow 4 \mid n)$. Draf ini memakai kesimpulan klaim sebagai hipotesis dan hipotesis klaim sebagai sasaran; peran keduanya tertukar. Karena itu, sekalipun langkah-langkahnya lengkap, draf ini tidak akan pernah membuktikan klaim yang diminta.

(b) Konvers itu salah. Kontra-contohnya adalah $n = 2$. Bilangan $2$ genap dengan saksi $1$, tetapi $4 \nmid 2$, sebagaimana ditunjukkan di Contoh 6.1.7. Jadi titik-titik pada draf tidak dapat diisi dengan argumen apa pun yang sah.

(c) Bukti. Ambil $n \in \mathbb{Z}$ sebarang dengan $4 \mid n$. Menurut Definisi 6.1.1(b), terdapat $k \in \mathbb{Z}$ dengan $n = 4k$. Maka

$$n = 2(2k).$$

Karena $2k \in \mathbb{Z}$, bilangan $2k$ adalah saksi bahwa $n$ genap. $\blacksquare$

Baris terakhir menyatakan tepat kesimpulan klaim, yaitu "$n$ genap" beserta saksinya.

---

Menuju 6.2

Bukti hasil-hasil utama di unit ini (Lema 6.1.10, Teorema 6.1.11, Korolari 6.1.12, serta Latihan 6.1.16(c), 6.1.21, 6.1.22(b), dan 6.1.23(c)) mengikuti pola yang sama.

1. Tulis klaim dalam bentuk $\forall x \in D,\ (P(x) \Rightarrow Q(x))$.
2. Ambil $x \in D$ sebarang dan andaikan $P(x)$.
3. Buka definisi untuk memperoleh saksi.
4. Susun objek atau saksi baru dengan operasi yang sah pada domainnya.
5. Akhiri dengan $Q(x)$ yang dinyatakan persis.

Pola ini disebut pembuktian langsung. Subbab 6.2 membahasnya secara khusus. Pembahasan itu mencakup arah setiap langkah aljabar, syarat yang diperlukan ketika membagi atau mengalikan silang, keterbagian lewat saksi, kesamaan himpunan lewat dua inklusi, dan ketertutupan $\mathbb{Q}$ terhadap operasi aritmetika.

Pernyataan "jika $n^2$ genap maka $n$ genap", yang buktinya kita bedah sebagai contoh sirkular, sengaja dibiarkan terbuka di sini. Hipotesisnya memberi saksi $j$ dengan $n^2 = 2j$, tetapi saksi itu tidak langsung menghasilkan saksi bagi $n$. Klaim tersebut dibuktikan dengan kontraposisi pada Subbab 6.3.

6.2 Pembuktian Langsung (Direct Proof)

Motivasi: mengapa contoh tidak cukup

Perhatikan klaim "jumlah dua bilangan bulat genap selalu genap". Kita dapat menghitung $2+4=6$, $10+(-6)=4$, dan $0+18=18$. Ketiga hasilnya genap. Namun klaim itu membicarakan setiap pasangan bilangan bulat genap, dan banyaknya pasangan tersebut tak hingga. Seratus atau sejuta contoh hanya memeriksa seratus atau sejuta pasangan. Pasangan lain belum tersentuh.

Pembuktian langsung mengatasi hal ini dengan bernalar tentang objek sebarang. Objek sebarang dipilih tanpa mengasumsikan sifat khusus selain keanggotaannya dalam domain dan hipotesis yang dinyatakan. Satu-satunya informasi tentangnya ialah bahwa ia berada dalam domain dan memenuhi hipotesis. Apa pun yang berhasil diturunkan untuk objek seperti itu berlaku untuk setiap objek yang memenuhi syarat yang sama. Unit ini menunjukkan cara kerja metode tersebut pada isi matematika yang nyata, yaitu paritas, keterbagian, himpunan, fungsi, dan bilangan rasional.

Rumusan metode

Banyak teorema berbentuk

$$\forall x\in D,\; \bigl(P(x)\Rightarrow Q(x)\bigr).$$

Implikasi $P(x)\Rightarrow Q(x)$ hanya dapat salah bila $P(x)$ benar dan $Q(x)$ salah. Oleh karena itu, kita cukup memeriksa objek yang memenuhi $P$. Objek yang tidak memenuhi $P$ membuat implikasinya benar dengan sendirinya. Pembuktian langsung mengikuti pola berikut.

1. Ambil objek sebarang. Tulis "Ambil $x\in D$ sebarang dan misalkan $P(x)$." Sejak titik ini, $x$ tidak boleh diganti dengan nilai tertentu yang kebetulan nyaman.
2. Buka definisi hipotesis. Tuliskan arti $P(x)$ menurut definisinya. Definisi seperti "genap", "membagi", atau "rasional" berbentuk eksistensial ("ada $k\in\mathbb Z$ sehingga ..."). Membukanya memberi kita sebuah saksi, yaitu objek yang dijamin ada dan kita beri nama baru. Tentang saksi itu kita hanya mengetahui apa yang dinyatakan definisi, misalnya $k\in\mathbb Z$ dan $n=2k$.
3. Turunkan rantai implikasi yang sah. Setiap langkah harus mengikuti dari langkah sebelumnya beserta fakta yang tersedia. Arah langkah penting. Kita memerlukan "jika baris ini benar, maka baris berikutnya benar". Kita tidak memerlukan kebalikannya.
4. Bentuk kesimpulan menurut definisinya. Jika $Q(x)$ juga berbentuk eksistensial, kita harus menyusun saksi baru dan memeriksa bahwa saksi itu berada dalam himpunan yang dituntut definisi, misalnya $\mathbb Z$.
5. Tutup. Karena $x$ sebarang, pernyataan universal terbukti.

Dalam bukti langsung kita memakai kata "misalkan" untuk hipotesis yang diasumsikan. Kata "andaikan" lebih sering dipakai untuk asumsi yang hendak dibawa ke kontradiksi, yang dibahas di Unit 6.3.

Fakta yang dipinjam

Unit ini tidak membangun sistem bilangan. Fakta berikut dipinjam sebagai bahan contoh:

• (F1) $\mathbb Z$ tertutup terhadap penjumlahan, pengurangan, dan perkalian.
• (F2) Operasi medan pada $\mathbb R$ berlaku, dan $\mathbb Z\subseteq\mathbb R$. Setiap $b\in\mathbb R$ dengan $b\ne 0$ mempunyai invers tunggal $b^{-1}$, dan $\dfrac{a}{b}$ berarti $a\,b^{-1}$.
• (F3) Tidak ada pembagi nol: jika $x,y\in\mathbb R$ dan $xy=0$, maka $x=0$ atau $y=0$. Secara setara, jika $x\ne0$ dan $y\ne0$, maka $xy\ne0$. Karena $\mathbb Z\subseteq\mathbb R$, fakta ini berlaku pula untuk bilangan bulat.
• (F4) Setiap $m\in\mathbb Z$ memenuhi $m\le 0$ atau $m\ge 1$. Selain itu berlaku sifat urutan biasa pada $\mathbb R$, termasuk bahwa perkalian dengan bilangan positif mempertahankan urutan.

Arah langkah dalam rantai implikasi

Langkah yang sah satu arah belum tentu sah dua arah. Untuk $x\in\mathbb R$, implikasi $x=-3\Rightarrow x^2=9$ benar, tetapi $x^2=9\Rightarrow x=-3$ salah karena $x=3$ memenuhi hipotesis dan menggagalkan kesimpulan. Demikian pula, untuk $a,b,c\in\mathbb R$, implikasi $a=b\Rightarrow ac=bc$ selalu benar. Sebaliknya, $ac=bc\Rightarrow a=b$ memerlukan syarat $c\neq 0$. Dengan syarat itu, $ac=bc$ memberi $(a-b)c=0$, dan karena (F3) serta $c\ne 0$, diperoleh $a-b=0$. Tanpa syarat itu, $a=1$, $b=2$, $c=0$ memenuhi $ac=bc$ padahal $a\ne b$. Dalam bukti langsung, tanda $\Leftrightarrow$ hanya boleh ditulis jika kedua arah memang telah diperiksa.

Definisi kerja

Kegenapan dan keterbagian berikut mengingatkan Definisi 6.1.1 (serta Definisi 4.3.5). Contoh paritas dan konvers dari Unit 6.1 dibahas ulang untuk menelaah langkah metode langsung secara rinci.

Definisi 6.2.1 (genap dan ganjil). Bilangan $n\in\mathbb Z$ disebut genap jika ada $k\in\mathbb Z$ sehingga $n=2k$. Bilangan $n\in\mathbb Z$ disebut ganjil jika ada $k\in\mathbb Z$ sehingga $n=2k+1$.

Unit ini tidak memakai fakta bahwa setiap bilangan bulat tepat salah satu dari genap atau ganjil. Fakta itu memerlukan pembagian dengan sisa dan baru dipakai di Unit 6.3.

Definisi 6.2.2 (keterbagian). Untuk $a,b\in\mathbb Z$, kita menulis $a\mid b$ ("$a$ membagi $b$") jika ada $k\in\mathbb Z$ sehingga $b=ak$.

Perlu dicatat bahwa $a\mid b$ adalah sebuah pernyataan, bukan bilangan $b/a$. Definisi ini tidak memuat pembagian, sehingga berlaku juga untuk $a=0$. Pernyataan $0\mid b$ benar tepat ketika $b=0$, sebab $0\cdot k=0$ untuk setiap $k$. Pernyataan $a\mid 0$ benar untuk setiap $a$, karena saksinya $k=0$.

Definisi 6.2.3 (bilangan rasional). Bilangan $r\in\mathbb R$ disebut rasional, ditulis $r\in\mathbb Q$, jika ada $a,b\in\mathbb Z$ dengan $b\ne 0$ sehingga $r=\dfrac ab$.

Setiap $n\in\mathbb Z$ rasional karena $n=\dfrac n1$ dan $1\ne0$. Representasi $r=a/b$ tidak tunggal, misalnya $\tfrac12=\tfrac24$. Bukti di bawah berlaku untuk representasi mana pun yang dipilih.

Paritas: saksi bilangan bulat

Lema 6.2.4. Untuk setiap $m,n\in\mathbb Z$, jika $m$ dan $n$ genap, maka $m+n$ genap.

Strategi. Hipotesisnya memuat dua pernyataan eksistensial, sehingga kita memperoleh dua saksi. Kedua saksi itu harus diberi nama berbeda, karena $m$ dan $n$ tidak harus sama. Targetnya juga eksistensial, sehingga kita perlu menyusun satu saksi bulat untuk $m+n$.

Bukti. Ambil $m,n\in\mathbb Z$ sebarang dan misalkan keduanya genap. Menurut Definisi 6.2.1, ada $k\in\mathbb Z$ dengan $m=2k$, dan ada $l\in\mathbb Z$ dengan $n=2l$. Maka

$$m+n=2k+2l=2(k+l).$$

Menurut (F1), $k+l\in\mathbb Z$. Jadi $m+n=2j$ dengan $j=k+l\in\mathbb Z$, sehingga $m+n$ genap. Karena $m$ dan $n$ sebarang, lema terbukti. $\blacksquare$

Teorema 6.2.5. Untuk setiap $n\in\mathbb Z$, jika $n$ genap, maka $n^2$ genap.

Strategi. Buka definisi genap untuk $n$. Kuadratkan bentuk yang diperoleh. Kemudian tulis hasilnya sebagai $2\cdot(\text{bilangan bulat})$ dan sebutkan mengapa faktor tersebut bulat.

Bukti. Ambil $n\in\mathbb Z$ sebarang dan misalkan $n$ genap. Ada $k\in\mathbb Z$ dengan $n=2k$. Maka

$$n^2=(2k)^2=4k^2=2(2k^2).$$

Menurut (F1), $k^2=k\cdot k\in\mathbb Z$ dan $2k^2=2\cdot k^2\in\mathbb Z$. Jadi $n^2=2j$ dengan saksi $j=2k^2\in\mathbb Z$, sehingga $n^2$ genap. $\blacksquare$

Catatan. Bukti ini tidak memakai $n/2$. Pecahan $n/2$ adalah bilangan rasional, dan pernyataan "$n/2$ bulat" hanyalah cara lain menyebut $n$ genap. Jika pernyataan itu dipakai sebagai titik awal, kita belum membuka definisi, melainkan hanya mengulang hipotesis dengan kata lain. Perhatikan pula bahwa Lema 6.2.4 tidak dipakai dalam bukti Teorema 6.2.5. Label "lema" mencerminkan peran penyajian (lihat Unit 6.1), bukan ketergantungan logis dalam unit ini. Bukti alternatif $n^2=n\cdot n=n(2k)=2(nk)$ dengan $nk\in\mathbb Z$ juga sah. Bukti alternatif itu bahkan menunjukkan bahwa hasil kali bilangan genap dengan bilangan bulat apa pun selalu genap.

Keterbagian: saksi menggantikan pecahan

Teorema 6.2.6 (transitivitas keterbagian). Untuk setiap $a,b,c\in\mathbb Z$, jika $a\mid b$ dan $b\mid c$, maka $a\mid c$.

Draf analisis. Kita mencari $j\in\mathbb Z$ dengan $c=aj$. Dari hipotesis diperoleh $c=bl$ dan $b=ak$, sehingga $c=(ak)l$. Calon saksinya adalah $j=kl$. Draf ini belum menjadi bukti. Bukti final menyatakan calon saksi tersebut lalu memeriksanya.

Bukti. Ambil $a,b,c\in\mathbb Z$ sebarang dan misalkan $a\mid b$ dan $b\mid c$. Menurut Definisi 6.2.2, ada $k\in\mathbb Z$ dengan $b=ak$, dan ada $l\in\mathbb Z$ dengan $c=bl$. Substitusi menghasilkan

$$c=bl=(ak)l=a(kl).$$

Menurut (F1), $kl\in\mathbb Z$. Jadi $c=aj$ dengan saksi $j=kl\in\mathbb Z$, sehingga $a\mid c$. $\blacksquare$

Kasus pembagi nol. Bukti di atas tidak pernah membagi, sehingga berlaku tanpa pengecualian. Jika $a=0$ dan hipotesisnya benar, maka $b=0\cdot k=0$ dan $c=0\cdot l=0$. Kesimpulannya, $0\mid 0$, memang benar, dengan saksi $j=kl$ sebagaimana dalam bukti. Kita tidak perlu memisahkan kasus ini.

Contoh 6.2.7 (bukti pecahan yang ilegal). Perhatikan "bukti" berikut.

Karena $a\mid b$, $\frac ba=k$ bulat. Karena $b\mid c$, $\frac cb=l$ bulat. Maka $\frac ca=\frac cb\cdot\frac ba=lk$ bulat.

Argumen ini gagal pada kasus yang sebenarnya tercakup dalam teorema.

• Jika $a=0$, hipotesis memaksa $b=c=0$, dan baris pertama memuat $0/0$, yang tidak terdefinisi. Padahal kesimpulan $0\mid0$ benar.
• Jika $a=5$, $b=0$, dan $c=0$, maka $5\mid0$ dan $0\mid0$ keduanya benar. Namun $c/b=0/0$ tidak terdefinisi, sedangkan kesimpulan $5\mid 0$ benar.

Selain itu, "$b/a$ bulat" bukan definisi $a\mid b$, melainkan rumusan ulang yang baru bermakna setelah $a\ne0$ dijamin. Bukti melalui saksi menghindari semua masalah ini karena hanya memakai perkalian dalam $\mathbb Z$.

Kesamaan himpunan: dua inklusi

Untuk himpunan $X$ dan $Y$, $X=Y$ berarti $X\subseteq Y$ dan $Y\subseteq X$. Masing-masing inklusi adalah pernyataan universal-implikatif: $X\subseteq Y$ berarti $\forall x\,(x\in X\Rightarrow x\in Y)$. Jadi strateginya mengikuti bentuk target: dua bukti langsung, satu untuk setiap arah.

Proposisi 6.2.8. Misalkan

$$A=\{n\in\mathbb Z: 6\mid n\},\quad B=\{n\in\mathbb Z: 2\mid n\},\quad C=\{n\in\mathbb Z: 3\mid n\}.$$

Maka $A=B\cap C$.

Strategi. Arah $\subseteq$ cukup dengan menata ulang saksi. Arah $\supseteq$ lebih menarik. Dari $n=2k$ dan $n=3l$, kita perlu menghasilkan $n=6j$. Draf analisis memperlihatkan bahwa $1=3-2$, sehingga $n=3n-2n$. Pada suku $3n$ kita memakai saksi $n=2k$, dan pada suku $2n$ kita memakai saksi $n=3l$. Hasilnya, kedua suku menjadi kelipatan 6.

Bukti. ($A\subseteq B\cap C$.) Ambil $n\in A$ sebarang. Maka $n\in\mathbb Z$ dan ada $m\in\mathbb Z$ dengan $n=6m$. Dari $n=2(3m)$ dengan $3m\in\mathbb Z$ diperoleh $2\mid n$, sehingga $n\in B$. Dari $n=3(2m)$ dengan $2m\in\mathbb Z$ diperoleh $3\mid n$, sehingga $n\in C$. Jadi $n\in B\cap C$.

($B\cap C\subseteq A$.) Ambil $n\in B\cap C$ sebarang. Maka $n\in\mathbb Z$, dan ada $k,l\in\mathbb Z$ dengan $n=2k$ dan $n=3l$. Akibatnya,

$$n=3n-2n=3(2k)-2(3l)=6k-6l=6(k-l).$$

Menurut (F1), $k-l\in\mathbb Z$, sehingga $6\mid n$ dan $n\in A$.

Kedua inklusi berlaku, jadi $A=B\cap C$. $\blacksquare$

Diagram Venn dapat membantu memahami pernyataan ini, tetapi tidak membuktikannya. Diagram hanya menggambarkan susunan daerah. Diagram tidak memeriksa mengapa suatu $n$ yang habis dibagi 2 dan 3 juga habis dibagi 6.

Fungsi: komposisi injeksi bertipe

Kita memakai definisi dari bab fungsi: $f:A\to B$ injektif jika untuk setiap $x_1,x_2\in A$, $f(x_1)=f(x_2)$ mengakibatkan $x_1=x_2$. Untuk $f:A\to B$ dan $g:B\to C$, komposisi $g\circ f:A\to C$ didefinisikan oleh $(g\circ f)(x)=g(f(x))$. Komposisi ini terdefinisi karena setiap nilai $f(x)$ berada dalam $B$, yaitu domain $g$.

Teorema 6.2.9. Misalkan $f:A\to B$ dan $g:B\to C$ keduanya injektif. Maka $g\circ f:A\to C$ injektif.

Strategi. Target "$g\circ f$ injektif" adalah pernyataan universal-implikatif tentang pasangan anggota $A$. Ambil pasangan sebarang yang nilainya sama di bawah $g\circ f$. Kemudian lepaskan $g$ lebih dahulu karena $g$ berada di lapisan luar, baru lepaskan $f$.

Bukti. Ambil $x_1,x_2\in A$ sebarang dan misalkan $(g\circ f)(x_1)=(g\circ f)(x_2)$, yaitu $g(f(x_1))=g(f(x_2))$. Karena $f(x_1),f(x_2)\in B$ dan $g$ injektif pada $B$, diperoleh $f(x_1)=f(x_2)$. Karena $x_1,x_2\in A$ dan $f$ injektif pada $A$, diperoleh $x_1=x_2$. Jadi $g\circ f$ injektif. $\blacksquare$

Tipe fungsi dipakai secara nyata dalam bukti ini. Injektivitas $g$ hanya dapat diterapkan pada anggota domain $g$, dan langkah itu sah karena $f(x_1)$ dan $f(x_2)$ berada dalam $B$.

Lema penutupan $\mathbb Q$

Lema berikut akan dipakai di Unit 6.3 untuk membuktikan bahwa jumlah bilangan rasional dan bilangan irasional selalu irasional. Semua penyebut harus diperiksa tidak nol, karena pemeriksaan itulah yang membuat setiap pecahan bermakna.

Lema 6.2.10 (penutupan $\mathbb Q$). Misalkan $r,s\in\mathbb Q$ dengan $r=\dfrac ab$ dan $s=\dfrac cd$, di mana $a,b,c,d\in\mathbb Z$, $b\ne0$, dan $d\ne0$. Maka:

1. $bd\ne 0$, dan

$$r+s=\frac{ad+bc}{bd},\qquad r-s=\frac{ad-bc}{bd},\qquad rs=\frac{ac}{bd},$$

dengan $ad+bc,\ ad-bc,\ ac,\ bd\in\mathbb Z$. Jadi $r+s,\ r-s,\ rs\in\mathbb Q$. 2. Jika $s\ne0$, maka $c\ne0$, $bc\ne0$, dan

$$\frac rs=\frac{ad}{bc},$$

dengan $ad,\ bc\in\mathbb Z$. Jadi $r/s\in\mathbb Q$.

Karena setiap bilangan rasional mempunyai representasi seperti itu menurut Definisi 6.2.3, $\mathbb Q$ tertutup terhadap penjumlahan, pengurangan, perkalian, dan pembagian oleh bilangan rasional yang tidak nol.

Strategi. Buka definisi rasional untuk $r$ dan $s$ sehingga diperoleh empat saksi bulat. Hitung dalam $\mathbb R$ dengan operasi medan (F2). Untuk setiap hasil, tunjukkan dua hal: pembilangnya bulat menurut (F1), dan penyebutnya bulat serta tidak nol menurut (F1) dan (F3).

Bukti. (1) Karena $b\ne0$ dan $d\ne0$, (F3) memberi $bd\ne0$. Selanjutnya $(bd)(b^{-1}d^{-1})=(bb^{-1})(dd^{-1})=1$, sehingga ketunggalan invers dalam (F2) memberi $(bd)^{-1}=b^{-1}d^{-1}$. Dengan memakai $dd^{-1}=1$ dan $bb^{-1}=1$, diperoleh

$$r+s=ab^{-1}+cd^{-1}=ab^{-1}(dd^{-1})+cd^{-1}(bb^{-1})=(ad)(bd)^{-1}+(bc)(bd)^{-1}=(ad+bc)(bd)^{-1},$$$$r-s=ab^{-1}-cd^{-1}=ab^{-1}(dd^{-1})-cd^{-1}(bb^{-1})=(ad)(bd)^{-1}-(bc)(bd)^{-1}=(ad-bc)(bd)^{-1}.$$

Untuk perkalian,

$$rs=(ab^{-1})(cd^{-1})=(ac)(b^{-1}d^{-1})=(ac)(bd)^{-1}.$$

Menurut (F1), bilangan $ad+bc$, $ad-bc$, $ac$, dan $bd$ semuanya bulat, dan $bd\ne 0$. Jadi ketiga hasil memenuhi Definisi 6.2.3.

(2) Misalkan $s\ne0$. Dari $s=c\,d^{-1}$ diperoleh

$$c=c\,(d^{-1}d)=(c\,d^{-1})\,d=sd.$$

Karena $s\ne0$ dan $d\ne0$, (F3) memberi $c=sd\ne0$. Karena $b\ne0$ dan $c\ne0$, (F3) memberi $bc\ne0$. Selanjutnya $(cd^{-1})(dc^{-1})=(cc^{-1})(dd^{-1})=1$, sehingga ketunggalan invers memberi $s^{-1}=d\,c^{-1}$. Maka

$$\frac rs=rs^{-1}=(ab^{-1})(dc^{-1})=(ad)(b^{-1}c^{-1})=(ad)(bc)^{-1},$$

dengan $(bc)^{-1}=b^{-1}c^{-1}$ menurut alasan yang sama seperti pada bagian (1). Karena $ad\in\mathbb Z$, $bc\in\mathbb Z$, dan $bc\ne0$, diperoleh $r/s\in\mathbb Q$. $\blacksquare$

Mengapa syarat $s\ne 0$ diperlukan. Tanpa syarat itu, $r/s$ tidak terdefinisi, dan rumus $ad/(bc)$ memuat penyebut $bc=0$. Syarat itu dipakai tepat di langkah yang membutuhkannya, yaitu untuk menyimpulkan $c\ne0$ dari $c=sd$.

Implikasi berbeda dari konversnya

Konvers dari $P\Rightarrow Q$ adalah $Q\Rightarrow P$. Membuktikan salah satunya tidak membuktikan yang lain.

Proposisi 6.2.11. Untuk setiap $n\in\mathbb Z$, jika $4\mid n$, maka $n$ genap.

Bukti. Ambil $n\in\mathbb Z$ sebarang dan misalkan $4\mid n$. Ada $m\in\mathbb Z$ dengan $n=4m=2(2m)$. Menurut (F1), $2m\in\mathbb Z$, sehingga $n$ genap. $\blacksquare$

Contoh 6.2.12 (konvers yang salah). Konvers dari Proposisi 6.2.11 adalah "untuk setiap $n\in\mathbb Z$, jika $n$ genap maka $4\mid n$". Pernyataan ini salah. Ambil $n=2$.

• Hipotesis terpenuhi: $2\in\mathbb Z$ dan $2=2\cdot1$ dengan $1\in\mathbb Z$, sehingga $2$ genap.
• Kesimpulan gagal: kita tunjukkan bahwa $4m\ne 2$ untuk setiap $m\in\mathbb Z$. Menurut (F4), $m\le0$ atau $m\ge1$. Jika $m\le 0$, maka $4m\le 0<2$. Jika $m\ge1$, maka $4m\ge4>2$. Dalam kedua kasus $4m\ne2$, sehingga $4\nmid 2$.

Jadi $n=2$ adalah kontra-contoh bagi konvers tersebut. Pembahasan umum tentang kontra-contoh ada di Unit 6.4.

Contoh ini tidak menunjukkan bahwa konvers selalu salah. Konvers Teorema 6.2.5, yaitu "jika $n^2$ genap maka $n$ genap", ternyata benar dan akan dibuktikan di Unit 6.3. Status sebuah konvers harus diperiksa tersendiri, dengan bukti atau dengan kontra-contoh.

Kesalahan umum

1. Menguji beberapa nilai sebagai pengganti bukti. Memeriksa $n=2,4,6$ untuk Teorema 6.2.5 tidak menjangkau $n=-8$ ataupun $n=10^{100}$. Pernyataan universal atas domain tak hingga memerlukan argumen tentang objek sebarang.
2. Satu saksi untuk dua objek. Menulis "$m=2k$ dan $n=2k$" dalam bukti Lema 6.2.4 diam-diam mengasumsikan $m=n$, sehingga yang terbukti hanyalah bahwa $2n$ genap. Setiap hipotesis eksistensial memerlukan saksinya sendiri.
3. Mengganti objek sebarang dengan objek tertentu. Menulis "ambil $n=6$" di tengah bukti universal membuat bukti itu hanya berlaku untuk $n=6$.
4. Saksi yang tidak diperiksa keanggotaannya. Menulis $n=2\cdot\frac n2$ tidak membuktikan bahwa $n$ genap, karena $\frac n2$ belum tentu bulat. Saksi harus berada dalam himpunan yang dituntut definisi.
5. Membagi atau memakai pecahan tanpa syarat. Untuk $x\in\mathbb R$, membagi kedua ruas $x^2=x$ dengan $x$ menghasilkan $x=1$ dan menghilangkan solusi $x=0$. Langkah yang benar adalah $x^2-x=x(x-1)=0$, lalu (F3) memberi $x=0$ atau $x=1$. Pada keterbagian, gunakan saksi dan jangan memakai $b/a$ (Contoh 6.2.7).
6. Menulis $\Leftrightarrow$ untuk langkah satu arah. Contohnya, $x=-3\Rightarrow x^2=9$ sah, tetapi kebalikannya tidak.
7. Mulai dari kesimpulan. Jika langkah-langkahnya hanya berupa implikasi satu arah, menulis kesimpulan di baris pertama lalu menurunkan pernyataan benar belum membuktikan kesimpulan itu. Draf analisis harus dilengkapi bukti dalam arah yang diperlukan. Namun rantai ekuivalensi yang setiap langkahnya telah diperiksa dua arah dapat dibaca balik dari pernyataan benar dan merupakan bukti yang sah.
8. Menganggap diagram sebagai bukti universal. Diagram Venn atau grafik membantu intuisi, tetapi setiap inklusi tetap harus dibuktikan dari definisi.

Latihan

Latihan 6.2.13. Buktikan: untuk setiap $m,n\in\mathbb Z$, jika $m$ dan $n$ ganjil, maka $m+n$ genap.

Latihan 6.2.14. Buktikan: untuk setiap $n\in\mathbb Z$, jika $n$ ganjil, maka $n^2$ ganjil.

Latihan 6.2.15. Buktikan: untuk setiap $a,b,c\in\mathbb Z$, jika $a\mid b$ dan $a\mid c$, maka untuk setiap $x,y\in\mathbb Z$ berlaku $a\mid(bx+cy)$. Jelaskan apa yang terjadi bila $a=0$.

Latihan 6.2.16. Seorang mahasiswa "membuktikan" bahwa untuk setiap $a,b,c\in\mathbb Z$, jika $a\mid b$ maka $a\mid bc$, sebagai berikut: "Karena $a\mid b$, $b/a$ bulat, sehingga $bc/a=(b/a)\,c$ bulat." Tunjukkan kelemahan argumen itu dengan kasus konkret, lalu tulis bukti yang benar.

Latihan 6.2.17. Misalkan $r,s\in\mathbb Q$. (a) Buktikan bahwa $\dfrac{r+s}{2}\in\mathbb Q$ dengan menuliskan pembilang dan penyebutnya secara eksplisit. (b) Jika $s\ne0$, buktikan bahwa $\dfrac{r-2s}{s}\in\mathbb Q$. Periksa setiap penyebut.

Latihan 6.2.18. Buktikan: untuk himpunan $A$ dan $B$, jika $A\subseteq B$ maka $A\cap B=A$.

Latihan 6.2.19. Misalkan $f:A\to B$ dan $g:B\to C$. Buktikan: jika $g\circ f$ injektif, maka $f$ injektif. Kemudian periksa model $A=\{0\}$, $B=\{0,1\}$, $C=\{0\}$, $f(0)=0$, $g(0)=g(1)=0$ untuk menunjukkan bahwa $g$ tidak harus injektif.

Latihan 6.2.20. Buktikan: untuk setiap $n\in\mathbb Z$, jika $6\mid n$ maka $3\mid n$. Tunjukkan bahwa konversnya salah.

Latihan 6.2.21. Seseorang berargumen: "Konvers Proposisi 6.2.11 salah. Karena itu, konvers Teorema 6.2.5 juga salah. Lagi pula saya sudah memeriksa bahwa $n^2$ genap untuk $n=2,4,6,8$, jadi Teorema 6.2.5 terbukti." Nilai kedua bagian argumen ini.

Strategi dan pembahasan

6.2.13. Strategi: dua hipotesis memberi dua saksi yang diberi nama berbeda; nilainya boleh sama, lalu susun saksi untuk $m+n$. Ambil $m,n\in\mathbb Z$ sebarang yang ganjil. Ada $k,l\in\mathbb Z$ dengan $m=2k+1$ dan $n=2l+1$. Maka $m+n=2k+2l+2=2(k+l+1)$. Menurut (F1), $k+l+1\in\mathbb Z$, sehingga $m+n$ genap. $\blacksquare$

6.2.14. Strategi: buka definisi ganjil, kuadratkan, lalu bentuk $2j+1$ dengan $j$ bulat. Ambil $n\in\mathbb Z$ sebarang yang ganjil. Ada $k\in\mathbb Z$ dengan $n=2k+1$. Maka $n^2=4k^2+4k+1=2(2k^2+2k)+1$. Menurut (F1), $2k^2+2k\in\mathbb Z$, sehingga $n^2$ ganjil menurut Definisi 6.2.1. $\blacksquare$ Bukti ini menyimpulkan "ganjil" langsung dari definisinya. Bukti ini tidak memakai, dan tidak memerlukan, fakta bahwa ganjil berarti tidak genap.

6.2.15. Strategi: dua saksi, lalu faktorkan $a$ keluar. Ambil $a,b,c\in\mathbb Z$ sebarang dengan $a\mid b$ dan $a\mid c$, dan ambil $x,y\in\mathbb Z$ sebarang. Ada $k,l\in\mathbb Z$ dengan $b=ak$ dan $c=al$. Maka $bx+cy=akx+aly=a(kx+ly)$. Menurut (F1), $kx+ly\in\mathbb Z$, sehingga $a\mid(bx+cy)$. $\blacksquare$ Jika $a=0$, hipotesis memaksa $b=c=0$, sehingga $bx+cy=0$, dan kesimpulan $0\mid0$ benar. Bukti di atas sudah mencakup kasus ini karena tidak memuat pembagian.

6.2.16. Strategi: cari anggota domain tempat ekspresi $b/a$ tak bermakna, lalu buka definisi lewat saksi. Argumen itu memakai $b/a$, yang tidak terdefinisi untuk $a=0$. Ambil $a=0$, $b=0$, dan $c=7$. Hipotesis $0\mid0$ benar dengan saksi $k=0$, dan kesimpulan $0\mid 0$ juga benar. Namun baris "$b/a$ bulat" berbunyi "$0/0$ bulat", yang tidak bermakna. Jadi argumen tersebut tidak mencakup seluruh domain klaim. Selain itu, "$b/a$ bulat" bukan definisi $a\mid b$. Bukti yang benar. Ambil $a,b,c\in\mathbb Z$ sebarang dengan $a\mid b$. Ada $k\in\mathbb Z$ dengan $b=ak$. Maka $bc=(ak)c=a(kc)$, dan menurut (F1), $kc\in\mathbb Z$. Jadi $a\mid bc$. $\blacksquare$

6.2.17. Strategi: buka definisi $r=a/b$ dan $s=c/d$ dengan $a,b,c,d\in\mathbb Z$, $b,d\ne0$, lalu terapkan Lema 6.2.10 langkah demi langkah. (a) Menurut lema, $r+s=\dfrac{ad+bc}{bd}$ dengan $bd\ne0$. Bilangan $2=\dfrac21$ rasional dan tidak nol. Bagian (2) lema, dengan pembilang $ad+bc$, penyebut $bd$, serta $2=\tfrac21$, memberi

$$\frac{r+s}{2}=\frac{(ad+bc)\cdot 1}{(bd)\cdot 2}=\frac{ad+bc}{2bd}.$$

Pembilang $ad+bc\in\mathbb Z$ menurut (F1). Penyebut $2bd\in\mathbb Z$ dan $2bd\ne 0$ karena $2\ne0$, $b\ne0$, $d\ne0$, menurut (F3). Jadi $\dfrac{r+s}2\in\mathbb Q$. $\blacksquare$ (b) Misalkan $s\ne0$. Menurut bagian (2) lema, $c\ne0$. Bagian (1) lema memberi $2s=\dfrac21\cdot\dfrac cd=\dfrac{2c}{1\cdot d}=\dfrac{2c}{d}$, dengan $d\ne0$, lalu

$$r-2s=\frac{ad-b(2c)}{bd}=\frac{ad-2bc}{bd},$$

dengan $ad-2bc\in\mathbb Z$ dan $bd\ne0$. Karena $s\ne0$, bagian (2) lema dengan $r-2s=\frac{ad-2bc}{bd}$ dan $s=\frac cd$ memberi

$$\frac{r-2s}{s}=\frac{(ad-2bc)\,d}{(bd)\,c}.$$

Pembilang $(ad-2bc)d\in\mathbb Z$. Penyebut $bdc\in\mathbb Z$ dan $bdc\ne0$ karena $b$, $d$, dan $c$ masing-masing tidak nol, menurut (F3) yang diterapkan dua kali. Jadi $\dfrac{r-2s}{s}\in\mathbb Q$. $\blacksquare$

6.2.18. Strategi: kesamaan himpunan dibuktikan dengan dua inklusi. Hipotesis $A\subseteq B$ hanya diperlukan pada salah satu arah. Ambil himpunan $A,B$ sebarang dan misalkan $A\subseteq B$. ($\subseteq$) Ambil $x\in A\cap B$ sebarang. Menurut definisi irisan, $x\in A$. ($\supseteq$) Ambil $x\in A$ sebarang. Karena $A\subseteq B$, diperoleh $x\in B$. Jadi $x\in A$ dan $x\in B$, yaitu $x\in A\cap B$. Kedua inklusi berlaku, sehingga $A\cap B=A$. $\blacksquare$

6.2.19. Strategi: targetnya adalah injektivitas $f$. Ambil dua anggota $A$ dengan nilai $f$ yang sama, lalu terapkan $g$ untuk memanfaatkan hipotesis. Ambil $x_1,x_2\in A$ sebarang dengan $f(x_1)=f(x_2)$. Nilai bersama ini adalah satu anggota $B$, dan $g$ adalah fungsi, sehingga $g(f(x_1))=g(f(x_2))$, yaitu $(g\circ f)(x_1)=(g\circ f)(x_2)$. Karena $g\circ f$ injektif, $x_1=x_2$. Jadi $f$ injektif. $\blacksquare$ Model. Fungsi $f:\{0\}\to\{0,1\}$ dan $g:\{0,1\}\to\{0\}$ terdefinisi pada seluruh domainnya. Komposisi $g\circ f:\{0\}\to\{0\}$ injektif, karena setiap $x_1,x_2\in\{0\}$ sama, yaitu $0$. Namun $g(0)=g(1)=0$ padahal $0\ne1$, sehingga $g$ tidak injektif. Jadi dari hipotesis tersebut kita hanya dapat menyimpulkan bahwa $f$ injektif, bukan bahwa $g$ injektif.

6.2.20. Strategi: susun ulang saksi; untuk konvers, cari $n$ dengan $3\mid n$ lalu tunjukkan tidak ada $m\in\mathbb Z$ dengan $n=6m$. Bukti implikasi. Ambil $n\in\mathbb Z$ sebarang dengan $6\mid n$. Ada $m\in\mathbb Z$ dengan $n=6m=3(2m)$, dan $2m\in\mathbb Z$ menurut (F1). Jadi $3\mid n$. $\blacksquare$ Konvers. Konversnya berbunyi "untuk setiap $n\in\mathbb Z$, jika $3\mid n$ maka $6\mid n$". Ambil $n=3$. Hipotesis terpenuhi karena $3=3\cdot1$ dengan $1\in\mathbb Z$. Untuk kesimpulan, ambil $m\in\mathbb Z$ sebarang. Menurut (F4), $m\le0$ atau $m\ge1$. Pada kasus pertama $6m\le0<3$, dan pada kasus kedua $6m\ge6>3$. Jadi $6m\ne3$ untuk setiap $m\in\mathbb Z$, sehingga $6\nmid3$. Dengan demikian, $n=3$ membantah konvers tersebut.

6.2.21. Strategi: nilai tiap bagian sebagai pernyataan logis tersendiri. Bagian pertama tidak sah. Status konvers suatu teorema tidak menentukan status konvers teorema lain. Setiap konvers adalah pernyataan tersendiri yang harus dibuktikan atau dibantah sendiri. Konvers Teorema 6.2.5 bahkan benar, dan buktinya diberikan di Unit 6.3. Bagian kedua juga tidak sah. Empat nilai hanya memeriksa empat anggota domain tak hingga $\mathbb Z$ dan tidak menyentuh, misalnya, $n=-2$. Teorema 6.2.5 terbukti oleh argumen tentang $n$ sebarang dengan saksi $2k^2\in\mathbb Z$, bukan oleh daftar contoh.

Transisi ke Unit 6.3

Pembuktian langsung bekerja baik ketika hipotesis dapat dibuka menjadi saksi yang dapat diolah. Dua klaim berikut menunjukkan situasi ketika metode tidak langsung lebih mudah diterapkan.

• "Jika $n^2$ genap maka $n$ genap." Membuka hipotesis memberi $n^2=2k$. Dari persamaan ini tidak tampak cara menyusun $j\in\mathbb Z$ dengan $n=2j$; menulis $n=\pm\sqrt{2k}$ tidak menyediakan saksi semacam itu.
• "Jika $r\in\mathbb Q$ dan $\alpha\in\mathbb R\setminus\mathbb Q$, maka $r+\alpha$ irasional." Hipotesis "$\alpha$ irasional" bersifat negatif: tidak ada $a,b\in\mathbb Z$ dengan $b\ne0$ yang memenuhi $\alpha=a/b$. Akibatnya, tidak ada saksi yang dapat dibuka.

Untuk klaim seperti ini, lebih mudah bekerja dengan negasi kesimpulan. Unit 6.3 membahas dua metode yang melakukan hal itu, yaitu kontraposisi dan kontradiksi. Lema 6.2.10, khususnya penutupan $\mathbb Q$ terhadap pengurangan dan pembagian oleh bilangan rasional tidak nol, akan menjadi alat utama dalam bukti-bukti tersebut.

6.3 Pembuktian dengan Kontradiksi dan Kontraposisi

Motivasi

Perhatikan pernyataan berikut: untuk setiap bilangan bulat $n$, jika $n^2$ genap maka $n$ genap. Pembuktian langsung dimulai dengan menulis $n^2 = 2m$ untuk suatu $m \in \mathbb{Z}$, lalu mencari $k \in \mathbb{Z}$ dengan $n = 2k$. Langkah berikutnya tidak tampak. Persamaan $n^2 = 2m$ tidak memberi cara yang sah untuk "mengambil akar" dan memperoleh saksi bagi $n$. Arah sebaliknya jauh lebih mudah. Jika kita mengetahui bentuk $n$, misalnya $n = 2k+1$, kita cukup mengkuadratkannya. Jadi informasi tentang $n$ mudah dibawa ke $n^2$, sedangkan informasi tentang $n^2$ sulit dibawa kembali ke $n$.

Kesulitan serupa muncul pada sifat yang dirumuskan secara negatif. Bilangan real $\alpha$ disebut irasional bila $\alpha \notin \mathbb{Q}$, yaitu bila tidak ada bilangan bulat $a, b$ dengan $b \neq 0$ dan $\alpha = a/b$. Sifat negatif seperti ini, baik sebagai hipotesis maupun sebagai sasaran, tidak memberi persamaan apa pun untuk diolah. Tidak ada saksi yang dapat dibuka seperti pada definisi genap. Sebaliknya, pengandaian bahwa representasi $\alpha = a/b$ ada langsung memberi persamaan konkret, dan dari persamaan itu kita dapat menurunkan sesuatu yang mustahil.

Dua metode dalam subbab ini, kontraposisi dan kontradiksi, menangani situasi tersebut. Keduanya sering memakai langkah aljabar yang sama, tetapi struktur asumsi dan sasarannya berbeda. Perbedaan inilah yang harus terbaca dalam setiap bukti.

Struktur logis kedua metode

Definisi 6.3.1 (Konvers, invers, kontrapositif). Untuk implikasi $P \Rightarrow Q$:

• konversnya adalah $Q \Rightarrow P$;
• inversnya adalah $\neg P \Rightarrow \neg Q$;
• kontrapositifnya adalah $\neg Q \Rightarrow \neg P$.

Proposisi 6.3.2. Implikasi $P \Rightarrow Q$ ekuivalen logis dengan kontrapositifnya $\neg Q \Rightarrow \neg P$.

Bukti. Dalam logika proposisional klasik, implikasi $P \Rightarrow Q$ salah tepat ketika $P$ benar dan $Q$ salah. Implikasi $\neg Q \Rightarrow \neg P$ salah tepat ketika $\neg Q$ benar dan $\neg P$ salah, yaitu ketika $Q$ salah dan $P$ benar. Kedua implikasi salah pada keadaan yang sama persis dan benar pada semua keadaan lain. Jadi nilai kebenarannya selalu sama. $\blacksquare$

Konvers dan invers adalah kontrapositif satu sama lain. Dengan Proposisi 6.3.2, keduanya ekuivalen satu sama lain, tetapi tidak selalu ekuivalen dengan implikasi semula. Contohnya, untuk $n \in \mathbb{Z}$, "jika $4 \mid n$ maka $n$ genap" benar (Subbab 6.2), sedangkan konversnya "jika $n$ genap maka $4 \mid n$" dibantah oleh $n = 2$ (lihat Latihan 6.3.14).

Untuk pernyataan berkuantor, ekuivalensi itu berlaku titik demi titik dengan domain yang sama:

$$\forall x \in D,\ \bigl(P(x) \Rightarrow Q(x)\bigr) \quad\text{ekuivalen dengan}\quad \forall x \in D,\ \bigl(\neg Q(x) \Rightarrow \neg P(x)\bigr).$$

Yang dinegasikan hanyalah $P(x)$ dan $Q(x)$. Syarat $x \in D$ tidak ikut dinegasikan.

Skema kontraposisi. Untuk membuktikan $\forall x \in D,\ (P(x) \Rightarrow Q(x))$:

Ambil $x \in D$ sebarang. Andaikan $\neg Q(x)$. [Langkah-langkah sah.] Maka $\neg P(x)$.

Ini adalah bukti langsung untuk kontrapositif. Sasarannya spesifik, yaitu pernyataan $\neg P(x)$.

Proposisi 6.3.3 (Dasar pembuktian dengan kontradiksi). Jika dari asumsi $P$ dan $\neg Q$ dapat diturunkan secara sah suatu pernyataan $R$ beserta negasinya $\neg R$, maka $P \Rightarrow Q$ benar.

Bukti. Andaikan $P \Rightarrow Q$ salah. Maka $P$ benar dan $Q$ salah, sehingga $P$ dan $\neg Q$ keduanya benar. Karena setiap langkah penurunan sah, semua yang diturunkan dari asumsi benar juga benar. Akibatnya $R$ dan $\neg R$ keduanya benar, padahal itu mustahil. Dalam logika klasik, setiap pernyataan bernilai benar atau salah, sehingga $P \Rightarrow Q$ benar. $\blacksquare$

Skema kontradiksi. Untuk membuktikan $\forall x \in D,\ (P(x) \Rightarrow Q(x))$:

Ambil $x \in D$ sebarang dengan $P(x)$. Andaikan $\neg Q(x)$. [Langkah-langkah sah.] Diperoleh $R$ dan $\neg R$, suatu kontradiksi. Jadi $Q(x)$.

Untuk membuktikan pernyataan $T$ yang tidak berbentuk implikasi, kita mengandaikan $\neg T$ dan menurunkan kontradiksi. Kesimpulan $T$ kemudian diperoleh dengan alasan klasik yang sama.

Dua catatan struktur:

1. Jika dalam bukti dengan kontradiksi kita menurunkan $\neg P(x)$ dari $\neg Q(x)$ tanpa menggunakan hipotesis $P(x)$, lalu mempertentangkannya dengan $P(x)$, maka penurunan tersebut sudah merupakan bukti kontrapositif. Syarat tidak menggunakan $P(x)$ penting: munculnya kontradiksi terhadap hipotesis saja belum menunjukkan bahwa hipotesis itu dapat dihapus dari penurunan. Bukti tersebut sah, tetapi biasanya lebih jernih bila ditulis ulang sebagai kontraposisi.
2. Semua pernyataan yang diturunkan di dalam blok "andaikan $\neg Q(x)$" bersifat hipotetis. Setelah asumsi dilepas, pernyataan yang masih bergantung padanya tidak boleh dipakai sebagai fakta tanpa pembenaran independen. Pernyataan yang juga telah diturunkan dari premis yang tetap berlaku dapat dipakai berdasarkan pembenaran independen tersebut.

Paritas: kontraposisi dan kontradiksi pada contoh yang sama

Definisi genap dan ganjil mengikuti Definisi 6.2.1: bilangan $n \in \mathbb{Z}$ genap bila terdapat $k \in \mathbb{Z}$ dengan $n = 2k$. Kita sebut $n \in \mathbb{Z}$ ganjil bila terdapat $k \in \mathbb{Z}$ dengan $n = 2k+1$. Perhatikan bahwa "tidak genap" dan "ganjil" adalah dua pernyataan yang berbeda secara definisi. Hubungan keduanya harus dibuktikan dan tidak boleh diandaikan.

Hasil pinjaman (pembagian Euclid, Teorema 4.3.9). Untuk setiap $n \in \mathbb{Z}$ terdapat tepat satu pasangan $(h, t) \in \mathbb{Z} \times \mathbb{Z}$ dengan $n = 2h + t$ dan $0 \le t < 2$. Jadi $t \in \{0, 1\}$.

Lema 6.3.4 (Genap dan ganjil saling lepas dan mencakup $\mathbb{Z}$). Setiap $n \in \mathbb{Z}$ memenuhi tepat satu dari dua sifat berikut: genap atau ganjil. Khususnya, untuk $n \in \mathbb{Z}$: (a) jika $n$ tidak genap, maka $n$ ganjil; (b) jika $n$ ganjil, maka $n$ tidak genap.

Bukti. Ambil $n \in \mathbb{Z}$ sebarang. Menurut pembagian Euclidean, terdapat $(h, t)$ dengan $n = 2h + t$ dan $t \in \{0,1\}$.

Paling sedikit satu. Jika $t = 0$, maka $n = 2h$ dengan saksi $h \in \mathbb{Z}$, sehingga $n$ genap. Jika $t = 1$, maka $n = 2h + 1$ dengan saksi $h \in \mathbb{Z}$, sehingga $n$ ganjil.

Tidak keduanya. Andaikan $n$ genap dan ganjil sekaligus, yaitu $n = 2k$ dan $n = 2l + 1$ untuk suatu $k, l \in \mathbb{Z}$. Maka $(k, 0)$ dan $(l, 1)$ adalah dua pasangan yang memenuhi $n = 2h + t$ dengan $0 \le t < 2$. Ketunggalan pasangan memberi $(k,0) = (l,1)$, sehingga $0 = 1$. Ini kontradiksi.

Untuk (a): bila $n$ tidak genap, kasus $t = 0$ tidak mungkin terjadi karena kasus itu membuat $n$ genap. Jadi $t = 1$ dan $n$ ganjil. Pernyataan (b) adalah bagian "tidak keduanya". $\blacksquare$

Lema ini berlaku untuk semua bilangan bulat, termasuk bilangan negatif. Misalnya $-3 = 2(-2) + 1$, sehingga $-3$ ganjil dengan saksi $k = -2$. Ganjil tidak berarti positif.

Teorema 6.3.5. Untuk setiap $n \in \mathbb{Z}$, jika $n^2$ genap maka $n$ genap.

Strategi. Kontrapositifnya adalah: untuk setiap $n \in \mathbb{Z}$, jika $n$ tidak genap maka $n^2$ tidak genap. Hipotesis kontrapositif ini memberi bentuk eksplisit bagi $n$ melalui Lema 6.3.4, dan bentuk itu mudah dikuadratkan.

Bukti (kontraposisi). Ambil $n \in \mathbb{Z}$ sebarang dan andaikan $n$ tidak genap. Menurut Lema 6.3.4(a), $n$ ganjil, sehingga terdapat $k \in \mathbb{Z}$ dengan $n = 2k + 1$. Maka

$$n^2 = (2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1.$$

Bilangan $2k^2 + 2k$ adalah bilangan bulat karena $\mathbb{Z}$ tertutup terhadap penjumlahan dan perkalian. Jadi $n^2$ ganjil dengan saksi $2k^2 + 2k$. Menurut Lema 6.3.4(b), $n^2$ tidak genap. Dengan demikian kontrapositifnya terbukti, dan menurut Proposisi 6.3.2 teorema terbukti. $\blacksquare$

Pemeriksaan satu kasus negatif, yang bukan bagian dari bukti: untuk $n = -3$ kita punya $k = -2$, sehingga $2k^2 + 2k = 8 - 4 = 4$ dan $n^2 = 9 = 2 \cdot 4 + 1$.

Contoh 6.3.6 (Teorema 6.3.5 dengan kontradiksi). Untuk membandingkan struktur, berikut bukti dengan kontradiksi untuk teorema yang sama.

Ambil $n \in \mathbb{Z}$ sebarang dengan $n^2$ genap, lalu andaikan $n$ tidak genap. Seperti sebelumnya, $n = 2k+1$ untuk suatu $k \in \mathbb{Z}$ dan $n^2 = 2(2k^2+2k)+1$, sehingga $n^2$ ganjil. Sekarang $n^2$ genap (hipotesis) dan ganjil (hasil turunan). Ini bertentangan dengan bagian "tidak keduanya" pada Lema 6.3.4. Di sini $R$ adalah "$n^2$ genap" dan $\neg R$ diperoleh dari Lema 6.3.4(b). Jadi pengandaian salah, dan $n$ genap. $\blacksquare$

Langkah aljabarnya identik dengan bukti kontraposisi. Yang berbeda adalah asumsinya: bukti ini memakai hipotesis "$n^2$ genap" sejak awal dan menutup argumen dengan kontradiksi. Karena penurunan bahwa kuadratnya ganjil hanya memakai asumsi bahwa n tidak genap, tanpa memakai hipotesis bahwa kuadratnya genap, kita berada dalam situasi catatan 1 di atas. Versi kontraposisi lebih ringkas.

Bilangan rasional dan irasional

Kita meminjam hal-hal berikut sebagai bahan contoh:

• inklusi $\mathbb{Z} \subseteq \mathbb{Q} \subseteq \mathbb{R}$;
• operasi medan dan urutan pada $\mathbb{R}$;
• fakta bahwa operasi pada $\mathbb{Q}$ sama dengan operasi $\mathbb{R}$ yang dibatasi pada $\mathbb{Q}$;
• fakta bahwa $\mathbb{Z}$ tidak memiliki pembagi nol.

Konstruksi sistem bilangan ini bukan tugas bab ini. Notasi $\alpha \in \mathbb{R}\setminus\mathbb{Q}$ berarti $\alpha \in \mathbb{R}$ dan $\alpha \notin \mathbb{Q}$, dan bilangan seperti ini disebut irasional.

Lema penutupan $\mathbb{Q}$ (Lema 6.2.10). Jika $r, s \in \mathbb{Q}$, maka $r + s,\ r - s,\ rs \in \mathbb{Q}$. Jika selain itu $s \neq 0$, maka $r/s \in \mathbb{Q}$. Kita juga memakai fakta sederhana bahwa setiap $m \in \mathbb{Z}$ rasional karena $m = m/1$. Khususnya $0, 1, -1, 2, 3 \in \mathbb{Q}$.

Teorema 6.3.7 (Rasional ditambah irasional). Untuk setiap $r \in \mathbb{Q}$ dan setiap $\alpha \in \mathbb{R}\setminus\mathbb{Q}$, berlaku $r + \alpha \in \mathbb{R}\setminus\mathbb{Q}$.

Strategi. Kesimpulan "$r + \alpha \in \mathbb{R}\setminus\mathbb{Q}$" terdiri atas dua bagian. Bagian positif, $r + \alpha \in \mathbb{R}$, diperoleh langsung dari penutupan $\mathbb{R}$. Bagian negatif, $r+\alpha \notin \mathbb{Q}$, ditangani dengan kontradiksi.

Bukti. Ambil $r \in \mathbb{Q}$ dan $\alpha \in \mathbb{R}\setminus\mathbb{Q}$ sebarang. Karena $r \in \mathbb{Q} \subseteq \mathbb{R}$ dan $\alpha \in \mathbb{R}$, penutupan $\mathbb{R}$ terhadap penjumlahan memberi $r + \alpha \in \mathbb{R}$.

Andaikan $r + \alpha \in \mathbb{Q}$, dan tulis $q = r + \alpha$. Dengan menambahkan $-r$ pada kedua ruas di $\mathbb{R}$, diperoleh $\alpha = q - r$. Karena $q, r \in \mathbb{Q}$, penutupan $\mathbb{Q}$ terhadap pengurangan memberi $q - r \in \mathbb{Q}$, sehingga $\alpha \in \mathbb{Q}$. Ini bertentangan dengan $\alpha \notin \mathbb{Q}$. Jadi $r + \alpha \notin \mathbb{Q}$, dan bersama bagian pertama, $r + \alpha \in \mathbb{R}\setminus\mathbb{Q}$. $\blacksquare$

Teorema ini tidak memerlukan syarat $r \neq 0$. Untuk $r = 0$, kesimpulannya hanya mengatakan bahwa $\alpha$ irasional. Tidak ada rasional $r$ dan irasional $\alpha$ yang jumlahnya rasional. Rumusan "jumlah bilangan rasional dan irasional bisa rasional atau irasional" adalah salah. Yang memang dapat menghasilkan kedua jenis adalah jumlah dua bilangan irasional (Proposisi 6.3.11).

Teorema 6.3.8 (Rasional tak nol dikali irasional). Untuk setiap $r \in \mathbb{Q}\setminus\{0\}$ dan setiap $\alpha \in \mathbb{R}\setminus\mathbb{Q}$, berlaku $r\alpha \in \mathbb{R}\setminus\mathbb{Q}$.

Bukti. Ambil $r \in \mathbb{Q}\setminus\{0\}$ dan $\alpha \in \mathbb{R}\setminus\mathbb{Q}$ sebarang. Penutupan $\mathbb{R}$ terhadap perkalian memberi $r\alpha \in \mathbb{R}$.

Andaikan $r\alpha \in \mathbb{Q}$, dan tulis $q = r\alpha$. Karena $r \neq 0$, $r$ mempunyai kebalikan di $\mathbb{R}$. Dengan mengalikan kedua ruas dengan $r^{-1}$, diperoleh $\alpha = q/r$. Karena $q \in \mathbb{Q}$ dan $r \in \mathbb{Q}$ dengan $r \neq 0$, penutupan $\mathbb{Q}$ terhadap pembagian oleh rasional tak nol memberi $q/r \in \mathbb{Q}$. Jadi $\alpha \in \mathbb{Q}$, bertentangan dengan $\alpha \notin \mathbb{Q}$. Dengan demikian $r\alpha \in \mathbb{R}\setminus\mathbb{Q}$. $\blacksquare$

Syarat $r \neq 0$ tidak dapat dihapus. Untuk $r = 0$ dan $\alpha$ irasional apa pun, $0 \cdot \alpha = 0 \in \mathbb{Q}$. Dalam bukti, syarat ini dipakai tepat pada langkah pembagian dengan $r$. Langkah itu tidak boleh dilakukan sebelum $r \neq 0$ diketahui.

Korolari 6.3.9. Jika $\alpha \in \mathbb{R}\setminus\mathbb{Q}$, maka $-\alpha \in \mathbb{R}\setminus\mathbb{Q}$.

Bukti. Kita punya $-1 \in \mathbb{Q}\setminus\{0\}$ dan $-\alpha = (-1)\alpha$. Terapkan Teorema 6.3.8 dengan $r = -1$. $\blacksquare$

Contoh 6.3.10 (Bentuk affine konkret). Misalkan $\alpha \in \mathbb{R}\setminus\mathbb{Q}$. Kita tunjukkan bahwa $3\alpha - 5 \in \mathbb{R}\setminus\mathbb{Q}$ dengan dua cara.

Lewat teorema. Karena $3 \in \mathbb{Q}\setminus\{0\}$, Teorema 6.3.8 memberi $3\alpha \in \mathbb{R}\setminus\mathbb{Q}$. Karena $-5 \in \mathbb{Q}$, Teorema 6.3.7 yang diterapkan pada $r = -5$ dan bilangan irasional $3\alpha$ memberi $-5 + 3\alpha = 3\alpha - 5 \in \mathbb{R}\setminus\mathbb{Q}$.

Langsung dengan kontradiksi. Bilangan $3\alpha - 5$ berada di $\mathbb{R}$ menurut penutupan $\mathbb{R}$. Andaikan $3\alpha - 5 = q \in \mathbb{Q}$. Maka $3\alpha = q + 5$. Karena $3 \neq 0$, diperoleh $\alpha = (q+5)/3$. Kita punya $q + 5 \in \mathbb{Q}$ karena $q, 5 \in \mathbb{Q}$ dan $\mathbb{Q}$ tertutup terhadap penjumlahan. Selanjutnya $(q+5)/3 \in \mathbb{Q}$ karena $3 \in \mathbb{Q}$ dan $3 \neq 0$. Jadi $\alpha \in \mathbb{Q}$, kontradiksi.

Sebagai pembanding, bentuk $0\cdot\alpha - 5 = -5$ rasional. Koefisien tak nol pada $\alpha$ adalah syarat yang benar-benar diperlukan.

Proposisi 6.3.11 (Jumlah dua irasional tidak mempunyai jenis tetap). Misalkan $\alpha \in \mathbb{R}\setminus\mathbb{Q}$. (a) Bilangan $\alpha$ dan $-\alpha$ keduanya irasional, dan $\alpha + (-\alpha) = 0 \in \mathbb{Q}$. (b) Bilangan $\alpha$ dan $\alpha + 1$ keduanya irasional, dan $\alpha + (\alpha+1) = 2\alpha + 1 \in \mathbb{R}\setminus\mathbb{Q}$.

Bukti. (a) Bilangan $-\alpha$ irasional menurut Korolari 6.3.9. Jumlahnya $\alpha + (-\alpha) = 0$, dan $0 = 0/1 \in \mathbb{Q}$.

(b) Bilangan $\alpha + 1$ irasional menurut Teorema 6.3.7 dengan $r = 1 \in \mathbb{Q}$. Jumlahnya $2\alpha + 1$ berada di $\mathbb{R}$ menurut penutupan $\mathbb{R}$. Andaikan $2\alpha + 1 = q \in \mathbb{Q}$. Maka $2\alpha = q - 1$. Karena $2 \neq 0$, diperoleh $\alpha = (q-1)/2$. Kita punya $q - 1 \in \mathbb{Q}$ (penutupan terhadap pengurangan, dengan $1 \in \mathbb{Q}$) dan $(q-1)/2 \in \mathbb{Q}$ (pembagian oleh $2 \in \mathbb{Q}\setminus\{0\}$). Jadi $\alpha \in \mathbb{Q}$, kontradiksi. Dengan demikian $2\alpha + 1 \in \mathbb{R}\setminus\mathbb{Q}$. $\blacksquare$

Status logis. Proposisi 6.3.11 bersifat kondisional: proposisi ini menyatakan apa yang terjadi bila suatu bilangan irasional $\alpha$ diberikan. Proposisi ini tidak membuktikan bahwa bilangan irasional ada. Pada titik ini, keberadaan sekurang-kurangnya satu bilangan irasional kita pinjam sebagai fakta tentang $\mathbb{R}$. Bukti bahwa $\sqrt{2}$ irasional dijadwalkan pada Bab 8, dan tidak diandaikan di sini. Dengan pinjaman itu, Proposisi 6.3.11 menunjukkan bahwa klaim "jumlah dua irasional selalu rasional" dan klaim "jumlah dua irasional selalu irasional" keduanya salah. Bentuk logis bantahan semacam ini, yaitu kontra-contoh, dibahas secara lengkap di Subbab 6.4.

Contoh 6.3.12 (Kuantor di dalam pengandaian). Kita buktikan bahwa tidak ada bilangan rasional positif terkecil. Dalam simbol, pernyataan yang dibuktikan adalah

$$\neg\, \exists q \in \mathbb{Q}\ \bigl(q > 0 \ \wedge\ \forall p \in \mathbb{Q}\ (p > 0 \Rightarrow q \le p)\bigr).$$

Bukti. Andaikan negasinya benar, yaitu terdapat $q \in \mathbb{Q}$ dengan $q > 0$ dan $q \le p$ untuk setiap $p \in \mathbb{Q}$ yang positif.

Pengandaian ini memberi kita satu bilangan $q$ tertentu, yang tidak kita pilih. Bagian universalnya memberi kebebasan memilih $p$ apa pun di $\mathbb{Q}$ yang positif. Pilih $p = q/2$. Bilangan ini rasional karena $q \in \mathbb{Q}$ dan $2 \in \mathbb{Q}\setminus\{0\}$, dan positif karena $q > 0$ (sifat urutan yang dipinjam). Bagian universal memberi $q \le q/2$. Dengan mengurangkan $q/2$ dari kedua ruas, diperoleh $q/2 \le 0$, sehingga $q \le 0$. Ini bertentangan dengan $q > 0$. $\blacksquare$

Perhatikan asimetrinya. Kuantor eksistensial dalam pengandaian menghasilkan objek tetap $q$, sedangkan kuantor universal dalam pengandaian adalah alat yang boleh kita terapkan pada objek pilihan kita. Domain $\mathbb{Q}$ dipertahankan di kedua kuantor. Yang dinegasikan adalah keseluruhan klaim eksistensial, bukan syarat keanggotaan $q \in \mathbb{Q}$.

Kesalahan umum

1. Membuktikan konvers atau invers. Membuktikan "jika $n$ genap maka $n^2$ genap" tidak membuktikan Teorema 6.3.5. Itu konversnya, dan kebetulan juga benar. Kontraposisi selalu menukar dan menegasikan kedua bagian.
2. Negasi yang membuang domain. Untuk $\alpha \in \mathbb{R}\setminus\mathbb{Q}$ yang tetap, negasi dari "$\forall r \in \mathbb{Q}$, $r + \alpha \notin \mathbb{Q}$" adalah "$\exists r \in \mathbb{Q}$, $r + \alpha \in \mathbb{Q}$". Negasinya bukan "$\exists r \notin \mathbb{Q}$, ..." dan juga bukan "$\forall r \in \mathbb{Q}$, $r + \alpha \in \mathbb{Q}$".
3. "Tidak genap berarti ganjil" tanpa dasar. Kedua sifat didefinisikan secara terpisah. Hubungan keduanya adalah isi Lema 6.3.4 dan bergantung pada pembagian Euclidean.
4. Menerapkan penutupan $\mathbb{Q}$ pada bilangan yang belum diketahui rasional. Dari $\alpha + \beta = q$ tidak dapat disimpulkan bahwa $q - \beta$ rasional bila $\beta$ irasional (Latihan 6.3.20).
5. Membagi sebelum memeriksa pembagi. Pada Teorema 6.3.8, langkah $\alpha = q/r$ hanya sah setelah $r \neq 0$ dipakai.
6. Kontradiksi semu. Kontradiksi berarti diperolehnya suatu $R$ dan $\neg R$ secara sah. Masing-masing harus berasal dari hipotesis, pengandaian $\neg Q$, definisi, hasil yang sudah terbukti, atau langkah sah dari semua itu. Pertentangan dengan dugaan atau intuisi yang belum dibuktikan belum merupakan kontradiksi yang sah. Contoh numerik dapat dipakai bila semua hipotesisnya terpenuhi; bahkan kesamaan numerik yang mustahil dapat menjadi kontradiksi bila diturunkan secara sah. Menurunkan $\neg Q$ dari pengandaian $\neg Q$ juga bukan kontradiksi, karena itu hanya mengulang pengandaian. Mengandaikan kesimpulan lalu "memeriksa" bahwa tidak muncul pertentangan bukanlah bukti.
7. Membawa keluar fakta hipotetis. Kesimpulan yang pembenarannya masih bergantung pada pengandaian $\neg Q$ tidak boleh dibawa keluar setelah pengandaian itu dilepas, kecuali tersedia pembenaran independen dari premis yang tetap berlaku.

Latihan

Latihan 6.3.13–6.3.14 bersifat dasar, 6.3.15–6.3.17 menengah, dan 6.3.18–6.3.20 lanjut.

Latihan 6.3.13 (Memilih metode). Buktikan bahwa untuk setiap $n \in \mathbb{Z}$, jika $n^2$ ganjil maka $n$ ganjil. Jelaskan mengapa metode yang Anda pilih cocok.

Latihan 6.3.14 (Konvers, invers, kontrapositif). Untuk $n \in \mathbb{Z}$, misalkan $P(n)$: "$4 \mid n$" dan $Q(n)$: "$n$ genap". Tuliskan konvers, invers, dan kontrapositif dari $\forall n \in \mathbb{Z},\ (P(n) \Rightarrow Q(n))$. Tentukan nilai kebenaran masing-masing beserta bukti atau kontra-contohnya.

Latihan 6.3.15 (Bentuk affine umum). Buktikan dengan kontradiksi, tanpa mengutip Teorema 6.3.7 maupun 6.3.8, bahwa untuk setiap $r \in \mathbb{Q}\setminus\{0\}$, $s \in \mathbb{Q}$, dan $\alpha \in \mathbb{R}\setminus\mathbb{Q}$, berlaku $r\alpha + s \in \mathbb{R}\setminus\mathbb{Q}$.

Latihan 6.3.16 (Kasus $r = 0$). (a) Apakah pernyataan Latihan 6.3.15 tetap benar bila syarat $r \neq 0$ dihapus? (b) Langkah mana dalam bukti yang gagal? (c) Buktikan bahwa untuk $r = 0$, setiap $s \in \mathbb{Q}$, dan setiap $\alpha \in \mathbb{R}$, berlaku $r\alpha + s \in \mathbb{Q}$.

Latihan 6.3.17 (Negasi kuantor dalam kontradiksi). Teorema 6.3.7 berbentuk $\forall r \in \mathbb{Q}\ \forall \alpha \in \mathbb{R}\setminus\mathbb{Q},\ r + \alpha \notin \mathbb{Q}$ (bagian keanggotaan di $\mathbb{R}$ telah diperoleh dari penutupan $\mathbb{R}$ dalam bukti Teorema 6.3.7). (a) Mahasiswa A memulai bukti dengan "Andaikan untuk setiap $r \in \mathbb{Q}$ dan setiap $\alpha \in \mathbb{R}\setminus\mathbb{Q}$ berlaku $r + \alpha \in \mathbb{Q}$." Mengapa ini bukan negasi yang tepat? (b) Mahasiswa B menulis "Andaikan terdapat $r \notin \mathbb{Q}$ dan $\alpha \in \mathbb{Q}$ dengan $r + \alpha \in \mathbb{Q}$." Apa kesalahannya? (c) Tuliskan negasi yang benar, lalu tunjukkan kontradiksi yang tepat.

Latihan 6.3.18 (Melengkapi penutupan yang hilang). Seorang mahasiswa menulis: "Andaikan $\alpha/r = q$ rasional. Maka $\alpha = rq$ rasional, kontradiksi." Lengkapi argumen ini menjadi bukti utuh bahwa untuk $r \in \mathbb{Q}\setminus\{0\}$ dan $\alpha \in \mathbb{R}\setminus\mathbb{Q}$, berlaku $\alpha / r \in \mathbb{R}\setminus\mathbb{Q}$. Tunjukkan secara eksplisit, dengan pecahan, mengapa $rq \in \mathbb{Q}$.

Latihan 6.3.19 (Kebalikan irasional). Buktikan bahwa jika $\alpha \in \mathbb{R}\setminus\mathbb{Q}$, maka $1/\alpha$ terdefinisi dan $1/\alpha \in \mathbb{R}\setminus\mathbb{Q}$.

Latihan 6.3.20 (Mendeteksi bukti keliru). Periksa "bukti" berikut.

"Teorema". Jumlah dua bilangan irasional selalu irasional. "Bukti". Andaikan $\alpha, \beta$ irasional dan $\alpha + \beta = q \in \mathbb{Q}$. Maka $\alpha = q - \beta$. Karena $\mathbb{Q}$ tertutup terhadap pengurangan, $q - \beta \in \mathbb{Q}$, sehingga $\alpha \in \mathbb{Q}$, kontradiksi.

Tunjukkan langkah yang tidak sah dan jelaskan status klaim tersebut.

Pembahasan

6.3.13. Hipotesis "$n^2$ ganjil" memberi $n^2 = 2m + 1$, dan bentuk ini sulit dibawa kembali ke $n$. Seperti pada Teorema 6.3.5, kontraposisi lebih alami. Kontrapositifnya adalah: jika $n$ tidak ganjil, maka $n^2$ tidak ganjil.

Ambil $n \in \mathbb{Z}$ sebarang yang tidak ganjil. Menurut Lema 6.3.4, $n$ memenuhi paling sedikit salah satu dari genap atau ganjil. Karena $n$ tidak ganjil, $n$ genap, sehingga $n = 2k$ untuk suatu $k \in \mathbb{Z}$. Maka $n^2 = 4k^2 = 2(2k^2)$ dengan $2k^2 \in \mathbb{Z}$, sehingga $n^2$ genap. Menurut bagian "tidak keduanya" pada Lema 6.3.4, $n^2$ tidak ganjil. Kontrapositif terbukti, sehingga pernyataan semula terbukti menurut Proposisi 6.3.2.

6.3.14.

• Semula, $4 \mid n \Rightarrow n$ genap: benar. Jika $n = 4k$ dengan $k \in \mathbb{Z}$, maka $n = 2(2k)$ dengan $2k \in \mathbb{Z}$.
• Kontrapositif, $n$ tidak genap $\Rightarrow 4 \nmid n$: benar, karena ekuivalen dengan pernyataan semula (Proposisi 6.3.2).
• Konvers, $n$ genap $\Rightarrow 4 \mid n$: salah. Ambil $n = 2$. Maka $n \in \mathbb{Z}$ dan $2 = 2 \cdot 1$, jadi hipotesis dipenuhi. Andaikan $4 \mid 2$, yaitu $2 = 4k$ untuk suatu $k \in \mathbb{Z}$. Setiap $k \in \mathbb{Z}$ memenuhi $k \le 0$ atau $k \ge 1$ (sifat urutan $\mathbb{Z}$ yang dipinjam). Jika $k \le 0$, maka $4k \le 0 < 2$. Jika $k \ge 1$, maka $4k \ge 4 > 2$. Kedua kasus mustahil, sehingga $4 \nmid 2$ dan kesimpulan gagal.
• Invers, $4 \nmid n \Rightarrow n$ tidak genap: salah, dengan kontra-contoh yang sama. Untuk $n = 2$, hipotesis $4 \nmid 2$ dipenuhi, tetapi $2$ genap.

Fakta bahwa konvers dan invers dibantah oleh kontra-contoh yang sama bukan kebetulan. Keduanya saling kontrapositif.

6.3.15. Ambil $r \in \mathbb{Q}\setminus\{0\}$, $s \in \mathbb{Q}$, dan $\alpha \in \mathbb{R}\setminus\mathbb{Q}$ sebarang. Penutupan $\mathbb{R}$ memberi $r\alpha + s \in \mathbb{R}$.

Andaikan $r\alpha + s = q \in \mathbb{Q}$. Maka $r\alpha = q - s$, dan karena $r \neq 0$, $\alpha = (q-s)/r$. Kita punya $q - s \in \mathbb{Q}$ karena $q, s \in \mathbb{Q}$ (penutupan terhadap pengurangan). Kemudian $(q-s)/r \in \mathbb{Q}$ karena $r \in \mathbb{Q}$ dan $r \neq 0$ (penutupan terhadap pembagian oleh rasional tak nol). Jadi $\alpha \in \mathbb{Q}$.

Kontradiksi yang tepat adalah $\alpha \in \mathbb{Q}$ dan $\alpha \notin \mathbb{Q}$. Jadi $r\alpha + s \in \mathbb{R}\setminus\mathbb{Q}$.

Sebagai alternatif, hasil ini dapat diperoleh dari Teorema 6.3.8, yang memberi $r\alpha$ irasional, lalu Teorema 6.3.7 dengan bilangan rasional $s$.

6.3.16. (a) Tidak, asalkan ada bilangan irasional. Dengan keberadaan suatu $\alpha \in \mathbb{R}\setminus\mathbb{Q}$ yang dipinjam, ambil $r = 0 \in \mathbb{Q}$ dan $s = 0 \in \mathbb{Q}$. Semua hipotesis yang tersisa dipenuhi, tetapi $0\cdot\alpha + 0 = 0 \in \mathbb{Q}$, sehingga kesimpulan gagal.

Seandainya $\mathbb{R}\setminus\mathbb{Q}$ kosong, pernyataan universal itu justru benar secara vakum. Inilah sebabnya pinjaman keberadaan perlu dinyatakan.

(b) Langkah yang gagal adalah $\alpha = (q-s)/r$, karena langkah ini membagi dengan $r$. Untuk $r = 0$, persamaan $r\alpha = q - s$ menjadi $0 = q - s$ dan tidak memuat informasi tentang $\alpha$.

(c) Untuk $r = 0$ dan $\alpha \in \mathbb{R}$ sebarang, $0\cdot\alpha = 0$ di $\mathbb{R}$, sehingga $r\alpha + s = s \in \mathbb{Q}$.

6.3.17. (a) Negasi dari "$\forall r\ \forall \alpha,\ r + \alpha \notin \mathbb{Q}$" adalah "$\exists r\ \exists \alpha,\ r + \alpha \in \mathbb{Q}$". Mahasiswa A tidak mengubah kuantor universal menjadi eksistensial. Pengandaiannya menuntut semua pasangan, bukan cukup satu pasangan, sehingga lebih kuat daripada negasi. Kontradiksi darinya hanya membantah pernyataan kuat itu dan tidak membuktikan teorema.

(b) Mahasiswa B menegasikan syarat domain. Bilangan $r$ tetap harus di $\mathbb{Q}$ dan $\alpha$ tetap harus di $\mathbb{R}\setminus\mathbb{Q}$. Yang dinegasikan hanya kesimpulan $r + \alpha \notin \mathbb{Q}$.

(c) Negasi yang benar adalah: terdapat $r \in \mathbb{Q}$ dan $\alpha \in \mathbb{R}\setminus\mathbb{Q}$ dengan $r + \alpha \in \mathbb{Q}$. Ambil saksi $r, \alpha$ tersebut dan tulis $q = r + \alpha$. Maka $\alpha = q - r \in \mathbb{Q}$ menurut penutupan terhadap pengurangan. Ini bertentangan dengan $\alpha \notin \mathbb{Q}$, yang merupakan bagian dari syarat domain saksi $\alpha$.

6.3.18. Karena $r \neq 0$, pembagian $\alpha/r$ terdefinisi di $\mathbb{R}$, dan $\alpha/r \in \mathbb{R}$.

Andaikan $\alpha/r = q \in \mathbb{Q}$. Dengan mengalikan kedua ruas dengan $r$, diperoleh $\alpha = rq$. Tulis $r = a/b$ dan $q = c/d$ dengan $a, b, c, d \in \mathbb{Z}$ serta $b \neq 0$ dan $d \neq 0$. Maka

$$rq = \frac{ac}{bd}.$$

Pembilang $ac$ dan penyebut $bd$ adalah bilangan bulat karena $\mathbb{Z}$ tertutup terhadap perkalian. Penyebutnya juga tak nol, $bd \neq 0$, karena $b \neq 0$, $d \neq 0$, dan $\mathbb{Z}$ tidak memiliki pembagi nol. Jadi $rq \in \mathbb{Q}$, sehingga $\alpha \in \mathbb{Q}$. Ini bertentangan dengan $\alpha \notin \mathbb{Q}$.

Bukti mahasiswa itu kehilangan tiga hal: alasan $\alpha/r$ terdefinisi, alasan pecahan $ac/(bd)$ sah, dan penunjukan kontradiksi yang tepat. Sebagai alternatif, $\alpha/r = (1/r)\alpha$. Bilangan $1/r$ rasional menurut penutupan terhadap pembagian, karena $1 \in \mathbb{Q}$ dan $r \neq 0$. Bilangan itu juga tak nol karena $r \cdot (1/r) = 1 \neq 0$. Jadi $1/r \in \mathbb{Q}\setminus\{0\}$, lalu Teorema 6.3.8 dapat diterapkan.

6.3.19. Karena $0 = 0/1 \in \mathbb{Q}$ dan $\alpha \notin \mathbb{Q}$, kita punya $\alpha \neq 0$. Jadi $1/\alpha$ terdefinisi di $\mathbb{R}$. Syarat ini tidak perlu ditambahkan sebagai hipotesis karena sudah termuat dalam irasionalitas $\alpha$.

Andaikan $1/\alpha = q \in \mathbb{Q}$. Maka $q\alpha = 1$. Jika $q = 0$, diperoleh $0 = 1$, mustahil, sehingga $q \neq 0$. Dengan membagi oleh $q$, diperoleh $\alpha = 1/q$. Bilangan ini rasional karena $1 \in \mathbb{Q}$ dan $q \in \mathbb{Q}\setminus\{0\}$. Secara eksplisit, jika $q = c/d$ dengan $c, d \in \mathbb{Z}$ dan $d \neq 0$, maka $c \neq 0$ karena $q \neq 0$, dan $1/q = d/c$ dengan $c \neq 0$. Jadi $\alpha \in \mathbb{Q}$, kontradiksi. Dengan demikian $1/\alpha \in \mathbb{R}\setminus\mathbb{Q}$.

6.3.20. Langkah "$q - \beta \in \mathbb{Q}$" tidak sah. Penutupan $\mathbb{Q}$ terhadap pengurangan hanya berlaku bila kedua operan rasional, sedangkan $\beta$ irasional. Bahkan $q - \beta = q + (-\beta)$ irasional menurut Korolari 6.3.9 dan Teorema 6.3.7. Jadi argumen ini tidak menghasilkan kontradiksi apa pun.

Klaim itu sendiri salah begitu ada satu bilangan irasional $\alpha$, yang keberadaannya dipinjam. Menurut Proposisi 6.3.11(a), $\alpha$ dan $-\alpha$ keduanya irasional, tetapi jumlahnya $0 \in \mathbb{Q}$. Klaim kebalikannya, "jumlah dua irasional selalu rasional", juga salah menurut Proposisi 6.3.11(b).

Transisi ke 6.4

Proposisi 6.3.11 meninggalkan dua pertanyaan. Pertama, hasilnya kondisional pada adanya bilangan irasional: pernyataan "terdapat $\alpha \in \mathbb{R}\setminus\mathbb{Q}$" adalah klaim eksistensial yang memerlukan buktinya sendiri. Kedua, bantahan terhadap "jumlah dua irasional selalu irasional" bertumpu pada satu pasangan yang memenuhi hipotesis tetapi menggagalkan kesimpulan, yaitu sebuah kontra-contoh. Di sini kontra-contoh itu bersyarat pada bilangan irasional yang keberadaannya dipinjam. Subbab 6.4 menjadikan bentuk-bentuk ini objek kajian: bagaimana membuktikan eksistensi dan ketunggalan secara umum, dan apa yang harus diperiksa agar sebuah contoh sah sebagai kontra-contoh bagi pernyataan universal. Keberadaan bilangan irasional tertentu tetap ditunda sampai bukti di Bab 8.

6.4 Pembuktian Eksistensi dan Kontra-Contoh (Counterexample)

Motivasi

Pada Unit 6.2 dan 6.3, sasaran bukti hampir selalu berbentuk universal: untuk setiap objek yang memenuhi hipotesis, kesimpulan tertentu berlaku. Banyak pernyataan matematika berbentuk lain. Pernyataan "persamaan ini mempunyai solusi" menuntut eksistensi objek yang memenuhi persamaan. Pernyataan "persamaan ini mempunyai tepat satu solusi" menuntut tambahan: tidak ada dua solusi yang berbeda. Sebaliknya, untuk menolak klaim universal, cukup satu objek dalam domain yang memenuhi semua hipotesis tetapi menggagalkan kesimpulan.

Unit ini membahas tiga pekerjaan tersebut: membuktikan eksistensi, membuktikan keunikan, dan menyusun kontra-contoh. Ketiganya bergantung pada pembacaan kuantor dan domain yang tepat. Kesalahan kecil dapat membuat seluruh argumen gugur, misalnya calon solusi yang ternyata di luar domain atau kontra-contoh yang tidak memenuhi hipotesis.

Tiga bentuk kuantor

Misalkan $D$ suatu himpunan dan $P(x)$ suatu sifat untuk $x \in D$.

• $\forall x \in D,\ P(x)$: setiap anggota $D$ memenuhi $P$.
• $\exists x \in D,\ P(x)$: sekurang-kurangnya satu anggota $D$ memenuhi $P$.
• $\exists!\, x \in D,\ P(x)$: tepat satu anggota $D$ memenuhi $P$.

Bentuk ketiga merupakan gabungan dua klaim yang berbeda.

Definisi 6.4.1 (eksistensi tunggal). Pernyataan $\exists!\, x \in D,\ P(x)$ berarti

$$\Big(\exists x \in D,\ P(x)\Big) \ \wedge\ \Big(\forall x \in D\ \forall y \in D,\ \big(P(x) \wedge P(y)\big) \to x = y\Big).$$

Konjung pertama adalah eksistensi. Konjung kedua adalah paling banyak satu (keunikan).

Menurut definisi ini, membuktikan $\exists!$ berarti membuktikan dua hal secara terpisah. Dengan aturan negasi Unit 6.1, negasinya adalah

$$\Big(\forall x \in D,\ \neg P(x)\Big) \ \vee\ \Big(\exists x \in D\ \exists y \in D,\ P(x) \wedge P(y) \wedge x \neq y\Big).$$

Jadi $\exists!$ gagal bila tidak ada saksi sama sekali, atau bila ada dua saksi yang berbeda.

Konjung "paling banyak satu" tidak memuat eksistensi. Konjung ini dapat benar secara vakum.

Contoh 6.4.2 (paling banyak satu tanpa eksistensi). Ambil $D = \mathbb{R}$ dan $P(x)$: $x^2 = -1$. Menurut sifat urutan $\mathbb{R}$ yang dipinjam, $x^2 \ge 0 > -1$ untuk setiap $x \in \mathbb{R}$. Jadi $\forall x \in \mathbb{R},\ \neg P(x)$. Akibatnya, untuk sebarang $x, y \in \mathbb{R}$, hipotesis $P(x) \wedge P(y)$ salah, sehingga implikasi $(P(x) \wedge P(y)) \to x = y$ benar. Klaim "paling banyak satu" benar. Namun $\exists!\, x \in \mathbb{R},\ P(x)$ salah karena konjung eksistensinya salah. Bukti keunikan saja tidak pernah cukup untuk menyimpulkan "tepat satu".

Eksistensi konstruktif: calon, domain, substitusi

Bukti konstruktif untuk $\exists x \in D,\ P(x)$ memuat tiga langkah yang perlu dituliskan terpisah.

1. Konstruksi calon. Sebutkan objek $x_0$ secara eksplisit, biasanya dinyatakan dengan data yang diberikan.
2. Pemeriksaan domain. Tunjukkan $x_0 \in D$. Langkah ini mencakup syarat tersembunyi, misalnya pembagi tidak nol dan ketertutupan operasi dalam domain.
3. Substitusi. Tunjukkan bahwa $P(x_0)$ benar dengan perhitungan langsung.

Calon biasanya ditemukan melalui analisis: kita mengandaikan solusi sudah ada, lalu memanipulasinya. Analisis semacam itu membuktikan implikasi "jika $x$ solusi, maka $x$ berbentuk tertentu". Implikasi ini tidak membuktikan bahwa bentuk tersebut memang solusi. Implikasi ini juga tidak membuktikan bahwa bentuk tersebut berada dalam domain. Karena itu langkah 2 dan 3 tetap wajib.

Eksistensi melalui kontradiksi

Dalam logika klasik, $\exists x \in D,\ P(x)$ juga dapat dibuktikan dengan mengandaikan negasinya, yaitu $\forall x \in D,\ \neg P(x)$, lalu menurunkan kontradiksi. Yang dinegasikan adalah seluruh klaim eksistensial. Mengandaikan bahwa satu calon tertentu gagal tidak cukup. Kegagalan satu calon tidak bertentangan dengan adanya calon lain.

Proposisi 6.4.3. Misalkan $a, b \in \mathbb{R}$ dan $a + b > 0$. Maka terdapat $x \in \{a, b\}$ dengan $x > 0$.

Strategi. Negasikan klaim eksistensial secara utuh, lalu jumlahkan ketaksamaannya.

Bukti. Andaikan tidak ada $x \in \{a, b\}$ dengan $x > 0$, yaitu $\forall x \in \{a, b\},\ \neg(x > 0)$. Menurut trikotomi urutan $\mathbb{R}$ (dipinjam), $\neg(x > 0)$ setara dengan $x \le 0$. Jadi $a \le 0$ dan $b \le 0$. Karena urutan kompatibel dengan penjumlahan, $a + b \le 0 + b = b \le 0$. Ini bertentangan dengan hipotesis $a + b > 0$. Jadi pengandaian salah, dan terdapat $x \in \{a, b\}$ dengan $x > 0$. $\blacksquare$

Bukti ini tidak menyebutkan apakah saksinya $a$ atau $b$. Bukti ini hanya menyatakan bahwa keduanya tidak mungkin sama-sama gagal. Hipotesis $a+b>0$ dipertahankan selama bukti. Yang dinegasikan hanya kesimpulannya.

Teorema utama: persamaan linear $3x + 2 = a$

Teorema 6.4.4. Untuk setiap $a \in \mathbb{R}$ terdapat tepat satu $x \in \mathbb{R}$ dengan $3x + 2 = a$.

Analisis (bukan bukti). Jika $3x + 2 = a$, maka $3x = a - 2$, sehingga $x = (a-2)/3$. Langkah ini hanya menunjukkan bahwa setiap solusi, jika ada, sama dengan $(a-2)/3$. Langkah ini belum menunjukkan bahwa $(a-2)/3$ adalah bilangan real yang benar-benar memenuhi persamaan. Analisis memberi calon. Bukti di bawah memeriksa calon tersebut.

Strategi. Menurut Definisi 6.4.1, buktikan secara terpisah eksistensi (konstruksi, domain, substitusi) dan keunikan (dua saksi sebarang adalah sama).

Bukti. Ambil $a \in \mathbb{R}$ sebarang.

Konstruksi calon. Tetapkan $x_0 = \dfrac{a-2}{3}$.

Pemeriksaan domain. Karena $\mathbb{R}$ tertutup atas pengurangan, $a - 2 \in \mathbb{R}$. Karena $3 \neq 0$, invers $3^{-1}$ ada di $\mathbb{R}$ menurut sifat medan. Jadi $x_0 = (a-2)\cdot 3^{-1} \in \mathbb{R}$.

Substitusi.

$$3x_0 + 2 = 3\cdot\frac{a-2}{3} + 2 = (a-2) + 2 = a.$$

Jadi $x_0$ memenuhi persamaan, dan eksistensi terbukti.

Keunikan. Misalkan $x, y \in \mathbb{R}$ sebarang dengan $3x + 2 = a$ dan $3y + 2 = a$. Maka $3x + 2 = 3y + 2$. Dengan mengurangkan $2$ dari kedua ruas, diperoleh $3x = 3y$, sehingga $3(x - y) = 0$. Di $\mathbb{R}$ tidak ada pembagi nol. Karena $3 \neq 0$, haruslah $x - y = 0$, yaitu $x = y$.

Eksistensi dan keunikan sama-sama berlaku. Jadi terdapat tepat satu $x \in \mathbb{R}$ dengan $3x + 2 = a$. Karena $a$ sebarang, klaim berlaku untuk setiap $a \in \mathbb{R}$. $\blacksquare$

Bagian keunikan tidak memakai rumus $x_0$. Bagian itu hanya memakai dua saksi sebarang, sehingga argumennya tidak bergantung pada siapa saksinya.

Variasi: persamaan $ax + b = c$ di $\mathbb{R}$

Jika koefisien $3$ diganti parameter, status eksistensi dan keunikan bergantung pada parameter tersebut.

Proposisi 6.4.5. Misalkan $a, b, c \in \mathbb{R}$, dan tinjau persamaan $ax + b = c$ dengan $x \in \mathbb{R}$.

1. Jika $a \neq 0$, terdapat tepat satu solusi, yaitu $x = \dfrac{c-b}{a}$.
2. Jika $a = 0$ dan $b = c$, setiap $x \in \mathbb{R}$ adalah solusi. Solusi ada, tetapi tidak tunggal.
3. Jika $a = 0$ dan $b \neq c$, tidak ada solusi.

Ketiga kasus ini saling lepas dan mencakup semua kemungkinan. Berlaku $a \neq 0$ atau $a = 0$. Bila $a = 0$, berlaku $b = c$ atau $b \neq c$.

Strategi. Pisahkan kasus menurut $a$. Pada kasus $a\neq0$, ulangi pola Teorema 6.4.4. Pada kasus $a=0$, ruas kiri tidak bergantung pada $x$.

Bukti.

(1) Domain: $c - b \in \mathbb{R}$ dan $a \neq 0$, sehingga $a^{-1}$ ada dan $x_0 = (c-b)a^{-1} \in \mathbb{R}$. Substitusi: $a \cdot \dfrac{c-b}{a} + b = (c-b) + b = c$. Keunikan: jika $ax + b = c = ay + b$, maka $a(x-y) = 0$. Karena $a \neq 0$ dan tidak ada pembagi nol, $x = y$.

(2) Untuk setiap $x \in \mathbb{R}$, $0\cdot x + b = b = c$. Jadi setiap bilangan real adalah solusi. Khususnya, $0$ dan $1$ keduanya solusi, dan $0 \neq 1$. Pasangan ini adalah saksi bagi disjung kedua dalam negasi $\exists!$, sehingga solusi tidak tunggal.

(3) Untuk setiap $x \in \mathbb{R}$, $0\cdot x + b = b \neq c$. Jadi tidak ada $x \in \mathbb{R}$ yang merupakan solusi. $\blacksquare$

Pada kasus (3), pernyataan "setiap dua solusi adalah sama" benar secara vakum, seperti pada Contoh 6.4.2. Meskipun begitu, persamaan tidak mempunyai tepat satu solusi. Kasus (2) dan (3) juga menjelaskan mengapa bukti kasus (1) harus memakai $a \neq 0$ secara eksplisit. Tanpa syarat itu, invers $a^{-1}$ tidak tersedia. Dari $a(x-y)=0$ juga tidak dapat disimpulkan $x-y=0$, karena untuk $a=0$ kesamaan itu berlaku untuk sebarang $x,y$.

Mengganti domain: $3x + 2 = a$ di $\mathbb{Z}$

Teorema 6.4.4 menyebut domain $\mathbb{R}$ untuk $a$ maupun $x$. Jika domain diganti, klaimnya juga berubah.

Proposisi 6.4.6. Misalkan $a \in \mathbb{Z}$. Persamaan $3x + 2 = a$ mempunyai solusi $x \in \mathbb{Z}$ jika dan hanya jika $3 \mid (a - 2)$. Bila solusi bulat ada, solusi itu tunggal.

Strategi. Arah $(\Rightarrow)$ membaca saksi keterbagian dari solusi. Arah $(\Leftarrow)$ membangun calon dari saksi keterbagian, bukan dari rumus real $(a-2)/3$. Keunikan diperoleh seperti pada Teorema 6.4.4.

Bukti.

($\Rightarrow$) Misalkan $x \in \mathbb{Z}$ memenuhi $3x + 2 = a$. Maka $a - 2 = 3x$ dengan $x \in \mathbb{Z}$ sebagai saksi, sehingga $3 \mid (a-2)$.

($\Leftarrow$) Misalkan $3 \mid (a-2)$. Menurut definisi keterbagian, terdapat $k \in \mathbb{Z}$ dengan $a - 2 = 3k$. Calon: $x_0 = k$. Domain: $k \in \mathbb{Z}$ karena $k$ diberikan sebagai saksi keterbagian. Substitusi: $3k + 2 = (a-2) + 2 = a$.

Keunikan. Jika $x, y \in \mathbb{Z}$ keduanya solusi, maka $3(x - y) = 0$. Karena $\mathbb{Z}$ tidak mempunyai pembagi nol dan $3 \neq 0$, berlaku $x = y$. Sebagai alternatif, $x$ dan $y$ juga solusi real, sehingga keunikan mengikuti Teorema 6.4.4. $\blacksquare$

Calon $x_0 = k$ di atas diperoleh dari saksi keterbagian, bukan dari rumus $(a-2)/3$. Rumus itu selalu menghasilkan bilangan real, tetapi belum tentu bilangan bulat.

Korolari 6.4.7. Persamaan $3x + 2 = 0$ tidak mempunyai solusi $x \in \mathbb{Z}$.

Bukti. Menurut arah $(\Rightarrow)$ Proposisi 6.4.6, cukup ditunjukkan $3 \nmid (-2)$, yaitu tidak ada $k \in \mathbb{Z}$ dengan $3k = -2$. Ambil $k \in \mathbb{Z}$ sebarang. Jika $k \ge 0$, maka $3k \ge 0 > -2$. Jika $k \le -1$, maka $3k \le -3 < -2$. Kedua kasus ini mencakup semua $k$ karena tidak ada bilangan bulat di antara $-1$ dan $0$ (sifat urutan $\mathbb{Z}$ yang dipinjam). Jadi $3k \neq -2$. $\blacksquare$

Solusi real $-2/3$ tetap ada menurut Teorema 6.4.4, tetapi bilangan itu bukan bilangan bulat. Jadi pernyataan "untuk setiap $a \in \mathbb{Z}$ terdapat tepat satu $x \in \mathbb{Z}$ dengan $3x + 2 = a$" salah, dengan $a = 0$ sebagai saksinya. Teorema 6.4.4 tetap benar. Domain harus disebut lengkap sebelum sebuah teorema dinyatakan.

Kontra-contoh

Banyak klaim universal berbentuk $\forall x \in D,\ \big(P(x) \to Q(x)\big)$. Menurut Unit 6.1, negasinya adalah

$$\exists x \in D,\ \big(P(x) \wedge \neg Q(x)\big).$$

Pengamatan 6.4.8 (syarat kontra-contoh). Sebuah objek $x_0$ adalah kontra-contoh bagi $\forall x \in D,\ (P(x) \to Q(x))$ tepat bila ketiga syarat berikut dipenuhi:

1. $x_0 \in D$;
2. $P(x_0)$ benar, yaitu semua hipotesis terpenuhi;
3. $Q(x_0)$ salah.

Argumen kontra-contoh yang lengkap memeriksa ketiga syarat itu secara eksplisit. Objek yang gagal pada syarat 1 atau 2 tidak membantah klaim yang sedang diperiksa. Untuk objek demikian, implikasinya justru benar, atau objek itu memang tidak dibicarakan oleh klaim.

Untuk klaim dengan beberapa variabel terkuantifikasi universal, misalnya $\forall k\,\forall m\,\forall m'$, terapkan pengamatan ini dengan $D$ berupa hasil kali kartesius domainnya, misalnya $K\times M\times M$. Dalam hal itu, $x_0$ berupa tripel.

Contoh 6.4.9. Klaim: untuk setiap $a, b \in \mathbb{R}$, $(a+b)^2 = a^2 + b^2$. Ambil $a = b = 1$. Domain: $(1,1) \in \mathbb{R}\times\mathbb{R}$. Hipotesis: klaim tidak memuat hipotesis tambahan. Kesimpulan gagal: $(1+1)^2 = 4$, sedangkan $1^2 + 1^2 = 2$, dan $4 \neq 2$. Jadi klaim ini salah.

Kesamaan tersebut benar untuk sebagian pasangan, misalnya bila $a = 0$. Pasangan yang memenuhi tidak menyelamatkan klaim universal, sebab satu kontra-contoh sudah cukup.

Contoh 6.4.10 (jumlah dua irasional). Klaim A: untuk setiap $\alpha, \beta \in \mathbb{R}\setminus\mathbb{Q}$, $\alpha + \beta \in \mathbb{R}\setminus\mathbb{Q}$. Klaim B: untuk setiap $\alpha, \beta \in \mathbb{R}\setminus\mathbb{Q}$, $\alpha + \beta \in \mathbb{Q}$.

Kedua klaim tidak dapat dibantah tanpa sebuah bilangan irasional. Jika $\mathbb{R}\setminus\mathbb{Q}$ kosong, keduanya benar secara vakum (Unit 6.1). Keberadaan bilangan irasional di sini dipinjam. Buktinya untuk $\sqrt{2}$ dijadwalkan pada Bab 8. Misalkan $\alpha \in \mathbb{R}\setminus\mathbb{Q}$.

• Membantah A. Menurut Korolari 6.3.9, $-\alpha$ juga irasional: jika $-\alpha$ rasional, maka $\alpha = -(-\alpha)$ rasional oleh penutupan $\mathbb{Q}$, kontradiksi. Pasangan $(\alpha, -\alpha)$ berada dalam domain, kedua suku irasional, dan $\alpha + (-\alpha) = 0 \in \mathbb{Q}$. Jadi kesimpulan A gagal.
• Membantah B. Menurut Teorema 6.3.7 tentang jumlah bilangan rasional dan irasional, $\alpha + 1$ irasional. Pasangan $(\alpha, \alpha+1)$ berada dalam domain, dan jumlahnya $2\alpha + 1$. Jika $2\alpha + 1 = q \in \mathbb{Q}$, maka $\alpha = (q-1)/2 \in \mathbb{Q}$ oleh penutupan $\mathbb{Q}$ (pembaginya $2 \neq 0$), kontradiksi. Jadi $2\alpha + 1$ irasional, dan kesimpulan B gagal.

Jumlah dua irasional tidak mengikuti aturan tunggal. Hal ini berbeda dengan jumlah bilangan rasional dan irasional, yang selalu irasional (Unit 6.3).

Contoh 6.4.11 (domain mengubah status klaim). Klaim R: $\forall x \in \mathbb{R},\ x^2 \ge x$. Klaim Z: $\forall x \in \mathbb{Z},\ x^2 \ge x$.

Klaim R salah. Ambil $x = 1/2 \in \mathbb{R}$. Maka $x^2 = 1/4 < 1/2 = x$.

Klaim Z benar. Bilangan $1/2$ bukan kontra-contoh untuk klaim ini, karena $0 < 1/2 < 1$ dan tidak ada bilangan bulat di antara $0$ dan $1$ (dipinjam), sehingga $1/2 \notin \mathbb{Z}$. Buktinya sebagai berikut. Ambil $x \in \mathbb{Z}$ sebarang. Berdasarkan fakta pinjaman yang sama, berlaku $x \le 0$ atau $x \ge 1$. Jika $x \le 0$, maka $x^2 \ge 0 \ge x$. Jika $x \ge 1$, maka $x \ge 0$ dan $x - 1 \ge 0$, sehingga $x^2 - x = x(x-1) \ge 0$. $\blacksquare$

Contoh 6.4.12 (urutan kuantor). Klaim: $\forall a \in \mathbb{R}\ \exists x \in \mathbb{R},\ 3x + 2 = a$. Seseorang mengambil $a = 5$ dan $x = 0$, lalu menghitung $3\cdot 0 + 2 = 2 \neq 5$. Ini bukan kontra-contoh. Negasi klaim tersebut adalah $\exists a \in \mathbb{R}\ \forall x \in \mathbb{R},\ 3x + 2 \neq a$. Jadi kontra-contoh harus berupa satu $a$ yang gagal untuk semua $x$. Untuk $a = 5$, calon $x = 1$ berhasil. Lebih umum, Teorema 6.4.4 menunjukkan bahwa klaim ini benar, sehingga tidak ada kontra-contoh.

Model aplikasi terbatas untuk audit keamanan

Bagian ini memakai model mainan untuk melatih penyusunan kontra-contoh terhadap klaim "integritas pesan". Model ini bukan laporan kerentanan kriptografi atau protokol nyata.

Definisi 6.4.13 (model tag modulo 2). Tetapkan

$$K = \{0,1\}\ \text{(kunci)},\qquad M = \{0,1,2,3\}\ \text{(pesan)},\qquad T = \{0,1\}\ \text{(tag)}.$$

Untuk $k \in K$ dan $m \in M$, definisikan $\mathrm{tag}_k(m)$ sebagai sisa pembagian $k + m$ oleh $2$. Pembagian dengan sisa dipinjam melalui Teorema 4.3.9; aritmetika modulo dibahas dalam Unit 4.3. Karena sisa pembagian oleh $2$ adalah $0$ atau $1$, nilai $\mathrm{tag}_k(m)$ selalu berada di $T$.

Aturan penerimaan. Dengan kunci $k$, penerima menerima pasangan $(m, t) \in M \times T$ tepat bila $t = \mathrm{tag}_k(m)$.

Tabel lengkap. Untuk $k = 0$, nilai $k + m$ adalah $0,1,2,3$. Untuk $k = 1$, nilainya $1,2,3,4$. Sisa pembagiannya oleh $2$ adalah sebagai berikut.

Klaim yang hendak diuji (integritas pesan dalam model).

$$\forall k \in K\ \forall m \in M\ \forall m' \in M,\ \Big(\text{penerima dengan kunci } k \text{ menerima } (m', \mathrm{tag}_k(m))\Big) \to m' = m.$$

Dalam bahasa sehari-hari: misalkan pengirim menandai $m$, lalu pesannya diganti menjadi $m'$ sementara tagnya dibiarkan. Jika penerima tetap menerima pasangan itu, klaim menyatakan bahwa pesan yang diterima sama dengan pesan asal.

Negasinya adalah

$$\exists k \in K\ \exists m \in M\ \exists m' \in M,\ \Big(\text{penerima dengan kunci } k \text{ menerima } (m', \mathrm{tag}_k(m))\Big) \wedge m' \neq m.$$

Proposisi 6.4.14. Klaim integritas pesan dalam model Definisi 6.4.13 salah. Saksinya adalah $k = 0$, $m = 0$, $m' = 2$.

Bukti. Periksa ketiga syarat Pengamatan 6.4.8 dengan $D = K\times M\times M$ dan $x_0 = (0,0,2)$.

1. Domain: $0 \in K$, $0 \in M$, dan $2 \in M$.
2. Hipotesis: pengirim menghasilkan $\mathrm{tag}_0(0)$, yaitu sisa pembagian $0$ oleh $2$, sama dengan $0$. Penerima mendapat pasangan $(2, 0)$. Penerima menerima pasangan ini karena $\mathrm{tag}_0(2)$, yaitu sisa pembagian $2$ oleh $2$, sama dengan $0$. Jadi $t = 0 = \mathrm{tag}_0(2)$.
3. Kesimpulan gagal: $m' = 2 \neq 0 = m$.

Jadi negasi klaim terpenuhi, dan klaim salah. $\blacksquare$

Penggantian $0$ menjadi $2$ juga mempertahankan tag untuk $k = 1$, karena $\mathrm{tag}_1(0) = 1 = \mathrm{tag}_1(2)$. Namun klaim berbentuk universal atas $k$, sehingga satu nilai $k$ sudah cukup untuk membantahnya. Domain model ini berhingga, yaitu ada $2 \cdot 4 \cdot 4 = 32$ tripel $(k,m,m')$. Karena itu, klaim universal di dalamnya dapat diperiksa menyeluruh dengan tabel. Pemeriksaan menyeluruh atas domain berhingga berbeda dengan pengujian beberapa nilai pada domain tak hingga. Untuk membantah klaim, satu saksi tetap cukup.

Batas makna hasil. Proposisi 6.4.14 hanya menyatakan bahwa aturan penerimaan dalam model ini tidak menjamin pesan yang diterima sama dengan pesan asal. Hasil ini:

• bukan definisi atau analisis keamanan kode autentikasi pesan (MAC) modern;
• bukan bukti bahwa semua skema yang memakai aritmetika modulo tidak aman;
• bukan audit atas sistem nyata mana pun.

Model ini tidak memiliki jaringan, nonce, probabilitas, batas komputasi, atau asumsi tentang kemampuan penyerang. Model protokol lain dapat dianalisis dengan cara yang sama. Ruang keadaan, aturan, kondisi awal, dan klaim harus dinyatakan lebih dahulu. Setelah itu, berikan trace yang sah langkah demi langkah. Menyebut sesuatu sebagai "serangan" tanpa rumusan seperti itu bukan pembuktian.

Kesalahan umum

1. Calon tanpa verifikasi. Rumus dari analisis ("maka $x = (a-2)/3$") dianggap sudah membuktikan eksistensi. Pemeriksaan domain dan substitusi tetap wajib.
2. Keunikan dianggap eksistensi. Pernyataan "setiap dua solusi sama" dapat benar secara vakum (Contoh 6.4.2; Proposisi 6.4.5(3)).
3. Membagi tanpa syarat. Menulis $x = (c-b)/a$ tanpa memeriksa $a \neq 0$.
4. Domain diganti diam-diam. Calon real dipakai sebagai solusi bulat, atau kontra-contoh real dipakai untuk klaim tentang $\mathbb{Z}$ (Korolari 6.4.7; Contoh 6.4.11).
5. Kontra-contoh tidak memenuhi hipotesis. Objek yang tidak memenuhi $P$ tidak membantah $P \to Q$.
6. Urutan kuantor salah. Satu pasangan $(a, x)$ yang gagal tidak membantah klaim $\forall a\ \exists x$ (Contoh 6.4.12).
7. Negasi parsial dalam bukti eksistensi dengan kontradiksi. Yang diandaikan hanya "calon ini gagal", bukan "semua calon gagal".
8. Makna model dilebih-lebihkan. Hasil model mainan dibaca sebagai temuan tentang sistem nyata.

Latihan

Latihan 6.4.15. Tuliskan $\exists!\, x \in \mathbb{R},\ x^2 = 4$ dengan kuantor lengkap menurut Definisi 6.4.1, lalu tentukan nilai kebenarannya.

Latihan 6.4.16. Misalkan $D = \{x \in \mathbb{R} : x > 0\}$. Buktikan bahwa terdapat tepat satu $x \in D$ dengan $x^2 = 4$. Pisahkan konstruksi calon, pemeriksaan domain, substitusi, dan keunikan.

Latihan 6.4.17. Untuk $a \in \mathbb{Z}$, tinjau persamaan $2x + 3 = a$ dengan $x \in \mathbb{Z}$. (a) Rumuskan dan buktikan syarat perlu dan cukup untuk adanya solusi bulat, beserta keunikannya. (b) Tunjukkan bahwa $a = 4$ tidak memberi solusi bulat, padahal persamaannya mempunyai solusi real.

Latihan 6.4.18. Benar atau salah: "Untuk setiap $a, b, c \in \mathbb{R}$, jika setiap dua solusi real dari $ax + b = c$ sama, maka persamaan itu mempunyai tepat satu solusi real." Jika salah, berikan kontra-contoh dengan pemeriksaan lengkap, lalu perbaiki klaimnya dengan hipotesis yang cukup.

Latihan 6.4.19. Klaim: $\forall n \in \mathbb{Z}$, jika $n$ genap maka $4 \mid n$. Tentukan calon mana yang merupakan kontra-contoh sah, dan jelaskan alasannya: $n = 6$, $n = 3$, $n = 8$, $n = 1/2$.

Latihan 6.4.20. Klaim: $\forall x \in \mathbb{R},\ x^2 > x$. (a) Berikan kontra-contoh. (b) Perbaiki klaim dengan menambah hipotesis pada $x$ sehingga klaim menjadi benar, lalu buktikan.

Latihan 6.4.21. Dalam model Definisi 6.4.13: (a) Daftarkan semua pasangan $(m, m')$ dengan $m \neq m'$ sehingga penerima dengan kunci $k = 1$ menerima $(m', \mathrm{tag}_1(m))$. (b) Buktikan bahwa untuk setiap $k \in K$ dan $m, m' \in M$, penerima menerima $(m', \mathrm{tag}_k(m))$ jika dan hanya jika $2 \mid (m' - m)$. (c) Jelaskan mengapa (b) tidak memberi kesimpulan apa pun tentang sistem autentikasi nyata.

Latihan 6.4.22. Dalam model yang sama, tuliskan negasi dari $\forall k \in K\ \exists m \in M,\ \mathrm{tag}_k(m) = 1$, lalu tentukan nilai kebenaran klaim tersebut. Kemudian tentukan nilai kebenaran $\exists m \in M\ \forall k \in K,\ \mathrm{tag}_k(m) = 1$.

Pembahasan

6.4.15. Bentuk lengkapnya adalah

$$\big(\exists x \in \mathbb{R},\ x^2 = 4\big) \wedge \big(\forall x, y \in \mathbb{R},\ (x^2 = 4 \wedge y^2 = 4) \to x = y\big).$$

Konjung pertama benar karena $2 \in \mathbb{R}$ dan $2^2 = 4$. Konjung kedua salah. Pasangan $x = 2$, $y = -2$ berada di $\mathbb{R}$, keduanya memenuhi $2^2 = 4 = (-2)^2$, tetapi $2 \neq -2$. Pasangan ini menjadi saksi bagi disjung kedua dalam negasi $\exists!$. Jadi pernyataan tersebut salah: solusinya ada, tetapi tidak tunggal.

6.4.16. Calon: $x_0 = 2$. Domain: $2 \in \mathbb{R}$ dan $2 > 0$, sehingga $2 \in D$. Substitusi: $2^2 = 4$. Keunikan: ambil $x, y \in D$ dengan $x^2 = 4 = y^2$. Maka $x^2 - y^2 = 0$, yaitu $(x-y)(x+y) = 0$. Karena $x > 0$ dan $y > 0$, berlaku $x + y > 0$, sehingga $x + y \neq 0$. Karena tidak ada pembagi nol, $x - y = 0$, jadi $x = y$. Domain $D$ dipakai tepat pada langkah $x + y \neq 0$. Tanpa langkah ini, keunikan gagal, seperti ditunjukkan Latihan 6.4.15.

6.4.17. (a) Klaim: untuk $a \in \mathbb{Z}$, terdapat $x \in \mathbb{Z}$ dengan $2x + 3 = a$ jika dan hanya jika $2 \mid (a - 3)$. Bila solusi itu ada, solusinya tunggal. ($\Rightarrow$) Jika $x \in \mathbb{Z}$ solusi, maka $a - 3 = 2x$ dengan saksi $x \in \mathbb{Z}$. ($\Leftarrow$) Jika $a - 3 = 2k$ untuk suatu $k \in \mathbb{Z}$, maka calon $x_0 = k \in \mathbb{Z}$ memenuhi $2k + 3 = a$. Keunikan: $2x + 3 = 2y + 3$ memberi $2(x-y) = 0$. Karena $2 \neq 0$ dan $\mathbb{Z}$ tidak mempunyai pembagi nol, $x = y$. (b) Untuk $a = 4$, berlaku $a - 3 = 1$. Jika $2 \mid 1$, maka $1$ genap. Padahal $1 = 2\cdot 0 + 1$ ganjil, sedangkan genap dan ganjil saling lepas oleh ketunggalan sisa pembagian dengan $2$ (Unit 6.3, berdasarkan hasil Bab 4). Jadi tidak ada solusi bulat. Solusi realnya ada. Dengan Proposisi 6.4.5(1) untuk koefisien $2 \neq 0$, suku tetap $3$, dan ruas kanan $4$, solusi real tunggalnya adalah $x = (4-3)/2 = 1/2$. Namun $1/2 \notin \mathbb{Z}$, karena $0 < 1/2 < 1$ dan tidak ada bilangan bulat di antara $0$ dan $1$ (dipinjam).

6.4.18. Salah. Ambil $a = 0$, $b = 0$, $c = 1$, semuanya anggota $\mathbb{R}$. Hipotesis: untuk setiap $x \in \mathbb{R}$, $0\cdot x + 0 = 0 \neq 1$, sehingga tidak ada solusi. Akibatnya, "setiap dua solusi sama" benar secara vakum. Kesimpulan gagal: persamaan tidak mempunyai solusi, jadi tidak mempunyai tepat satu solusi. Perbaikan: "Untuk setiap $a, b, c \in \mathbb{R}$ dengan $a \neq 0$, persamaan $ax + b = c$ mempunyai tepat satu solusi real." Pernyataan ini adalah Proposisi 6.4.5(1). Perbaikan lain yang sah adalah menambah hipotesis "persamaan mempunyai sekurang-kurangnya satu solusi". Dengan hipotesis itu, kesimpulannya langsung mengikuti Definisi 6.4.1.

6.4.19.

• $n = 6$ sah. Domain: $6 \in \mathbb{Z}$. Hipotesis: $6 = 2\cdot 3$ dengan $3 \in \mathbb{Z}$, jadi $6$ genap. Kesimpulan gagal: andaikan $4k = 6$ dengan $k \in \mathbb{Z}$. Jika $k \le 1$, maka $4k \le 4 < 6$. Jika $k \ge 2$, maka $4k \ge 8 > 6$. Kedua kasus ini mencakup semua bilangan bulat karena tidak ada bilangan bulat di antara $1$ dan $2$ (dipinjam). Jadi $4 \nmid 6$.
• $n = 3$ tidak sah. $3 = 2\cdot 1 + 1$ ganjil, jadi bukan genap (genap dan ganjil saling lepas; Lema 6.3.4). Hipotesis gagal, sehingga implikasinya benar di $n = 3$.
• $n = 8$ tidak sah. $8 = 4\cdot 2$ dengan $2 \in \mathbb{Z}$, jadi kesimpulan berlaku.
• $n = 1/2$ tidak sah. Menurut Contoh 6.4.11, $1/2 \notin \mathbb{Z}$, sehingga bilangan ini berada di luar domain.

6.4.20. (a) Ambil $x = 0 \in \mathbb{R}$. Maka $0^2 = 0$, dan $0 > 0$ salah. Klaim ini tidak memuat hipotesis lain. (b) Klaim perbaikan: $\forall x \in \mathbb{R},\ x > 1 \to x^2 > x$. Bukti: ambil $x \in \mathbb{R}$ dengan $x > 1$. Maka $x - 1 > 0$ dan $x > 1 > 0$. Hasil kali dua bilangan positif adalah positif (dipinjam), sehingga $x^2 - x = x(x-1) > 0$. Jadi $x^2 > x$. Mengganti $>$ menjadi $\ge$ tidak cukup untuk memperbaiki klaim di $\mathbb{R}$, sebab $x = 1/2$ tetap menjadi kontra-contoh (Contoh 6.4.11).

6.4.21. (a) Dari baris $k = 1$ pada tabel, $\mathrm{tag}_1(0) = \mathrm{tag}_1(2) = 1$ dan $\mathrm{tag}_1(1) = \mathrm{tag}_1(3) = 0$. Penerima menerima $(m', \mathrm{tag}_1(m))$ tepat bila $\mathrm{tag}_1(m') = \mathrm{tag}_1(m)$. Pasangan dengan $m \neq m'$ adalah $(0,2)$, $(2,0)$, $(1,3)$, dan $(3,1)$. (b) Menurut aturan penerimaan, penerima menerima $(m', \mathrm{tag}_k(m))$ jika dan hanya jika $\mathrm{tag}_k(m') = \mathrm{tag}_k(m)$. Kesamaan ini berarti $k + m'$ dan $k + m$ mempunyai sisa yang sama bila dibagi $2$. Menurut hasil Bab 4 tentang kongruensi, hal ini setara dengan $2 \mid \big((k+m') - (k+m)\big) = m' - m$. Karena domainnya berhingga, kesetaraan ini juga dapat diperiksa langsung dari tabel untuk kedua nilai $k$. Hasil (a) merupakan kasus khusus $k = 1$. (c) Bagian (b) adalah pernyataan tentang himpunan $K, M, T$ dan aturan dalam Definisi 6.4.13, tidak lebih. Sistem nyata mempunyai ruang kunci, fungsi tag, model penyerang, dan asumsi lain yang tidak termuat di sini. Tidak ada langkah dalam bukti yang menyentuh objek-objek tersebut.

6.4.22. Negasinya adalah $\exists k \in K\ \forall m \in M,\ \mathrm{tag}_k(m) \neq 1$. Klaim $\forall k\ \exists m$ benar. Untuk $k = 0$, saksinya $m = 1$ karena $\mathrm{tag}_0(1) = 1$. Untuk $k = 1$, saksinya $m = 0$ karena $\mathrm{tag}_1(0) = 1$. Kedua saksi berada di $M$, dan kedua anggota $K$ sudah ditangani. Klaim $\exists m\ \forall k$ salah. Negasinya adalah $\forall m \in M\ \exists k \in K,\ \mathrm{tag}_k(m) \neq 1$. Negasi ini benar: menurut tabel, untuk setiap $m$, nilai $\mathrm{tag}_0(m)$ dan $\mathrm{tag}_1(m)$ berbeda, sehingga salah satunya bernilai $0$. Pada klaim pertama, saksi $m$ boleh bergantung pada $k$. Pada klaim kedua, satu $m$ harus berlaku untuk semua $k$. Perbedaan urutan kuantor inilah yang mengubah nilai kebenarannya.

Penutup dan arah ke Bab 7

Bab ini telah menyusun perangkat dasar pembuktian: membaca anatomi pernyataan, pembuktian langsung, kontraposisi dan kontradiksi, serta eksistensi, keunikan, dan kontra-contoh. Unit ini menunjukkan bahwa satu kontra-contoh cukup untuk meruntuhkan klaim universal. Sebaliknya, berapa pun banyaknya contoh yang berhasil, contoh-contoh itu tidak membuktikan klaim universal atas domain tak hingga. Pemeriksaan kasus demi kasus atas seluruh domain hanya mungkin bila domainnya berhingga, seperti pada model mainan di atas.

Klaim universal atas domain tak hingga tidak selalu memerlukan alat baru. Teorema 6.4.4 dan Klaim Z pada Contoh 6.4.11 dibuktikan untuk setiap anggota domain dengan metode bab ini. Namun ada klaim tentang setiap bilangan asli $n$ yang kebenarannya untuk suatu $n$ secara alami bergantung pada kasus sebelumnya, misalnya rumus jumlah $1+2+\dots+n$. Untuk klaim seperti itu, memeriksa nilai $n$ satu per satu tidak pernah selesai, dan frasa "begitu seterusnya" bukan langkah bukti. Bab 7 membahas prinsip induksi, yang memberi dasar sah untuk menutup argumen semacam ini.

Rujukan Bab 6

[R6-1] Richard Hammack. Book of Proof, Bab 4--9, bacaan pembanding metode pembuktian. https://richardhammack.github.io/BookOfProof/

[R6-2] Mathematical Institute, University of Oxford. Deskripsi seminar Ben Green, Mathematics: the past, present and future — The Goldbach Conjecture, 16 November 2018. https://www.maths.ox.ac.uk/node/30003