# Bab 7: Induksi Matematika dan Rekursi Induksi membuktikan pernyataan pada seluruh bilangan asli; rekursi menentukan fungsi dari nilai awal dan aturan langkah. Bab ini membedakan kedua peran itu, menurunkan induksi kuat serta urutan baik dari induksi lemah, membuktikan pembagian Euclid, lalu membangun fungsi rekursif melalui grafik aproksimasi. Contoh terhitung disertai bukti umum, diagnosis argumen cacat, dan latihan beserta pembahasan. Konvensi bilangan asli memuat 0. Keberadaan bilangan asli dan hukum aritmetika yang dinyatakan tetap merupakan prasyarat kerja; pembahasan ini tidak mengklaim konstruksi semua sistem bilangan tanpa asumsi. ## 7.1 Prinsip Induksi Matematika Lemah ### Motivasi Banyak pernyataan matematika berbentuk "untuk setiap $n \in \mathbb{N}$, $P(n)$". Memeriksa $n = 0, 1, 2, \dots, 1000$ satu per satu tidak membuktikan pernyataan seperti itu, karena kasusnya tak berhingga. Bab 6 memberi cara membuktikan pernyataan universal: ambil unsur sebarang, lalu turunkan sifatnya. Namun untuk banyak sifat bilangan asli, cara itu tidak langsung berjalan. Sifat pada $n$ sering hanya dapat dipahami dari sifat pada bilangan sebelumnya. Contohnya jumlah $1 + 2 + \dots + n$, yang dibentuk dari jumlah sebelumnya dengan menambah satu suku. Intuisinya sederhana. Bilangan asli dimulai dari $0$, dan setiap bilangan asli dicapai dari $0$ dengan menambah $1$ berulang-ulang. Kata "berulang-ulang" itulah yang memerlukan prinsip tersendiri agar menjadi tepat. Bab 8 menyatakan prinsip itu dalam aksioma Peano dan membahas struktur bilangan; keberadaan struktur bilangan asli tetap diasumsikan di sana. Di sini prinsip itu kita terima sebagai asumsi. Unit ini menyatakan prinsip tersebut, menjelaskan cara membacanya, menunjukkan cara menulis bukti induksi yang sah, dan mendiagnosis bukti induksi yang keliru. ### Konvensi dan status asumsi Sepanjang Bab 7 berlaku konvensi berikut. 1. $\mathbb{N} = \{0, 1, 2, \dots\}$. Bilangan $0$ termasuk bilangan asli. 2. Aritmetika dan urutan pada $\mathbb{N}$ dipinjam sebagai bahan kerja, begitu pula pada $\mathbb{Z}$, $\mathbb{Q}$, dan $\mathbb{R}$ bila diperlukan. Yang dipinjam meliputi: - sifat komutatif, asosiatif, dan distributif; - $0$ sebagai identitas penjumlahan; - urutan total; - penjumlahan yang menjaga urutan, termasuk urutan tegas; - setiap $n > 0$ mempunyai pendahulu $n - 1 \in \mathbb{N}$; - untuk $j \le k + 1$ berlaku $j \le k$ atau $j = k + 1$; - jika $n_0 \le n$, terdapat $j \in \mathbb{N}$ dengan $n = n_0 + j$. Bab 8 membahas aksioma Peano, menurunkan sebagian sifat operasi, dan membangun perluasan ke $\mathbb{Z}$ serta $\mathbb{Q}$. Bab itu tetap mengasumsikan keberadaan struktur Peano dan menandai hukum yang belum diturunkan sebagai pinjaman. Sifat-sifat ini bukan konsekuensi logika murni. Sifat-sifat ini adalah aritmetika yang kita pinjam dan kita tandai. 3. **Prinsip induksi lemah diasumsikan pada unit ini, tidak dibuktikan.** Unit 7.2 menurunkan induksi kuat dari prinsip ini, dan unit 7.3 menurunkan prinsip urutan baik. Karena itu unit ini **tidak boleh** memakai prinsip urutan baik, sebab prinsip itu belum diturunkan. Dengan urutan ini tidak ada lingkaran asumsi: induksi lemah adalah titik awal, dan prinsip-prinsip lain adalah akibatnya. 4. Bab 3 dan Bab 4 pernah meminjam induksi secara eksplisit. Bab 7 menjelaskan prinsip yang dipinjam itu. Bab 7 tidak menghapus status $\mathbb{N}$ beserta sifat-sifatnya sebagai asumsi kerja. ### Pernyataan prinsip **Prinsip 7.1.1 (Induksi Lemah; versi himpunan; diasumsikan).** Misalkan $S \subseteq \mathbb{N}$ memenuhi - (i) $0 \in S$, dan - (ii) untuk setiap $k \in \mathbb{N}$, jika $k \in S$ maka $k + 1 \in S$. Maka $S = \mathbb{N}$. **Bentuk predikat, basis $0$ (diturunkan di bawah dari versi himpunan).** Misalkan $P(n)$ adalah sifat bilangan asli yang dinyatakan dengan rumus dalam bahasa himpunan dengan parameter himpunan yang diperlukan, sehingga aksioma separasi Bab 3 dapat diterapkan untuk membentuk $\{n \in \mathbb{N} : P(n)\}$. Jika - **(B)** $P(0)$ benar, dan - **(L)** untuk setiap $k \in \mathbb{N}$, implikasi $P(k) \Rightarrow P(k+1)$ benar, maka $P(n)$ benar untuk setiap $n \in \mathbb{N}$. **Bentuk predikat, basis $n_0$ (diturunkan di bawah dengan pergeseran).** Misalkan $n_0 \in \mathbb{N}$ dan $P(n)$ seperti di atas. Jika - **(B)** $P(n_0)$ benar, dan - **(L)** untuk setiap $k \in \mathbb{N}$ dengan $k \ge n_0$, implikasi $P(k) \Rightarrow P(k+1)$ benar, maka $P(n)$ benar untuk setiap $n \in \mathbb{N}$ dengan $n \ge n_0$. Hanya versi himpunan yang kita terima tanpa bukti. Dua bentuk lainnya dibuktikan pada dua bagian berikut. Pembuktiannya hanya memakai versi himpunan, separasi, ekstensionalitas, dan aritmetika pinjaman. Ada tiga hal yang perlu diperhatikan saat membaca prinsip ini. - **Basis tidak selalu $1$, dan tidak selalu $0$.** Basis $n_0$ adalah bilangan asli mana pun yang kita pilih. Pilihan itu menentukan rentang kesimpulan. - **(L) adalah satu pernyataan universal tentang implikasi.** (L) tidak menyatakan bahwa $P(k)$ benar. (L) hanya menyatakan bahwa *untuk setiap* $k \ge n_0$, *jika* $P(k)$ benar *maka* $P(k+1)$ benar. Memeriksa satu implikasi, misalnya $P(3) \Rightarrow P(4)$, belum membuktikan (L). - **Kesimpulan tidak mengatakan apa pun tentang $n < n_0$.** Untuk $n < n_0$, $P(n)$ boleh benar atau salah. ### Hubungan versi himpunan dan versi predikat **Proposisi 7.1.2.** Versi himpunan berimplikasi bentuk predikat dengan basis $0$, dan sebaliknya. *Bukti.* (Himpunan $\Rightarrow$ predikat.) Dalam arah ini yang dipakai adalah versi himpunan, yaitu prinsip yang kita asumsikan. Misalkan $P$ memenuhi (B) dan (L) dengan basis $0$. Dengan aksioma separasi (Bab 3), bentuk $$S = \{\, n \in \mathbb{N} : P(n) \,\}.$$ Maka $S \subseteq \mathbb{N}$. Dari (B), $P(0)$ benar, jadi $0 \in S$. Sekarang ambil $k \in \mathbb{N}$ sebarang dengan $k \in S$. Menurut definisi $S$, $P(k)$ benar. Menurut (L), $P(k+1)$ benar. Karena $k + 1 \in \mathbb{N}$, diperoleh $k + 1 \in S$. Jadi $S$ memenuhi (i) dan (ii), dan versi himpunan memberi $S = \mathbb{N}$. Akibatnya untuk setiap $n \in \mathbb{N}$, $n \in S$, yakni $P(n)$ benar. (Predikat $\Rightarrow$ himpunan.) Dalam arah ini yang diandaikan adalah bentuk predikat, bukan versi himpunan. Misalkan $S \subseteq \mathbb{N}$ memenuhi (i) dan (ii). Definisikan $P(n)$ sebagai "$n \in S$". Syarat (i) adalah (B), dan syarat (ii) adalah (L). Bentuk predikat memberi $n \in S$ untuk setiap $n \in \mathbb{N}$, jadi $\mathbb{N} \subseteq S$. Bersama $S \subseteq \mathbb{N}$, ekstensionalitas memberi $S = \mathbb{N}$. $\blacksquare$ Jadi kedua versi setara, asalkan separasi tersedia. Kita cukup mengasumsikan salah satunya. Dalam naskah ini, yang diasumsikan adalah versi himpunan, karena versi itu berbicara tentang struktur $\mathbb{N}$ sendiri. Versi predikat adalah cara pakainya sehari-hari. ### Pergeseran basis **Proposisi 7.1.3.** Bentuk predikat dengan basis $0$ berimplikasi bentuk predikat dengan basis $n_0$, untuk setiap $n_0 \in \mathbb{N}$. *Bukti.* Misalkan $n_0 \in \mathbb{N}$ dan $P$ memenuhi (B) dan (L) dengan basis $n_0$. Definisikan sifat baru $$Q(j) \;:\Longleftrightarrow\; P(n_0 + j), \qquad j \in \mathbb{N}.$$ $Q$ dirumuskan dari $P$ dan aritmetika, sehingga separasi juga berlaku padanya. *Basis untuk $Q$.* Karena $n_0 + 0 = n_0$ (aritmetika pinjaman), pernyataan $Q(0)$ adalah pernyataan $P(n_0)$. Pernyataan ini benar menurut (B). *Langkah untuk $Q$.* Ambil $j \in \mathbb{N}$ sebarang dan andaikan $Q(j)$, yaitu $P(n_0 + j)$. Tulis $k = n_0 + j$. Karena $0 \le j$ dan penjumlahan menjaga urutan, $n_0 = n_0 + 0 \le n_0 + j = k$. Jadi (L) berlaku pada $k$ dan memberi $P(k + 1)$. Menurut asosiativitas, $k + 1 = (n_0 + j) + 1 = n_0 + (j + 1)$. Jadi $P(n_0 + (j+1))$ benar, yaitu $Q(j+1)$. Bentuk basis $0$ memberi $Q(j)$ untuk setiap $j \in \mathbb{N}$. Sekarang ambil $n \in \mathbb{N}$ dengan $n \ge n_0$. Menurut fakta pinjaman, terdapat $j \in \mathbb{N}$ dengan $n = n_0 + j$. Karena $n = n_0 + j$, pernyataan $P(n)$ adalah pernyataan $P(n_0 + j)$, yaitu $Q(j)$, yang telah terbukti. $\blacksquare$ Bukti ini memakai empat fakta aritmetika pinjaman: $n_0 + 0 = n_0$; $(n_0 + j) + 1 = n_0 + (j+1)$; $0 \le j \Rightarrow n_0 \le n_0 + j$; dan $n \ge n_0 \Rightarrow \exists j\,(n = n_0 + j)$. Bukti ini tidak memakai urutan baik. Untuk $n_0 = 0$, $Q$ sama dengan $P$, sehingga tidak ada yang hilang. ### Struktur bukti induksi: asumsi lokal versus sirkularitas Bukti induksi yang sah dapat ditulis menurut pola berikut. 1. **Nyatakan** sifat $P(n)$ secara eksplisit dan tetapkan basis $n_0$. 2. **Basis.** Buktikan $P(n_0)$. Ini pernyataan konkret tentang satu bilangan. 3. **Langkah.** Tulis: "Ambil $k \in \mathbb{N}$ sebarang dengan $k \ge n_0$. Andaikan $P(k)$ (*hipotesis induksi*). Akan dibuktikan $P(k+1)$." Lalu turunkan $P(k+1)$. 4. **Kesimpulan.** Menurut prinsip induksi (basis $n_0$), $P(n)$ benar untuk semua $n \ge n_0$. Langkah 3 adalah bukti langsung sebuah implikasi (Bab 6) yang digeneralisasi atas $k$ sebarang. Hipotesis induksi adalah **asumsi lokal**. Asumsi itu hanya berlaku di dalam subbukti untuk $k$ yang tetap itu, dan dilepas begitu $P(k+1)$ diperoleh. Yang dihasilkan subbukti itu adalah implikasi $P(k) \Rightarrow P(k+1)$, bukan $P(k)$. Keadaannya sama dengan membuktikan "jika $x > 2$ maka $x^2 > 4$". Kita mengandaikan $x > 2$ tanpa mengklaim bahwa setiap bilangan real lebih dari $2$. **Sirkularitas** terjadi jika kesimpulan yang belum terbukti dipakai untuk membenarkan dirinya sendiri. Contohnya mengandaikan "$P(n)$ untuk semua $n$" agar memperoleh $P(k+1)$, atau memakai $P(k+1)$ sebagai alasan bagi klaim yang sama tanpa pembuktian independen. Hipotesis induksi lemah hanya menyediakan $P(k)$. Hipotesis itu sendiri tidak menyediakan $P(m)$ untuk indeks lain. Pemakaian $P(m)$, baik $mk$, memerlukan pembenaran tambahan: misalnya basis yang sudah terbukti, teorema sebelumnya, atau bukti langsung. Jika pembenaran independen itu tersedia, pemakaiannya sah. Jika tidak tersedia, klaim itu tidak boleh diselundupkan sebagai fakta. Induksi kuat pada 7.2 akan menyediakan semua $P(m)$ dengan $n_0\le m\le k$ sebagai hipotesis lokal yang dinyatakan eksplisit. Bukti implikasi $P(k)\Rightarrow P(k+1)$ juga boleh memperoleh $P(k+1)$ tanpa menggunakan $P(k)$, apabila fakta yang sudah dibenarkan mencukupi. Yang wajib adalah implikasi berlaku bagi setiap $k$ dalam rentang yang ditentukan, bukan bahwa hipotesis induksi harus muncul dalam setiap baris perhitungan. Perhatikan juga bahwa langkah (L) dapat benar walaupun $P$ salah di mana-mana. Contohnya diberikan pada bagian diagnosis. Karena itu basis tidak dapat dihilangkan. Sebaliknya, basis saja jelas tidak cukup. ### Jumlah berhingga: definisi dan statusnya Misalkan $a_1, a_2, a_3, \dots$ adalah bilangan real yang diberikan untuk setiap indeks $i \ge 1$. Jumlah $\sum_{i=1}^{n} a_i$ didefinisikan oleh dua aturan: $$\sum_{i=1}^{0} a_i = 0 \quad\text{(jumlah kosong)}, \qquad \sum_{i=1}^{n+1} a_i = \Big(\sum_{i=1}^{n} a_i\Big) + a_{n+1} \quad (n \in \mathbb{N}).$$ Notasi $a_1 + a_2 + \dots + a_n$ berarti $\sum_{i=1}^{n} a_i$. Untuk $n = 0$, notasi titik-titik itu menyesatkan, sehingga yang berlaku adalah definisinya: nilainya $0$. Dari definisi, $\sum_{i=1}^{1} a_i = 0 + a_1 = a_1$ dan $\sum_{i=1}^{2} a_i = a_1 + a_2$. **Status.** Kedua aturan di atas adalah *definisi rekursif*: aturan pertama memberi nilai pada $0$, dan aturan kedua memberi cara memperoleh nilai pada $n+1$ dari nilai pada $n$. Bahwa ada **tepat satu** fungsi $n \mapsto \sum_{i=1}^{n} a_i$ yang memenuhi kedua aturan untuk semua $n$ adalah isi teorema rekursi, yang dibuktikan pada 7.4. Secara persis, dengan $X = \mathbb{R}$, $a = 0$, dan $F(n, x) = x + a_{n+1}$, teorema rekursi pada 7.4 menjamin tepat satu $u : \mathbb{N} \to \mathbb{R}$ dengan $u(0) = 0$ dan $u(n+1) = F(n, u(n))$. Kita menulis $\sum_{i=1}^{n} a_i$ untuk $u(n)$. Sampai 7.4, jumlah berhingga elementer kita pinjam. Kita menyatakannya di sini agar tidak ada asumsi tersembunyi. Jika fungsi itu sudah ada, sifat-sifatnya dapat dibuktikan dengan induksi. Misalnya, jika semua $a_i \in \mathbb{N}$, maka $\sum_{i=1}^{n} a_i \in \mathbb{N}$ untuk setiap $n$. Basisnya $0 \in \mathbb{N}$. Langkahnya memakai fakta bahwa $\mathbb{N}$ tertutup terhadap penjumlahan (aritmetika pinjaman). Argumen yang sama berlaku dengan $\mathbb{Z}$ menggantikan $\mathbb{N}$. ### Contoh utama: jumlah $n$ bilangan asli positif pertama **Proposisi 7.1.4.** Untuk setiap $n \in \mathbb{N}$ dengan $n \ge 1$, $$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}.$$ Pembagian dengan $2$ di ruas kanan dilakukan di $\mathbb{Q}$ (atau $\mathbb{R}$), yang aritmetikanya dipinjam. Kesamaan ini adalah kesamaan di $\mathbb{Q}$. Ruas kiri adalah jumlah bilangan asli, sehingga menurut bagian sebelumnya ruas kiri adalah bilangan asli. Karena itu kesamaan tersebut sekaligus menunjukkan bahwa $\frac{n(n+1)}{2}$ adalah bilangan asli, dan akibatnya $n(n+1)$ genap. Latihan 7.1.11 membuktikan fakta ini langsung tanpa melewati $\mathbb{Q}$. **Pemeriksaan pada $n = 4$.** Menurut definisi rekursif: $$\sum_{i=1}^{0} i = 0,\quad \sum_{i=1}^{1} i = 0 + 1 = 1,\quad \sum_{i=1}^{2} i = 1 + 2 = 3,\quad \sum_{i=1}^{3} i = 3 + 3 = 6,\quad \sum_{i=1}^{4} i = 6 + 4 = 10.$$ Ruas kanan memberi $\frac{4 \cdot 5}{2} = \frac{20}{2} = 10$. Kedua sisi bernilai $10$. Pemeriksaan ini hanya menguji satu kasus. Pemeriksaan ini bukan bukti. *Bukti.* Misalkan $P(n)$ menyatakan $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$. Basisnya $n_0 = 1$. *Basis ($n = 1$).* Ruas kiri: $\sum_{i=1}^{1} i = \sum_{i=1}^{0} i + 1 = 0 + 1 = 1$. Ruas kanan: $\frac{1 \cdot 2}{2} = 1$. Jadi $P(1)$ benar. *Langkah.* Ambil $k \in \mathbb{N}$ sebarang dengan $k \ge 1$. Andaikan $P(k)$, yaitu $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$. Akan dibuktikan $P(k+1)$, yaitu $\sum_{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2}$. Hitung: $$ \begin{aligned} \sum_{i=1}^{k+1} i &= \sum_{i=1}^{k} i + (k+1) && \text{(definisi jumlah)}\\ &= \frac{k(k+1)}{2} + (k+1) && \text{(hipotesis induksi)}\\ &= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} && \\ &= \frac{k(k+1) + 2(k+1)}{2} && \\ &= \frac{(k+1)(k+2)}{2} && \text{(distributivitas: faktor } k+1\text{)}\\ &= \frac{(k+1)\big((k+1)+1\big)}{2}. && \end{aligned} $$ Ini tepat $P(k+1)$. Hipotesis induksi dipakai tepat satu kali, pada baris kedua. Menurut prinsip induksi dengan basis $1$, $P(n)$ benar untuk semua $n \ge 1$. $\blacksquare$ **Perluasan ke $n = 0$.** Untuk $n = 0$, ruas kiri adalah jumlah kosong, yaitu $0$, dan ruas kanan adalah $\frac{0 \cdot 1}{2} = 0$. Jadi $P(0)$ juga benar. Perhitungan pada langkah di atas tidak pernah memakai $k \ge 1$, sehingga implikasi $P(k) \Rightarrow P(k+1)$ terbukti untuk setiap $k \in \mathbb{N}$. Dengan basis $0$, prinsip induksi memberi bentuk yang lebih kuat: $$\sum_{i=1}^{n} i = \frac{n(n+1)}{2} \quad\text{untuk setiap } n \in \mathbb{N}.$$ Versi basis $1$ adalah kejadian khusus dari bentuk ini. ### Contoh kedua: jumlah $n$ bilangan ganjil positif pertama Bilangan ganjil positif ke-$i$ (untuk $i \ge 1$) adalah $2i - 1$, sehingga $n$ bilangan ganjil positif pertama adalah $1, 3, \dots, 2n-1$. Tulis $n^2$ untuk $n \cdot n$. Notasi ini cukup sebagai singkatan perkalian dan belum memerlukan pangkat rekursif. **Proposisi 7.1.5.** Untuk setiap $n \in \mathbb{N}$, $$\sum_{i=1}^{n} (2i - 1) = n^2.$$ Pemeriksaan: $n = 1, 2, 3, 4$ memberi $1$, $1+3 = 4$, $4 + 5 = 9$, $9 + 7 = 16$. *Bukti.* Misalkan $P(n)$ menyatakan $\sum_{i=1}^{n}(2i-1) = n^2$. Basisnya $n_0 = 0$. *Basis ($n = 0$).* Ruas kiri adalah jumlah kosong, yaitu $0$. Ruas kanan $0 \cdot 0 = 0$. Jadi $P(0)$ benar. *Langkah.* Ambil $k \in \mathbb{N}$ sebarang dan andaikan $\sum_{i=1}^{k}(2i-1) = k^2$. Maka $$ \begin{aligned} \sum_{i=1}^{k+1}(2i-1) &= \sum_{i=1}^{k}(2i-1) + \big(2(k+1) - 1\big) && \text{(definisi jumlah)}\\ &= k^2 + (2k + 1) && \text{(hipotesis induksi; } 2(k+1)-1 = 2k+1\text{)}\\ &= (k+1)^2 && \text{(karena } (k+1)(k+1) = k^2 + 2k + 1\text{)}. \end{aligned} $$ Jadi $P(k+1)$ benar. Menurut prinsip induksi, $P(n)$ benar untuk setiap $n \in \mathbb{N}$. $\blacksquare$ Jika pembaca lebih suka tidak memakai jumlah kosong, basis $n = 1$ ($1 = 1^2$) bersama langkah yang sama memberi kesimpulan untuk $n \ge 1$. Versi di atas memuat versi itu. ### Diagnosis induksi yang salah **(a) Langkah benar, basis salah.** Misalkan $P(n)$ menyatakan "$2n + 1$ genap", yaitu terdapat $m \in \mathbb{Z}$ dengan $2n + 1 = 2m$. Langkahnya sah: jika $2k + 1 = 2m$ untuk suatu $m \in \mathbb{Z}$, maka $2(k+1) + 1 = (2k+1) + 2 = 2m + 2 = 2(m+1)$, jadi genap. Namun $P(0)$ menyatakan bahwa $1$ genap, dan ini salah. Akibatnya prinsip induksi tidak memberi apa-apa. Kenyataannya $P(n)$ salah untuk setiap $n$, karena $2n+1$ ganjil dan tidak ada bilangan bulat yang sekaligus genap dan ganjil (Lema 6.3.4, dengan status pinjaman pembagian Euclid yang dijelaskan di sana). Pelajarannya: langkah hanya *meneruskan* kebenaran, dan langkah tidak *menciptakan* kebenaran. **(b) Klaim "$n < n^2$ untuk setiap $n \in \mathbb{N}$".** Klaim ini gagal pada $n = 0$ ($0 < 0$ salah) dan pada $n = 1$ ($1 < 1$ salah). Meskipun begitu, langkahnya sah untuk *setiap* $k \in \mathbb{N}$. Andaikan $k < k^2$. Maka $$(k+1)^2 = k^2 + 2k + 1 > k + 2k + 1 = 3k + 1 \ge k + 1,$$ dengan ketaksamaan tegas dari $k < k^2$ (penjumlahan menjaga urutan tegas) dan ketaksamaan terakhir dari $2k \ge 0$. Pada $k = 0$ dan $k = 1$, hipotesis $k < k^2$ salah, sehingga implikasinya benar secara hampa. Implikasi yang benar secara hampa tidak memindahkan kebenaran apa pun. Pernyataan yang benar adalah: **untuk setiap $n \ge 2$, $n < n^2$**. Basisnya $2 < 4$, dan langkahnya seperti di atas. Basis tidak dapat diturunkan ke $0$ atau $1$ karena klaimnya memang salah di sana. **(c) "Semua kuda berwarna sama".** Klaimnya: $H(n)$ untuk setiap $n \ge 1$, dengan $H(n)$ menyatakan "dalam setiap kumpulan $n$ kuda, semua kuda berwarna sama". Contoh ini ilustratif, dan banyaknya unsur kumpulan berhingga dipakai secara intuitif. "Bukti" yang beredar berjalan sebagai berikut. > *Basis:* satu kuda jelas berwarna sama dengan dirinya. *Langkah:* misalkan $K$ kumpulan $k+1$ kuda. Ambil dua kuda berbeda $a, b \in K$. Kumpulan $K \setminus \{a\}$ dan $K \setminus \{b\}$ masing-masing berisi $k$ kuda, jadi masing-masing berwarna seragam menurut hipotesis induksi. Keduanya beririsan, sehingga warnanya sama, dan seluruh $K$ berwarna seragam. Kesalahannya terletak tepat pada kalimat "keduanya beririsan". Irisannya adalah $K \setminus \{a, b\}$, yang berisi $k - 1$ kuda. - Jika $k \ge 2$, irisan itu tak kosong. Ambil $c$ di dalamnya. Setiap kuda di $K \setminus \{a\}$ berwarna sama dengan $c$, dan setiap kuda di $K \setminus \{b\}$ juga berwarna sama dengan $c$. Karena $K = (K \setminus \{a\}) \cup (K \setminus \{b\})$, semua kuda di $K$ berwarna sama dengan $c$. Jadi argumen ini **sah** untuk $k \ge 2$. - Jika $k = 1$, maka $K = \{a, b\}$, $K \setminus \{a\} = \{b\}$, dan $K \setminus \{b\} = \{a\}$. Irisannya kosong. Tidak ada kuda penghubung, sehingga keseragaman $\{a\}$ dan $\{b\}$ tidak memberi informasi apa pun tentang hubungan warna $a$ dan $b$. Jadi yang benar-benar terbukti adalah $H(1)$ dan "untuk setiap $k \ge 2$, $H(k) \Rightarrow H(k+1)$". Syarat (L) dengan basis $1$ menuntut implikasi untuk *setiap* $k \ge 1$, sedangkan implikasi $H(1) \Rightarrow H(2)$ tidak pernah dibuktikan. Implikasi itu salah asalkan ada dua kuda berlainan warna, sebab untuk dua kuda tersebut $H(1)$ benar sedangkan $H(2)$ salah. Seandainya $H(2)$ benar, basis $2$ bersama langkah untuk $k \ge 2$ akan memberi $H(n)$ untuk semua $n \ge 2$; tetapi dalam model yang memuat dua kuda berlainan warna, $H(2)$ salah. Celah satu indeks saja sudah cukup untuk meruntuhkan seluruh argumen. ### Kesalahan umum 1. **Basis dilewati atau salah dihitung**, seperti pada contoh (a). 2. **Basis tidak cocok dengan klaim.** Contohnya mengklaim "untuk semua $n \in \mathbb{N}$" tetapi hanya membuktikan $P(1)$, atau memakai basis yang membuat klaim salah, seperti pada contoh (b). 3. **Langkah hanya diperiksa untuk satu $k$.** Menghitung $P(3)$ lalu $P(4)$ tidak membuktikan (L). 4. **Langkah tidak mencakup semua $k \ge n_0$**, seperti pada contoh (c). 5. **Sirkularitas.** Contohnya memakai "$P(n)$ untuk semua $n$" atau $P(k+1)$ sebagai fakta yang belum memiliki pembenaran independen di dalam langkah. 6. **Hipotesis induksi diperlakukan sebagai fakta global**, bukan sebagai asumsi lokal untuk $k$ yang tetap. 7. **Notasi titik-titik dipakai tanpa definisi**, sehingga kasus $n = 0$ (jumlah kosong) menjadi kabur. 8. **Urutan baik dipakai untuk "membuktikan" induksi di unit ini.** Prinsip itu baru diturunkan pada 7.3, dari induksi. ### Latihan Latihan dibagi tiga tingkat: **A** (dasar: basis $0$ atau basis kecil dengan langkah langsung), **B** (pergeseran, basis lain, dan aljabar langkah yang lebih panjang), dan **C** (diagnosis). Pembahasan lengkap disajikan setelah daftar soal. **Latihan 7.1.6 (A1).** Buktikan bahwa untuk setiap $n \in \mathbb{N}$, $\sum_{i=1}^{n} 2i = n(n+1)$. *Strategi:* basis jumlah kosong; pada langkah, pisahkan suku terakhir $2(k+1)$ lalu faktorkan $k+1$. **Latihan 7.1.7 (A2).** Untuk $n \in \mathbb{Z}$ tulis $n^3 = n \cdot n \cdot n$. Buktikan bahwa untuk setiap $n \in \mathbb{N}$, $3$ membagi $n^3 - n$, yaitu terdapat $m \in \mathbb{Z}$ dengan $n^3 - n = 3m$. *Strategi:* ekspansikan $(k+1)^3 - (k+1)$ dan temukan $k^3 - k$ di dalamnya. **Latihan 7.1.8 (A3).** Buktikan bahwa untuk setiap $n\in\mathbb{N}$ dengan $n \ge 3$, $2n + 1 < n^2$. Tunjukkan pula bahwa basis tidak dapat diganti dengan $0$, $1$, atau $2$. *Strategi:* pada langkah, $2(k+1)+1 = (2k+1) + 2$. Bandingkan $2$ dengan $2k + 1$. **Latihan 7.1.9 (B1).** Misalkan $S \subseteq \mathbb{N}$ dengan $5 \in S$ dan, untuk setiap $k\in\mathbb{N}$ dengan $k \ge 5$, $k \in S \Rightarrow k+1 \in S$. Dengan **versi himpunan** prinsip induksi (bukan bentuk basis $n_0$ secara langsung), buktikan bahwa setiap $n\in\mathbb{N}$ dengan $n \ge 5$ termuat dalam $S$. Beri pula contoh $S$ yang memenuhi hipotesis tetapi $S \ne \mathbb{N}$. *Strategi:* geser dengan $T = \{ j \in \mathbb{N} : 5 + j \in S \}$. **Latihan 7.1.10 (B2).** Buktikan bahwa untuk setiap $n \in \mathbb{N}$, $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$, dengan pembagian di $\mathbb{Q}$. Periksa nilai pada $n = 3$. *Strategi:* setelah memakai hipotesis induksi, keluarkan faktor $k+1$ dan faktorkan polinomial kuadrat yang tersisa. **Latihan 7.1.11 (B3).** Buktikan **tanpa** pembagian bahwa untuk setiap $n \in \mathbb{N}$ terdapat $m \in \mathbb{N}$ dengan $n(n+1) = 2m$. *Strategi:* $(k+1)(k+2) = k(k+1) + 2(k+1)$. **Latihan 7.1.12 (C1).** Seseorang "membuktikan" $\sum_{i=1}^{n} i = \frac{n^2 + n + 1}{2}$ untuk semua $n \in \mathbb{N}$ dengan langkah aljabar yang rapi. Periksa langkahnya, temukan kesalahannya, dan tentukan untuk $n$ mana saja klaim itu benar. *Strategi:* periksa langkah dan basis secara terpisah, lalu bandingkan dengan proposisi jumlah $n$ bilangan asli. **Latihan 7.1.13 (C2).** Misalkan $P(n)$ menyatakan "$n \ne 1$". Tunjukkan bahwa $P(0)$ benar dan bahwa untuk setiap $k \ge 1$, $P(k) \Rightarrow P(k+1)$ benar, tetapi $P(n)$ tidak benar untuk semua $n \in \mathbb{N}$. Syarat mana dari prinsip induksi yang tidak terpenuhi? Kaitkan dengan contoh kuda. *Strategi:* periksa implikasi pada $k = 0$. **Latihan 7.1.14 (C3).** Diagnosis dua "bukti" berikut untuk klaim $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ ($n \in \mathbb{N}$): (i) "Basis $n = 0$ benar. Langkah: karena rumus berlaku untuk semua $n$, khususnya rumus berlaku untuk $n = k+1$. Selesai." (ii) "Basis $n = 0$ benar. Langkah: untuk $k = 2$, $1 + 2 + 3 = 6 = \frac{3 \cdot 4}{2}$, jadi langkah induksi berlaku." *Strategi:* tanyakan apa yang diandaikan, dan untuk $k$ mana implikasi dibuktikan. ### Pembahasan latihan **Latihan 7.1.6 (A1).** Misalkan $P(n)$ menyatakan $\sum_{i=1}^{n} 2i = n(n+1)$. *Basis:* $\sum_{i=1}^{0} 2i = 0 = 0 \cdot 1$. *Langkah:* ambil $k \in \mathbb{N}$ sebarang dan andaikan $\sum_{i=1}^{k} 2i = k(k+1)$. Maka $$\sum_{i=1}^{k+1} 2i = \sum_{i=1}^{k} 2i + 2(k+1) = k(k+1) + 2(k+1) = (k+1)(k+2) = (k+1)\big((k+1)+1\big).$$ Menurut prinsip induksi, $P(n)$ benar untuk semua $n \in \mathbb{N}$. *Catatan:* menurunkan hasil ini dari proposisi utama dengan "mengeluarkan faktor $2$ dari jumlah" memerlukan sifat $\sum c\,a_i = c \sum a_i$. Sifat itu sendiri dibuktikan dengan induksi, sehingga bukti langsung di atas lebih hemat. **Latihan 7.1.7 (A2).** Misalkan $P(n)$ menyatakan "terdapat $m \in \mathbb{Z}$ dengan $n^3 - n = 3m$". *Basis:* $0^3 - 0 = 0 = 3 \cdot 0$. *Langkah:* ambil $k \in \mathbb{N}$ sebarang dan andaikan $k^3 - k = 3m$ untuk suatu $m \in \mathbb{Z}$. Dengan ekspansi $(k+1)^3 = k^3 + 3k^2 + 3k + 1$ (aljabar pinjaman), $$(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1 = (k^3 - k) + 3(k^2 + k) = 3m + 3(k^2+k) = 3(m + k^2 + k).$$ Karena $m + k^2 + k \in \mathbb{Z}$, $P(k+1)$ benar. Menurut prinsip induksi, $P(n)$ benar untuk semua $n \in \mathbb{N}$. **Latihan 7.1.8 (A3).** *Basis tidak dapat diturunkan:* untuk $n = 0, 1, 2$, ruas kiri berturut-turut $1, 3, 5$ dan ruas kanan $0, 1, 4$. Ketiga ketaksamaan itu salah, sehingga klaim memang tidak berlaku di sana. *Basis $n = 3$:* $7 < 9$. *Langkah:* ambil $k \ge 3$ sebarang dan andaikan $2k + 1 < k^2$. Maka $$2(k+1) + 1 = (2k+1) + 2 < k^2 + 2 \le k^2 + 2k + 1 = (k+1)^2.$$ Ketaksamaan tegas berasal dari hipotesis induksi. Ketaksamaan $2 \le 2k + 1$ berlaku karena $k \ge 1$, dan ini dijamin oleh $k \ge 3$. Menurut prinsip induksi dengan basis $3$, klaimnya benar untuk semua $n \ge 3$. **Latihan 7.1.9 (B1).** Dengan separasi, bentuk $T = \{ j \in \mathbb{N} : 5 + j \in S \}$. *$0 \in T$:* $5 + 0 = 5 \in S$. *Penutupan:* ambil $j \in T$, jadi $5 + j \in S$. Karena $5 + j \ge 5$, hipotesis memberi $(5 + j) + 1 \in S$. Menurut asosiativitas, $(5+j)+1 = 5 + (j+1)$, jadi $j + 1 \in T$. Versi himpunan memberi $T = \mathbb{N}$. Untuk $n \ge 5$, terdapat $j \in \mathbb{N}$ dengan $n = 5 + j$ (fakta pinjaman). Karena $j \in T$, diperoleh $n \in S$. *Contoh $S \ne \mathbb{N}$:* $S = \{ n \in \mathbb{N} : n \ge 5 \}$ memenuhi hipotesis, tetapi $0 \notin S$. Kesimpulan prinsip yang digeser memang tidak mengatakan apa pun tentang $n < 5$. **Latihan 7.1.10 (B2).** Misalkan $P(n)$ menyatakan $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$. *Basis:* $\sum_{i=1}^{0} i^2 = 0 = \frac{0 \cdot 1 \cdot 1}{6}$. *Langkah:* ambil $k \in \mathbb{N}$ sebarang dan andaikan $P(k)$. Maka $$ \begin{aligned} \sum_{i=1}^{k+1} i^2 &= \sum_{i=1}^{k} i^2 + (k+1)^2 && \text{(definisi jumlah)}\\ &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2 && \text{(hipotesis induksi)}\\ &= \frac{(k+1)\big[k(2k+1) + 6(k+1)\big]}{6} && \\ &= \frac{(k+1)(2k^2 + 7k + 6)}{6} && \\ &= \frac{(k+1)(k+2)(2k+3)}{6}. && \end{aligned} $$ Faktorisasi pada baris terakhir benar karena $(k+2)(2k+3) = 2k^2 + 3k + 4k + 6 = 2k^2 + 7k + 6$. Karena $k + 2 = (k+1)+1$ dan $2k + 3 = 2(k+1) + 1$, hasil ini tepat $P(k+1)$. Menurut prinsip induksi, $P(n)$ benar untuk semua $n \in \mathbb{N}$. *Pemeriksaan $n = 3$:* $1 + 4 + 9 = 14$ dan $\frac{3 \cdot 4 \cdot 7}{6} = \frac{84}{6} = 14$. **Latihan 7.1.11 (B3).** Misalkan $E(n)$ menyatakan "terdapat $m \in \mathbb{N}$ dengan $n(n+1) = 2m$". *Basis:* $0 \cdot 1 = 0 = 2 \cdot 0$. *Langkah:* ambil $k \in \mathbb{N}$ sebarang dan andaikan $k(k+1) = 2m$ dengan $m \in \mathbb{N}$. Maka $$(k+1)(k+2) = k(k+1) + 2(k+1) = 2m + 2(k+1) = 2(m + k + 1),$$ dengan $m + k + 1 \in \mathbb{N}$. Menurut prinsip induksi, $E(n)$ benar untuk semua $n \in \mathbb{N}$. Akibatnya $\frac{n(n+1)}{2} = m \in \mathbb{N}$, sesuai dengan catatan pada contoh utama, kali ini tanpa melewati $\mathbb{Q}$. **Latihan 7.1.12 (C1).** *Langkah:* andaikan $\sum_{i=1}^{k} i = \frac{k^2 + k + 1}{2}$. Maka $$\sum_{i=1}^{k+1} i = \frac{k^2 + k + 1}{2} + (k+1) = \frac{k^2 + 3k + 3}{2},$$ dan $$\frac{(k+1)^2 + (k+1) + 1}{2} = \frac{k^2 + 2k + 1 + k + 1 + 1}{2} = \frac{k^2 + 3k + 3}{2}.$$ Jadi langkahnya **sah** untuk setiap $k \in \mathbb{N}$. *Basis:* pada $n = 0$, ruas kiri $0$ dan ruas kanan $\frac{1}{2}$. Basisnya gagal. Kesalahannya ada di basis, bukan di aljabar. *Untuk $n$ mana klaim benar:* menurut proposisi utama, $\sum_{i=1}^{n} i = \frac{n^2 + n}{2}$ untuk setiap $n \in \mathbb{N}$, sehingga ruas kanan klaim selalu lebih besar tepat $\frac{1}{2}$. Klaim itu salah untuk **setiap** $n$. Ini contoh lain dari pola (a): langkah meneruskan kebenaran, tetapi tidak ada kebenaran yang diteruskan. **Latihan 7.1.13 (C2).** $P(0)$ menyatakan $0 \ne 1$, dan ini benar. Untuk $k \ge 1$, berlaku $k + 1 \ge 2$, sehingga $k + 1 \ne 1$. Jadi $P(k+1)$ benar, dan implikasi $P(k) \Rightarrow P(k+1)$ benar. Namun $P(1)$ salah. Prinsip induksi dengan basis $0$ menuntut (L) untuk **setiap** $k \ge 0$. Pada $k = 0$, implikasi $P(0) \Rightarrow P(1)$ salah, karena premisnya benar dan kesimpulannya salah. Jadi (L) tidak terpenuhi, dan prinsip itu tidak dapat diterapkan. Pola kegagalannya sama dengan contoh kuda: basis benar, langkah sah untuk hampir semua indeks, tetapi ada satu indeks pada awal rantai yang langkahnya gagal. Rantai implikasi terputus di sana. **Latihan 7.1.14 (C3).** (i) Langkah ini **sirkular**. Langkah itu memakai "rumus berlaku untuk semua $n$", padahal itulah yang hendak dibuktikan. Hipotesis induksi yang sah hanya $P(k)$ untuk $k$ yang tetap, dan $P(k+1)$ harus *diturunkan* dari premis yang sah; hipotesis induksi itu boleh dipakai bila diperlukan. Perbaikannya adalah langkah aljabar pada bukti proposisi utama. (ii) Ini hanya **pemeriksaan satu kasus**. Perhitungan itu membuktikan $P(3)$ secara langsung, sehingga juga membuktikan implikasi $P(2)\Rightarrow P(3)$. Namun ini baru satu indeks, yaitu $k=2$. Syarat (L) menuntut implikasi untuk *setiap* $k \in \mathbb{N}$ dengan $k$ sebarang. Perbaikannya sama dengan (i). ### Menuju 7.2 Dalam contoh bukti jumlah dan latihan aljabar induktif di unit ini, untuk membuktikan $P(k+1)$ cukup diketahui $P(k)$: suku baru ditambahkan pada jumlah lama. Tidak semua sifat bilangan asli berstruktur seperti itu. Pada 7.2 kita akan membuktikan bahwa setiap $n \ge 44$ dapat ditulis sebagai $6a + 9b + 20c$ dengan $a, b, c \in \mathbb{N}$. Representasi untuk $n$ diperoleh dari representasi untuk $n - 6$, bukan untuk $n - 1$. Hipotesis induksi lemah, yang hanya memuat $P(k)$, tidak menyediakan informasi itu. Induksi kuat memperluas asumsi lokal menjadi "$P(j)$ untuk semua $j$ dengan $n_0 \le j \le k$". Unit 7.2 akan membuktikan bahwa perluasan ini **diturunkan** dari prinsip induksi lemah, sehingga tidak ada prinsip baru yang diasumsikan. Kata "kuat" merujuk pada hipotesis lokal yang lebih luas, bukan pada prinsip yang secara logis lebih kuat. **Bacaan pembanding.** [R7-1] membahas pola dasar dan variasi induksi. Rujukan ini melengkapi penjelasan; pembuktian yang diperlukan telah dituliskan di atas. ## 7.2 Prinsip Induksi Matematika Kuat (Strong Induction) ### Motivasi: ketika satu langkah ke belakang tidak cukup Pada 7.1, langkah induksi lemah membuktikan $P(k+1)$ hanya dari $P(k)$. Banyak pernyataan tidak tersusun seperti itu. Untuk menunjukkan suatu sifat pada $n$, kita sering perlu kembali ke indeks yang lebih jauh, misalnya $n-6$, atau ke beberapa indeks sebelumnya sekaligus. Induksi kuat merumuskan pola ini. Dalam pembuktian $P(k+1)$, kita boleh mengasumsikan **semua** $P(j)$ untuk indeks $j$ dari basis sampai $k$. Unit ini menunjukkan bahwa perluasan ini tidak memerlukan asumsi baru tentang $\mathbb{N}$. Induksi kuat dapat diturunkan dari induksi lemah, dan sebaliknya. Kata "kuat" menggambarkan hipotesis lokal yang lebih luas dalam langkah pembuktian. Kata itu tidak berarti prinsipnya lebih kuat secara logis. Konvensi Bab 7 tetap berlaku: $\mathbb{N}=\{0,1,2,\dots\}$. Aritmetika dan urutan pada $\mathbb{N}$ dipinjam sebagai bahan kerja dengan pembahasan fondasi dan perluasannya pada Bab 8. Hukum asosiatif, komutatif, distributif, identitas 0 dan 1, serta ketertutupan penjumlahan dan perkalian pada $\mathbb{N}$ termasuk fakta aritmetika yang dipinjam di sini. Unit ini memakai secara khusus sifat-sifat berikut, yang **dipinjam**, bukan diturunkan dari logika saja: - (D1) $\le$ pada $\mathbb{N}$ adalah urutan total: refleksif, antisimetris, transitif, dan setiap dua unsur terbandingkan. $j0$. Jadi $44\le n-643$. Dalam setiap kasus, $6a+9b=43-20c$. Tulis $6a+9b=3t$ dengan $t=2a+3b\in\mathbb{N}$. - $c=0$: $3t=43$. Jika $t\le14$ maka $3t\le42<43$. Jika $t\ge15$ maka $3t\ge45>43$. Menurut totalitas dan diskretnya urutan (D1 dan D3), salah satu kasus terjadi, jadi $3t\ne43$. - $c=1$: $3t=23$. Jika $t\le7$ maka $3t\le21<23$. Jika $t\ge8$ maka $3t\ge24>23$. Jadi $3t\ne23$. - $c=2$: $6a+9b=3$. Jika $a\ge1$ atau $b\ge1$, maka $6a+9b\ge 6>3$. Jika $a=b=0$, maka $6a+9b=0\ne3$. Semua kasus mustahil. $\blacksquare$ Teorema 7.2.4 dan proposisi ini bersama-sama menunjukkan bahwa 44 adalah titik awal terkecil yang mungkin. Untuk setiap $n_0\le 43$, klaim "semua $n\ge n_0$ dapat ditulis" gagal pada $n=43$. **Batas klaim.** Proposisi ini **tidak** menyatakan bahwa semua $n<44$ gagal. Banyak yang dapat ditulis, misalnya $0=6\cdot0$, $6$, $9$, $20$, $39=6\cdot5+9$, $40=20\cdot2$, $41=6\cdot2+9+20$, dan $42=6\cdot7$. Klaimnya hanya tentang 43. **Representasi tidak dijamin tunggal.** Teorema menyatakan keberadaan saksi, bukan ketunggalannya. Representasi yang dibangun oleh bukti hanyalah salah satunya (lihat Latihan 7.2.9). ### Kesalahan umum 1. **Indeks di luar jangkauan.** Memakai $P(n-6)$ ketika $n-6k$ juga tidak disediakan oleh hipotesis induksi; klaim itu boleh dipakai hanya jika telah mempunyai pembenaran independen. Luasnya hipotesis bukan izin untuk mengasumsikan kesimpulan. 5. **Salah memahami kata "kuat".** Kata itu tidak berarti prinsip baru yang lebih kuat secara logis (7.2.2). ### Latihan **Latihan 7.2.6 (jangkauan hipotesis).** Perhatikan "bukti" berikut. *"Klaim: setiap $n\ge44$ dapat ditulis $6a+9b+20c$. Basis: $44=6\cdot4+20\cdot1$. Langkah: untuk $n>44$, menurut hipotesis induksi kuat $n-6$ dapat ditulis, tambahkan 1 pada $a$."* (a) Tentukan semua $n$ yang membuat langkah ini memakai indeks di luar jangkauan. (b) Perbaiki buktinya. *Pembahasan.* (a) Hipotesis pada $n$ hanya mencakup $44\le j0$ mempunyai pendahulu $n-1\in\mathbb{N}$ dengan $(n-1)+1=n$ dan $n-10$ memenuhi $m\ge1$. - $\mathbb{N}$ dipandang sebagai $\{z\in\mathbb{Z}:z\ge0\}$. --- ### Unsur terkecil **Definisi 7.3.1 (unsur terkecil).** Misalkan $(X,\le)$ himpunan terurut, yaitu $\le$ refleksif, antisimetris, dan transitif, dan misalkan $A\subseteq X$. Unsur $m$ disebut **unsur terkecil** dari $A$ jika dua syarat berikut terpenuhi: 1. $m\in A$; 2. untuk setiap $a\in A$ berlaku $m\le a$. Dalam subbab ini, $X$ adalah $\mathbb{N}$, $\mathbb{Z}$, atau $\mathbb{R}$ dengan urutan biasa. Untuk $m\in X$, syarat (2) menyatakan bahwa $m$ adalah **batas bawah** $A$. Unsur terkecil adalah batas bawah yang *sekaligus anggota* $A$. Perbedaan ini penting. Himpunan kosong mempunyai setiap $m\in X$ sebagai batas bawah, karena syarat (2) benar secara hampa. Namun himpunan kosong tidak mempunyai unsur terkecil, karena syarat (1) tidak dapat dipenuhi. **Proposisi 7.3.2 (ketunggalan).** Jika $m$ dan $m'$ keduanya unsur terkecil dari $A\subseteq X$, maka $m=m'$. *Bukti.* Karena $m'\in A$ dan $m$ batas bawah $A$, berlaku $m\le m'$. Dengan alasan yang sama, $m'\le m$. Menurut antisimetri urutan pada $X$, $m=m'$. $\blacksquare$ Bukti ini hanya memakai antisimetri. Jadi ketunggalan berlaku di setiap himpunan terurut. Yang tidak selalu berlaku adalah *keberadaan* unsur terkecil. Karena ketunggalan sudah terjamin, notasi $\min A$ sah dipakai, tetapi **hanya setelah** keberadaannya terbukti. --- ### Pernyataan prinsip **Teorema 7.3.3 (Prinsip Urutan Baik).** Setiap $S\subseteq\mathbb{N}$ dengan $S\neq\varnothing$ mempunyai unsur terkecil. Pernyataan ini dibuktikan sebagai Teorema 7.3.4 di bawah, jadi bukan aksioma baru. Syarat $S\neq\varnothing$ **wajib**. Tanpa syarat itu, pernyataannya salah, sebab $\varnothing\subseteq\mathbb{N}$ tidak mempunyai unsur terkecil. Prinsip ini merupakan sifat **$\mathbb{N}$ dengan urutan biasanya**. Ini bukan sifat setiap himpunan terurut, bahkan bukan sifat setiap himpunan terurut total. Lihat bagian *Himpunan terurut yang tidak berurut baik* di bawah. --- ### Status logis: dua arah dengan asumsi yang dipisahkan Pada buku ini, rantai deduksinya adalah: $$\text{induksi lemah (asumsi, 7.1)}\ \Longrightarrow\ \text{induksi kuat (teorema, 7.2)}\ \Longrightarrow\ \text{urutan baik (Teorema 7.3.4)}.$$ Setelah itu, Teorema 7.3.5 menunjukkan arah balik. Tabel berikut mencatat apa yang boleh dipakai pada setiap arah. | Arah | Boleh dipakai | Tidak boleh dipakai | |---|---|---| | Induksi kuat $\Rightarrow$ urutan baik | induksi kuat (dari 7.2), (A1)-(A3), separasi | urutan baik dalam bentuk apa pun | | Urutan baik $\Rightarrow$ induksi lemah | urutan baik, (A1)-(A4), separasi | induksi lemah atau kuat dalam bentuk apa pun | #### Arah pertama **Teorema 7.3.4 (induksi kuat mengakibatkan urutan baik).** Asumsikan prinsip induksi kuat dengan basis eksplisit dari Subbab 7.2, beserta (A1)-(A3). Maka setiap $S\subseteq\mathbb{N}$ yang tak kosong mempunyai unsur terkecil. *Bukti.* Misalkan $S\subseteq\mathbb{N}$ dan $S\ne\varnothing$. Andaikan $S$ **tidak** mempunyai unsur terkecil. Untuk $S$ yang tetap ini, definisikan predikat $$P(n):\quad n\notin S .$$ Kita buktikan $P(n)$ untuk semua $n\in\mathbb{N}$ dengan induksi kuat berbasis $n_0=0$. *Basis $P(0)$.* Andaikan $0\in S$. Menurut (A2), $0\le s$ untuk setiap $s\in S$. Jadi $0$ adalah unsur terkecil $S$, dan ini bertentangan dengan pengandaian. Maka $0\notin S$. *Langkah.* Ambil sembarang $k\in\mathbb{N}$. Asumsikan, sebagai hipotesis induksi kuat, bahwa $P(j)$ berlaku untuk semua $j$ dengan $0\le j\le k$. Artinya, tidak ada $j\le k$ yang menjadi anggota $S$. Kita tunjukkan $P(k+1)$. Andaikan $k+1\in S$. Ambil sembarang $s\in S$ dan bandingkan $s$ dengan $k+1$. Menurut keterbandingan (A1), berlaku $k+1\le s$ atau $s\le k+1$. - Jika $k+1\le s$, tidak ada yang perlu dibuktikan. - Jika $s\le k+1$, maka menurut (A3) berlaku $s\le k$ atau $s=k+1$. - Subkasus $s\le k$ mustahil. Hipotesis induksi memberi $s\notin S$, padahal $s\in S$. - Subkasus $s=k+1$ memberi $k+1\le s$ menurut refleksivitas. Dalam setiap kemungkinan, $k+1\le s$. Karena $s\in S$ sembarang dan $k+1\in S$, maka $k+1$ adalah unsur terkecil $S$. Ini kontradiksi. Jadi $k+1\notin S$. Menurut induksi kuat, $n\notin S$ untuk setiap $n\in\mathbb{N}$. Karena $S\subseteq\mathbb{N}$, setiap anggota $S$ adalah suatu $n\in\mathbb{N}$ dengan $n\in S$, dan itu mustahil. Maka $S=\varnothing$, bertentangan dengan $S\ne\varnothing$. Pengandaian salah, sehingga $S$ mempunyai unsur terkecil. Unsur itu tunggal menurut Proposisi 7.3.2. $\blacksquare$ **Di mana urutan total dipakai.** Pada langkah induksi, kita harus membandingkan anggota *sembarang* $s\in S$ dengan $k+1$. Seandainya ada $s$ yang tak terbandingkan dengan $k+1$, maka $k+1$ tidak dapat disimpulkan sebagai batas bawah $S$, dan bukti runtuh. Sifat diskret (A3) dipakai untuk mengubah "$s$ di bawah $k+1$" menjadi "$s\le k$", sehingga $s$ masuk ke dalam jangkauan hipotesis induksi. **Catatan (bentuk tanpa basis terpisah).** Induksi kuat juga dapat ditulis sebagai $\forall n\,[(\forall jn_0$.* Karena $m\in C$, berlaku $m\ge n_0$ dan $\neg P(m)$. Karena $P(n_0)$ benar, $m\ne n_0$. Jadi $m>n_0$. 2. *$m-1$ ada dan $m-1\ge n_0$.* Dari $0\le n_00$. Menurut (A4), pendahulu $m-1\in\mathbb{N}$ ada dan $(m-1)+1=m$. Karena $n_0<(m-1)+1$, sifat (A3) memberi $n_0\le m-1$. 3. *$m-1\notin C$.* Seandainya $m-1\in C$, minimalitas $m$ memberi $m\le m-1$. Bersama $m-1\le m$, antisimetri memberi $m=m-1$, bertentangan dengan $m-10}=\{x\in\mathbb{R}: x>0\}$, dengan urutan biasa, tidak mempunyai unsur terkecil. *Bukti.* Himpunan ini tak kosong karena $1\in\mathbb{R}_{>0}$. Ambil sembarang $x>0$. Berdasarkan sifat urutan medan $\mathbb{R}$ yang dipinjam, berlaku $x/2>0$ dan $x-x/2=x/2>0$. Jadi $x/2\in\mathbb{R}_{>0}$ dan $x/20}$, bilangan $0$ adalah batas bawah, tetapi $0\notin\mathbb{R}_{>0}$. Konsep batas bawah terbesar (infimum) termasuk bahasan bab lanjut dan tidak dipakai di sini. Pernyataan "setiap himpunan bagian tak kosong dari himpunan terurut mempunyai unsur terkecil" adalah **salah**. Prinsip Urutan Baik hanya dibuktikan untuk $(\mathbb{N},\le)$. Himpunan bagian $\mathbb{Z}$ yang tak kosong dan terbatas di bawah memang mempunyai unsur terkecil, tetapi fakta itu perlu dibuktikan tersendiri (Latihan 7.3.19). --- ### Pola bukti "kontra-contoh terkecil" Teorema 7.3.5 memperlihatkan pola yang dapat dipakai ulang: 1. Tulis himpunan kontra-contoh $C$ secara berpembatas, melalui separasi pada $\mathbb{N}$. 2. Andaikan $C\ne\varnothing$, lalu ambil $m=\min C$. Langkah ini sah karena $C$ tak kosong. 3. Gunakan basis atau kasus kecil untuk menunjukkan bahwa $m$ cukup besar, sehingga objek lebih kecil yang dibutuhkan memang ada di wilayah klaim. 4. Gunakan minimalitas: setiap objek di wilayah klaim yang lebih kecil dari $m$ bukan kontra-contoh. Dari situ, turunkan bahwa $m$ juga bukan kontra-contoh, atau bangun kontra-contoh yang lebih kecil dari $m$. 5. Simpulkan $C=\varnothing$. Objek pembanding tidak harus $m-1$. Pada Latihan 7.3.13, objek pembandingnya adalah suatu faktor sejati $a$ dengan $2\le a0$, terdapat tepat satu pasangan $(q,r)\in\mathbb{Z}\times\mathbb{Z}$ dengan $$x=mq+r\qquad\text{dan}\qquad 0\le r0$. Jadi himpunan ini tidak mempunyai unsur terkecil. Himpunan itu juga memuat anggota negatif: jika $x<0$, ambil $q=0$; jika $x\ge0$, ambil $q=x+1$ dan gunakan $m\ge1$ untuk memperoleh $x-m(x+1)\le-1$. Prinsip Urutan Baik juga tidak berlaku padanya karena himpunan itu bukan himpunan bagian $\mathbb{N}$. Pembatasan pada $\mathbb{N}$ justru yang memungkinkan prinsip itu dipakai. **Langkah 2: $S$ tak kosong.** Ambil $q_0=-|x|\in\mathbb{Z}$, sehingga $r_0=x-m(-|x|)=x+m|x|$. - Karena $m\ge 1$ dan $|x|\ge 0$, perkalian dengan bilangan taknegatif $|x|$ memberi $m|x|\ge 1\cdot|x|=|x|$. - Karena $|x|\ge -x$, berlaku $x+|x|\ge 0$. Jadi $$r_0=x+m|x|\ \ge\ x+|x|\ \ge\ 0 .$$ Maka $r_0\in\mathbb{N}$ dengan saksi $q_0$, sehingga $r_0\in S$. **Langkah 3: ambil minimum.** Menurut Prinsip Urutan Baik, $S$ mempunyai unsur terkecil $r$. Karena $r\in S$, ada $q\in\mathbb{Z}$ dengan $r=x-mq$, yaitu $x=mq+r$. Karena $r\in\mathbb{N}$, berlaku $r\ge 0$. **Langkah 4: $r0$, berlaku $r-m0-m=-m$. Jadi $|r-r'|-7$; - jika $q\le-2$, maka $5q\le-10\le-7$. Setiap bilangan bulat memenuhi $q\ge-1$ atau $q\le-2$. Jadi syarat $5q\le-7$ setara dengan $q\le-2$. Nilai $q=-2,-3,-4,\dots$ menghasilkan $r=3,8,13,\dots$, sehingga $S=\{3,8,13,18,\dots\}$. Saksi dari Langkah 2 adalah $q_0=-7$, yang memberi $r_0=-7+35=28\in S$. Unsur terkecil $S$ adalah $3$, dengan $q=-2$. Pemeriksaan: $$5\cdot(-2)+3=-10+3=-7,\qquad 0\le 3<5.$$ Penulisan $-7=5\cdot(-1)+(-2)$ juga benar secara aljabar, tetapi sisanya negatif. Penulisan itu adalah pembulatan hasil bagi ke arah nol, dan bukan pasangan yang dimaksud teorema. **Kasus $m=0$.** Persamaan $x=0\cdot q+r$ memaksa $r=x$, sedangkan syarat $0\le r<0$ tidak dapat dipenuhi oleh bilangan apa pun. Jadi, untuk setiap $x$, tidak ada pasangan yang memenuhi teorema. Di dalam bukti, dua langkah runtuh: - Langkah 2 runtuh karena $x+0\cdot|x|=x$ dapat negatif. Misalnya, untuk $x=-3$, diperoleh $S=\varnothing$. - Langkah 4 runtuh karena $r-00$ (Latihan 7.3.16). Jika bukti langsung ingin diulang untuk $m<0$, saksi $q_0=-|x|$ pada Langkah 2 harus diganti. --- ### Catatan tentang Subbab 4.4 (diagram Hasse) Bukti rekonstruksi diagram Hasse pada Subbab 4.4 memakai induksi kuat pada ukuran interval sebagai prinsip pinjaman. Subbab 7.2-7.3 sekarang memberi status yang jelas untuk **prinsip induksinya**: induksi kuat diturunkan dari induksi lemah, dan Prinsip Urutan Baik adalah perumusan yang ekuivalen dengannya. Subbab ini **tidak** membuktikan teori ukuran atau kardinalitas berhingga. Fakta tentang ukuran interval yang dipakai pada 4.4 tetap berstatus pinjaman. Kita juga tidak menambahkan teorema pengurutan topologis. --- ### Kesalahan umum 1. **Melupakan syarat tak kosong.** "Ambil unsur terkecil $C$" baru sah setelah $C\ne\varnothing$ diketahui atau diandaikan. 2. **Memakai Prinsip Urutan Baik di luar $\mathbb{N}$.** $\mathbb{Z}$ dan $\mathbb{R}_{>0}$ tidak berurut baik. Untuk himpunan bagian $\mathbb{Z}$, keberadaan minimum memerlukan argumen tambahan, seperti keterbatasan di bawah. 3. **Menyamakan batas bawah dengan unsur terkecil.** Unsur terkecil wajib menjadi anggota himpunan. 4. **Mengabaikan basis dalam argumen kontra-contoh terkecil.** Tanpa basis, $m-1$ mungkin tidak ada, atau berada di bawah $n_0$ sehingga di luar wilayah klaim. 5. **Penalaran melingkar.** Membuktikan induksi dari urutan baik dan urutan baik dari induksi, lalu menyatakan keduanya terbukti tanpa asumsi. 6. **Himpunan yang salah pada pembagian Euclid.** Mengambil minimum dari $\{x-mq: q\in\mathbb{Z}\}$ tidak sah. Himpunan itu bukan himpunan bagian $\mathbb{N}$ dan, untuk $m>0$, tidak terbatas di bawah, sehingga tidak mempunyai minimum. 7. **Diam-diam menganggap $m>0$.** Kekeliruan ini terjadi ketika teorema dipakai untuk pembagi nol atau negatif. --- ### Latihan **Latihan 7.3.10 (kasus kosong).** (a) Tunjukkan bahwa $\varnothing$ tidak mempunyai unsur terkecil, walaupun setiap $m\in\mathbb{N}$ merupakan batas bawahnya. (b) Tunjuk satu-satunya tempat di bukti Teorema 7.3.4 yang memakai $S\ne\varnothing$. Jelaskan apa yang terjadi bila argumen dijalankan untuk $S=\varnothing$. (c) Pada Teorema 7.3.5, mengapa kasus $C=\varnothing$ bukan masalah? **Latihan 7.3.11.** Tentukan apakah setiap himpunan berikut mempunyai unsur terkecil, beserta alasannya: (a) $\{n\in\mathbb{N}: n^2>50\}$; (b) $\{n\in\mathbb{N}: n^2<0\}$; (c) $\{z\in\mathbb{Z}: z<0\}$; (d) $\{z\in\mathbb{Z}: z^2<10\}$; (e) $\{x\in\mathbb{R}: 050$. Untuk $n\le 7$, kemonotonan kuadrat pada $\mathbb{N}$ (pinjaman) memberi $n^2\le 49$, sehingga $n$ bukan anggota. Jadi unsur terkecilnya $8$. (b) Himpunan ini kosong, sehingga tidak ada unsur terkecil. Hal ini tidak bertentangan dengan Prinsip Urutan Baik, karena prinsip itu mensyaratkan himpunan tak kosong. (c) Tidak ada unsur terkecil (Proposisi 7.3.6). (d) Gunakan kemonotonan kuadrat (pinjaman). Jika $|z|\ge4$, maka $z^2=|z|^2\ge16$. Jika $|z|\le3$, maka $z^2\le 9$. Jadi himpunannya $\{-3,-2,\dots,3\}$, dan dari daftar berhingga ini terlihat langsung bahwa unsur terkecilnya $-3$. Himpunan ini termuat di $\mathbb{Z}$ dan terbatas di bawah, sejalan dengan Latihan 7.3.19. (e) Tidak ada unsur terkecil. Untuk $x$ dengan $04$, yaitu $m\ge 5$, dan $m-1\ge 4$. - Minimalitas $m$ memberi $m-1\notin C$, sehingga $2^{m-1}\ge (m-1)^2$. - Akibatnya $2^m=2\cdot 2^{m-1}\ge 2(m-1)^2$. - Untuk $m\ge5$, berlaku $2(m-1)^2-m^2=m^2-4m+2=(m-2)^2-2$. Karena $m-2\ge3$, kemonotonan kuadrat (pinjaman) memberi $(m-2)^2\ge9$, sehingga $(m-2)^2-2\ge 7>0$. - Jadi $2^m> m^2$, bertentangan dengan $m\in C$. Maka $C=\varnothing$. Untuk $n=3$, berlaku $2^3=8<9=3^2$, sehingga klaim untuk semua $n\ge3$ salah. Perlu dicatat bahwa $P(0)$, $P(1)$, dan $P(2)$ benar, sedangkan $P(3)$ salah. Jadi basis $4$ bukan pilihan sembarangan. Hukum $2^m=2\cdot2^{m-1}$ adalah aritmetika pinjaman sampai 7.4. **Latihan 7.3.13.** Misalkan $C=\{n\in\mathbb{N}: n\ge2 \text{ dan } n \text{ tidak mempunyai pembagi prima}\}$. Andaikan $C\ne\varnothing$ dan ambil $m=\min C$. - Jika $m$ prima, maka $m\mid m$ karena $m=m\cdot1$, sehingga $m$ mempunyai pembagi prima. Ini mustahil. Jadi $m$ tidak prima. - Karena $m\ge2$ dan $m$ tidak prima, $m$ mempunyai pembagi positif $a$ dengan $a\ne1$ dan $a\ne m$. Tulis $m=ab$. Karena $a,m>0$, berlaku $b\ge1$, sehingga $a\le m$. Jadi $2\le a\le m-1$. - Karena $a\ge2$ dan $an_0$) gagal. Tidak ada $k=m-1\ge n_0$ yang dapat dipakai pada langkah, sehingga kontradiksi tidak muncul. **Latihan 7.3.15.** (a) Untuk setiap $q\in\mathbb{Z}$, nilai $r=-7-5q$ memberi solusi. Sebaliknya, setiap solusi memenuhi $r=-7-5q$. Jadi himpunan semua solusinya adalah $\{(q,-7-5q): q\in\mathbb{Z}\}$, yang tak berhingga banyaknya. (b) Menurut Contoh 7.3.9, syarat $-7-5q\ge0$ setara dengan $q\le-2$. Syarat $-7-5q<5$ setara dengan $5q>-12$: - jika $q\le-3$, maka $5q\le-15\le-12$, sehingga syaratnya gagal; - jika $q\ge-2$, maka $5q\ge-10>-12$, sehingga syaratnya terpenuhi. Jadi syarat kedua setara dengan $q\ge-2$. Satu-satunya solusi adalah $(q,r)=(-2,3)$, sesuai dengan Contoh 7.3.9 dan ketunggalan pada Teorema 7.3.8. Jika hanya syarat $r\ge0$ yang dipakai, nilai sisanya adalah $3,8,13,\dots$, yaitu tepat himpunan $S$ pada contoh itu. (c) Semua solusi berbentuk $(q,23-5q)$ dengan $q\in\mathbb{Z}$. - Syarat $23-5q\ge0$ berarti $5q\le23$. Jika $q\le4$, maka $5q\le20\le23$. Jika $q\ge5$, maka $5q\ge25>23$. Jadi syarat ini setara dengan $q\le4$. - Syarat $23-5q<5$ berarti $5q>18$. Jika $q\ge4$, maka $5q\ge20>18$. Jika $q\le3$, maka $5q\le15\le18$. Jadi syarat ini setara dengan $q\ge4$. Maka $q=4$ dan $r=3$. Pemeriksaan: $5\cdot4+3=23$. **Latihan 7.3.16.** (a) *Keberadaan.* Karena $|m|=-m>0$, Teorema 7.3.8 memberi $(q_1,r)$ dengan $x=(-m)q_1+r$ dan $0\le r<-m=|m|$. Ambil $q=-q_1$. Maka $x=mq+r$. *Ketunggalan.* Misalkan $x=mq+r=mq'+r'$ dengan $0\le r,r'<|m|$. Maka $x=(-m)(-q)+r=(-m)(-q')+r'$. Ketunggalan pada Teorema 7.3.8 untuk pembagi $-m$ memberi $-q=-q'$ dan $r=r'$, sehingga $q=q'$. (b) Untuk $x=-7$, $m=-5$: $(q,r)=(2,3)$, karena $(-5)\cdot 2+3=-7$. Untuk $x=7$, $m=-5$: $(q,r)=(-1,2)$, karena $(-5)(-1)+2=7$. (c) Dengan $q_0=-|x|$, diperoleh $x-m(-|x|)=x+m|x|=x-|m|\,|x|$, yang dapat negatif. Misalnya, untuk $x=7$ dan $m=-5$, hasilnya $7-35=-28$. Saksi penggantinya adalah $q_0=|x|$, yang memberi $x-m|x|=x+|m|\,|x|\ge x+|x|\ge0$. **Latihan 7.3.17.** Persamaan $x=0\cdot q+r$ memaksa $r=x$, sedangkan $0\le r<0$ mustahil. Jadi tidak ada pasangan untuk $x$ mana pun. Nasib langkah-langkah bukti Teorema 7.3.8 adalah sebagai berikut: - **Langkah 2 runtuh.** $S$ dapat kosong. Untuk $x=-3$, $S=\{r\in\mathbb{N}: r=-3\}=\varnothing$. - **Langkah 4 runtuh.** $r-00$ mempunyai pendahulu $n-1\in\mathbb{N}$ dengan $(n-1)+1=n$. - (A4) Untuk $m,n\in\mathbb{N}$ ada $\min(m,n)\in\mathbb{N}$, dan $k\le m$ serta $k\le n$ jika dan hanya jika $k\le\min(m,n)$. - (A5) Salinan bilangan diidentifikasi sehingga $\mathbb{N}\subseteq\mathbb{Z}\subseteq\mathbb{Q}\subseteq\mathbb{R}$. Hukum asosiatif, komutatif, distributif, identitas, dan ketertutupan penjumlahan/perkalian pada masing-masing sistem dipinjam; $\mathbb{Z}$ tertutup terhadap pengurangan. Urutan sesuai dengan operasi: penjumlahan menjaga urutan, dan perkalian faktor positif menjaga ketaksamaan. Pada $\mathbb{Q}$, invers $1/x$ tersedia dan bukan nol untuk $x\ne0$. Untuk model biaya real, aritmetika $\mathbb{R}_{\ge0}$ juga dipinjam. Fakta paritas elementer mengikuti pembahasan 6.2–6.3; pembagian Euclid telah dibuktikan pada Teorema 7.3.8. ### Pernyataan teorema **Teorema 7.4.1 (Rekursi pada $\mathbb{N}$).** Misalkan $X$ himpunan, $a\in X$, dan $F:\mathbb{N}\times X\to X$ fungsi. Maka terdapat tepat satu fungsi $u:\mathbb{N}\to X$ sehingga $$u(0)=a \qquad\text{dan}\qquad u(n+1)=F\bigl(n,u(n)\bigr)\ \text{untuk setiap } n\in\mathbb{N}.$$ **Catatan tentang hipotesis.** - Hipotesis $a\in X$ sudah menjamin $X$ tak kosong, jadi tidak perlu syarat terpisah. - Syarat tipe $F:\mathbb{N}\times X\to X$ adalah syarat **ketertutupan**: untuk setiap $n$ dan setiap $x\in X$, nilai $F(n,x)$ terdefinisi dan berada lagi di $X$. Bila aturan rekursi bisa keluar dari $X$ atau tidak terdefinisi di sebagian $X$, teorema tidak berlaku (lihat bagian kasus batas). **Versi tanpa indeks.** Jika $g:X\to X$, definisikan $F(n,x)=g(x)$. Grafik $F$ adalah $$\{((n,x),y)\in(\mathbb{N}\times X)\times X : y=g(x)\},$$ yang ada oleh separasi dan jelas total serta bernilai tunggal. Teorema lalu memberi tepat satu $u$ dengan $u(0)=a$ dan $u(n+1)=g(u(n))$. **Contoh penerapan langsung yang membayar pinjaman 7.1.** - *Jumlah berhingga.* Ambil $X=\mathbb{N}$, $a=0$, dan $F(n,x)=x+(n+1)$. Diperoleh tepat satu $S$ dengan $S(0)=0$ dan $S(n+1)=S(n)+(n+1)$. Inilah arti resmi $\sum_{i=1}^{n} i$ di 7.1, termasuk jumlah kosong untuk $n=0$. Lebih umum, untuk fungsi suku $a_i$ yang diberikan pada indeks asli positif dan bernilai real, ambil $X=\mathbb{R}$, nilai awal $0$, serta $F(n,x)=x+a_{n+1}$. Ketertutupan penjumlahan real menjamin tipenya; teorema menghasilkan tepat satu fungsi jumlah parsial yang digunakan dalam seluruh contoh 7.1. - *Pangkat.* Untuk $c\in\mathbb{Z}$, ambil $X=\mathbb{Z}$, $a=1$, dan $g(x)=cx$. Diperoleh tepat satu barisan, ditulis $c^n$, dengan $$c^0=1 \qquad\text{dan}\qquad c^{n+1}=c\cdot c^n. \tag{Pw}$$ Dalam unit ini **satu-satunya** sifat pangkat yang dipakai adalah persamaan (Pw) untuk $c=2$ dan $c=3$. Persamaan itu kini terbukti sebagai bagian dari Teorema Rekursi. Hukum pangkat lain, seperti $c^{m+n}=c^m c^n$, tidak dipakai dan tidak diklaim di sini. Sumber [R7-2] membahas rekursi pada $\mathbb{N}$, dalam kerangka teori himpunan; pembahasan di sini bukan teori komputabilitas. Bukti di bawah disusun mandiri dan tidak diklaim sebagai terjemahan sumber tersebut. ### Strategi bukti Kita tidak dapat langsung "mendefinisikan $u(n)$ untuk semua $n$". Yang dapat kita kerjakan dengan induksi adalah potongan berhingga: 1. **Aproksimasi.** Untuk tiap $n$, fungsi pada $I_n=\{0,1,\dots,n\}$ yang mematuhi resep sejauh resep itu masuk akal di $I_n$. 2. **Eksistensi aproksimasi** (Lema 7.4.4): dengan induksi pada $n$, menambah satu pasangan pada grafik. 3. **Kompatibilitas** (Lema 7.4.5): dua aproksimasi selalu sepakat pada irisan domainnya. 4. **Pengumpulan tanpa pemilihan** (Lema 7.4.7): himpunan $\mathcal{C}$ yang memuat *semua* grafik aproksimasi dibentuk dengan separasi pada $\mathcal{P}(\mathbb{N}\times X)$. Gabungannya, $U=\bigcup\mathcal{C}$, adalah calon grafik $u$. 5. **$U$ grafik fungsi total** (Lema 7.4.8), lalu **$u$ memenuhi basis dan rekursi** (Lema 7.4.9). 6. **Keunikan**: induksi biasa ditambah kesamaan titik demi titik. Langkah 4 menunjukkan secara eksplisit himpunan pembatas untuk pengumpulan aproksimasi. Semua grafik sudah berada di $\mathcal{P}(\mathbb{N}\times X)$, sehingga separasi cukup untuk membentuk $\mathcal{C}$. Tidak diperlukan Aksioma Pilihan atau Penggantian. Sesudah keunikan aproksimasi dibuktikan, bahkan grafik penugasan $n\mapsto G_n$ dapat dibentuk dengan separasi di $\mathbb{N}\times\mathcal{P}(\mathbb{N}\times X)$. Yang harus dihindari adalah menganggap penugasan itu sudah menjadi himpunan tanpa menunjukkan pembentukannya. ### Aproksimasi dan eksistensinya Tetapkan $X$, $a$, dan $F$ seperti pada teorema. **Definisi 7.4.2 (ruas awal).** Untuk $n\in\mathbb{N}$, $I_n=\{k\in\mathbb{N}:k\le n\}$, yang ada oleh separasi pada $\mathbb{N}$. Oleh (A1), $0\in I_n$ dan $n\in I_n$. Oleh (A2): $$I_0=\{0\},\qquad I_{n+1}=I_n\cup\{n+1\},\qquad n+1\notin I_n. \tag{I}$$ Selain itu, jika $k0$, pemanggilan memicu tepat satu subpemanggilan `Count(n-1)`. Argumen ini sah karena $n-1\in\mathbb{N}$ oleh (A3). Jika dan setelah subpemanggilan itu selesai dengan nilai $r$, pemanggilan `Count(n)` selesai dengan nilai $r+1$ tanpa pemanggilan lain. - (M4) Biaya: pemanggilan basis berbiaya $c_0$. Pemanggilan non-basis berbiaya $c$ untuk pekerjaannya sendiri, ditambah biaya seluruh eksekusi subpemanggilannya. Di sini $c_0,c\in\mathbb{N}$, dan bilangan real taknegatif juga boleh. *Banyak pemanggilan* eksekusi `Count(n)` adalah $1$ (pemanggilan itu sendiri) ditambah banyak pemanggilan dalam eksekusi subpemanggilannya, jika ada. Model ini tidak mengklaim apa pun tentang waktu riil pada mesin, tumpukan memori, atau ukuran bilangan. Klaim hanya berlaku sejauh model ini. **Rekurensi pembanding.** Oleh Teorema Rekursi, ada tepat satu $K:\mathbb{N}\to\mathbb{N}$ dengan $K_0=1$ dan $K_{n+1}=K_n+1$ (ambil $X=\mathbb{N}$, $a=1$, $g(x)=x+1$). Ada pula tepat satu $T$ dengan $T_0=c_0$ dan $T_{n+1}=T_n+c$ (ambil $X=\mathbb{N}$, $a=c_0$, $g(x)=x+c$; untuk biaya real taknegatif gunakan $X=\mathbb{R}_{\ge0}$ dengan aritmetika yang dipinjam). **Proposisi 7.4.11 (terminasi, nilai, pemanggilan, biaya).** Untuk setiap $n\in\mathbb{N}$, eksekusi `Count(n)` 1. berhenti dan mengembalikan $n$; 2. terdiri atas tepat $K_n$ pemanggilan; 3. berbiaya tepat $T_n$. *Bukti.* Induksi lemah pada $n$ untuk konjungsi ketiga klaim. *Basis $n=0$.* Oleh (M2), eksekusi berhenti dengan nilai $0$, terdiri atas $1=K_0$ pemanggilan, dan berbiaya $c_0=T_0$. *Langkah.* Misalkan klaim berlaku untuk $k$. Karena $k+1>0$, oleh (M3) `Count(k+1)` memicu tepat satu subpemanggilan dengan argumen $(k+1)-1=k$ (A3). Oleh hipotesis induksi, subpemanggilan itu berhenti dengan nilai $k$, memuat $K_k$ pemanggilan, dan berbiaya $T_k$. Maka `Count(k+1)` berhenti dengan nilai $k+1$, terdiri atas $1+K_k=K_{k+1}$ pemanggilan, dan berbiaya $c+T_k=T_{k+1}$ (M4). $\blacksquare$ **Proposisi 7.4.12 (bentuk eksplisit).** Untuk setiap $n\in\mathbb{N}$: $K_n=n+1$ dan $T_n=c_0+nc$. *Bukti.* Induksi lemah pada $n$. - *Basis.* $K_0=1=0+1$ dan $T_0=c_0=c_0+0\cdot c$. - *Langkah.* Jika $K_k=k+1$ dan $T_k=c_0+kc$, maka $$K_{k+1}=(k+1)+1 \qquad\text{dan}\qquad T_{k+1}=c_0+kc+c=c_0+(k+1)c,$$ dengan distributivitas (A5). $\blacksquare$ Jadi, dalam model (M1)-(M4), `Count(n)` berhenti, mengembalikan $n$, melakukan tepat $n+1$ pemanggilan (termasuk pemanggilan basis), dan berbiaya $c_0+nc$. **Mengapa terminasi tidak gratis: ukuran yang menurun.** Bukti terminasi di atas bertumpu pada fakta bahwa argumen turun tepat satu dan tetap di $\mathbb{N}$. Prinsip umumnya adalah lema berikut. **Lema 7.4.13 (tak ada rantai turun tak berhingga di $\mathbb{N}$).** Tidak ada fungsi $s:\mathbb{N}\to\mathbb{N}$ dengan $s(i+1)0$. Pendahulu tersedia oleh (A3), dan grafiknya dibentuk dengan separasi. Teorema Rekursi memberi $s:\mathbb{N}\to\mathbb{N}$ dengan $s(0)=n$ dan $s(i+1)=p(s(i))$. Andaikan $s(i)\ne0$ untuk semua $i$. Maka $s(i+1)=s(i)-1