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 $m<k$ maupun $m>k$, 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. $j<k$ berarti $j\le k$ dan $j\ne k$. Selain itu $0\le j$ untuk setiap $j\in\mathbb{N}$.
• (D2) Untuk setiap $j,k\in\mathbb{N}$, jika $j\le k+1$ maka $j\le k$ atau $j=k+1$.
• (D3) $k<k+1$ untuk setiap $k$, sehingga bersama (D1) dan (D2) berlaku $j<k+1 \iff j\le k$.
• (D4) Penjumlahan menjaga urutan dan dapat dicoret: $m\le n \iff m+p\le n+p$. Perkalian dengan bilangan asli menjaga urutan. Untuk $n\ge m$, selisih $n-m$ berada dalam $\mathbb{N}$ dan $(n-m)+m=n$.

Induksi lemah dari 7.1 adalah satu-satunya prinsip induksi yang diasumsikan.

Pernyataan prinsip

Untuk $n_0,k\in\mathbb{N}$, tulis

$$[n_0,k]=\{j\in\mathbb{N}: n_0\le j\le k\},$$

yang terbentuk melalui separasi pada $\mathbb{N}$ (Bab 3).

Teorema 7.2.1 (Prinsip Induksi Kuat, bentuk dengan basis eksplisit). Misalkan $n_0\in\mathbb{N}$ dan $P$ suatu predikat pada $\mathbb{N}$. Jika

1. (basis) $P(n_0)$, dan
2. (langkah kuat) untuk setiap $k\ge n_0$:

$$\Big(\forall j\in[n_0,k]\;P(j)\Big)\;\Rightarrow\;P(k+1),$$

maka $P(n)$ berlaku untuk semua $n\ge n_0$.

Anteseden pada langkah kuat disebut hipotesis induksi kuat. Seperti pada 7.1, hipotesis ini adalah asumsi lokal dalam pembuktian sebuah implikasi untuk $k$ sembarang yang tetap. Kita tidak menganggap kesimpulan universal sudah benar. Jangkauannya tepat $[n_0,k]$. Indeks di bawah $n_0$ atau di atas $k$ tidak tercakup dalam hipotesis ini. Pemakaian klaim pada indeks tersebut memerlukan pembenaran independen; yang salah adalah menganggapnya otomatis tersedia dari hipotesis induksi kuat.

Induksi lemah mengimplikasikan induksi kuat

Bukti teorema. Dalam bukti ini, induksi lemah (7.1) adalah prinsip yang diasumsikan. Pernyataan yang dibuktikan adalah induksi kuat.

Andaikan $P(n_0)$ dan langkah kuat berlaku. Definisikan predikat

$$Q(k):\quad \forall j\in[n_0,k]\;P(j),$$

yakni "$P$ berlaku di seluruh $[n_0,k]$". Kita buktikan $Q(k)$ untuk semua $k\ge n_0$ dengan induksi lemah berbasis $n_0$.

Basis $Q(n_0)$. Ambil $j$ dengan $n_0\le j\le n_0$. Menurut antisimetri (D1), $j=n_0$, dan $P(n_0)$ diberikan. Jadi $Q(n_0)$.

Langkah. Ambil $k\ge n_0$ sembarang dan asumsikan $Q(k)$ (hipotesis induksi lemah untuk $Q$). Karena $Q(k)$ tepat merupakan anteseden langkah kuat, langkah kuat memberi $P(k+1)$. Sekarang ambil $j$ dengan $n_0\le j\le k+1$. Menurut (D2), $j\le k$ atau $j=k+1$.

• Jika $j\le k$, maka $j\in[n_0,k]$, sehingga $Q(k)$ memberi $P(j)$.
• Jika $j=k+1$, maka $P(j)$ adalah $P(k+1)$, yang baru diperoleh.

Dalam kedua kasus berlaku $P(j)$. Jadi $Q(k+1)$. Langkah ini menggabungkan seluruh hasil lama yang dimuat $Q(k)$ dengan satu hasil baru $P(k+1)$.

Induksi lemah memberi $Q(k)$ untuk semua $k\ge n_0$. Akhirnya, untuk $n\ge n_0$, terapkan $Q(n)$ pada $j=n$. Karena $n_0\le n\le n$ (refleksivitas, D1), diperoleh $P(n)$. $\blacksquare$

Inti bukti ini adalah pergantian predikat. Induksi kuat untuk $P$ tidak lain adalah induksi lemah untuk predikat "kumulatif" $Q$.

Induksi kuat mengimplikasikan induksi lemah

Proposisi 7.2.2. Jika Prinsip Induksi Kuat diterima, Prinsip Induksi Lemah dapat diturunkan darinya.

Bukti. Dalam arah ini, induksi kuat adalah prinsip yang diasumsikan. Pernyataan yang dibuktikan adalah induksi lemah.

Andaikan $P(n_0)$ dan, untuk setiap $k\ge n_0$, $P(k)\Rightarrow P(k+1)$. Kita periksa hipotesis induksi kuat. Basisnya $P(n_0)$, yang sudah diberikan. Untuk langkah kuat, ambil $k\ge n_0$ dan asumsikan $P(j)$ untuk semua $j\in[n_0,k]$. Karena $n_0\le k\le k$ (D1), asumsi ini memuat $P(k)$. Implikasi lemah lalu memberi $P(k+1)$. Jadi langkah kuat berlaku, dan induksi kuat menyimpulkan $P(n)$ untuk semua $n\ge n_0$. $\blacksquare$

Kesimpulan kedua arah. Dengan latar aritmetika pinjaman (D1)–(D4), setiap prinsip dapat diturunkan dari yang lain. Keduanya ekuivalen. Induksi kuat tidak membuktikan pernyataan yang tidak dapat dibuktikan induksi lemah. Ia hanya mengizinkan hipotesis lokal yang lebih luas, sehingga sebagian bukti menjadi lebih langsung untuk ditulis. Sebaliknya, setiap bukti induksi lemah sudah merupakan bukti induksi kuat yang hanya memakai sebagian hipotesisnya.

Bentuk tanpa basis terpisah dan basis hampa

Induksi kuat sering dinyatakan tanpa basis terpisah:

Proposisi 7.2.3 (bentuk tanpa basis terpisah). Jika untuk setiap $n\ge n_0$

$$\Big(\forall j\,\big(n_0\le j< n \Rightarrow P(j)\big)\Big)\;\Rightarrow\;P(n),$$

maka $P(n)$ untuk semua $n\ge n_0$.

Basisnya tidak hilang, melainkan tersembunyi. Untuk $n=n_0$, tidak ada $j$ dengan $n_0\le j<n_0$, karena $j<n_0$ dan $n_0\le j$ bersama-sama memberi $j=n_0$ (antisimetri) sekaligus $j\ne n_0$. Karena itu anteseden "$P(j)$ untuk semua $j$ seperti itu" benar secara hampa. Implikasi untuk $n=n_0$ lalu menuntut $P(n_0)$ tanpa bantuan apa pun. Siapa pun yang membuktikan langkah dalam bentuk ini harus membuktikan $P(n_0)$ secara langsung pada kasus $n=n_0$.

Untuk $n_0=0$, syarat $0\le j$ selalu dipenuhi (D1), sehingga bentuk ini menjadi

$$\Big(\forall j<n\;P(j)\Big)\Rightarrow P(n)\quad\text{untuk setiap } n\in\mathbb{N}.$$

Pada $n=0$ tidak ada $j<0$, sehingga antesedennya hampa dan langkah itu tetap mewajibkan $P(0)$. Bentuk inilah yang dipakai pada 7.3.

Bukti bahwa bentuk ini sah. Asumsikan hipotesis bentuk tanpa basis. Kita turunkan hipotesis bentuk dengan basis eksplisit, lalu terapkan teorema 7.2.1.

• Basis. Pada $n=n_0$ antesedennya benar secara hampa, jadi $P(n_0)$.
• Langkah kuat. Ambil $k\ge n_0$ dan asumsikan $P(j)$ untuk semua $j\in[n_0,k]$. Menurut (D3), $j<k+1 \iff j\le k$. Jadi asumsi ini sama dengan "$P(j)$ untuk semua $n_0\le j<k+1$". Karena $n_0\le k<k+1$, transitivitas memberi $k+1\ge n_0$, sehingga hipotesis untuk $n=k+1$ memberi $P(k+1)$.

Teorema 7.2.1 memberi $P(n)$ untuk semua $n\ge n_0$. $\blacksquare$

Contoh utama: representasi $6a+9b+20c$

Teorema 7.2.4. Untuk setiap $n\in\mathbb{N}$ dengan $n\ge 44$, terdapat $a,b,c\in\mathbb{N}$ sehingga $n=6a+9b+20c$.

Strategi. Dari representasi untuk $n-6$, kita peroleh representasi untuk $n$ dengan menambah satu pada koefisien 6. Lompatan mundur sebesar 6 hanya sah bila $n-6$ masih berada dalam jangkauan hipotesis, yakni $n-6\ge 44$. Itu berarti $n\ge 50$. Keenam nilai $44,\dots,49$ tidak dapat dijangkau dengan cara ini. Semuanya harus diselesaikan langsung.

Tulis $P(n)$ untuk "$\exists a,b,c\in\mathbb{N}:\ n=6a+9b+20c$". Kita pakai bentuk tanpa basis terpisah (7.2.3) dengan $n_0=44$.

Bukti. Ambil $n\ge 44$ dan asumsikan hipotesis induksi kuat: $P(j)$ untuk semua $j$ dengan $44\le j<n$. Kita tunjukkan $P(n)$. Menurut totalitas (D1), $n<50$ atau $50\le n$. Menurut (D3), $n<50$ berarti $n\le 49$.

Kasus $44\le n\le 49$ (enam basis). Hipotesis tidak dipakai. Saksinya:

Kasus $n=44$ adalah kasus yang anteseden hipotesisnya hampa (tidak ada $j$ dengan $44\le j<44$). Saksi di atas membuktikannya tanpa bantuan.

Kasus $n\ge 50$. Menurut (D4), $n-6\in\mathbb{N}$ dan $(n-6)+6=n\ge 50=44+6$, sehingga setelah mencoret 6 diperoleh $n-6\ge 44$. Juga $n-6<n$, karena $6>0$. Jadi $44\le n-6<n$, dan $n-6$ berada dalam jangkauan hipotesis. Hipotesis memberi $a',b',c'\in\mathbb{N}$ dengan $n-6=6a'+9b'+20c'$. Maka

$$n=(n-6)+6=6(a'+1)+9b'+20c',$$

dan $a'+1,\,b',\,c'\in\mathbb{N}$. Jadi $P(n)$.

Kedua kasus memberi $P(n)$. Menurut 7.2.3, $P(n)$ berlaku untuk semua $n\ge 44$. $\blacksquare$

Mengapa enam basis, bukan satu. Langkah induksi hanya menghubungkan $n$ dengan $n-6$. Dengan menurunkan 6 berulang-ulang dari sembarang $n\ge 44$, kita berhenti tepat pada satu nilai di $\{44,\dots,49\}$, yakni nilai yang bersisa sama dengan $n$ jika dibagi 6. Keenam basis menutup keenam kelas sisa $0,1,\dots,5$ modulo 6. Itulah sebabnya keenamnya dibutuhkan. Uraian ini adalah intuisi yang memakai pembagian bersisa, yang baru dibuktikan pada 7.3. Buktinya sendiri adalah argumen induksi di atas, yang tidak memakai sisa pembagian.

Kalau basisnya hanya $P(44)$, argumen gagal pada $n=45$. Di sana $n-6=39<44$, dan hipotesis induksi tidak menyatakan apa pun tentang 39. Bilangan 39 sebenarnya dapat ditulis ($39=6\cdot5+9\cdot1$), tetapi fakta itu tidak termuat dalam hipotesis dan harus dibuktikan terpisah. Kecukupan basis adalah sifat argumen, bukan sifat kebenaran klaim.

Pembandingan dengan bentuk basis eksplisit. Dalam bentuk 7.2.1 dengan $n_0=44$, basisnya hanya $P(44)$. Kelima nilai $45,\dots,49$ muncul di dalam langkah kuat, ketika $k+1\le 49$, dan diselesaikan dengan saksi tanpa memakai hipotesis. Ini sah karena implikasi boleh dibuktikan tanpa memakai antesedennya. Kedua penulisan memuat pekerjaan yang sama.

Batas tajam: 43 tidak dapat ditulis

Proposisi 7.2.5. Tidak ada $a,b,c\in\mathbb{N}$ dengan $43=6a+9b+20c$.

Bukti. Andaikan ada. Karena $6a+9b\ge 0$, diperoleh $20c\le 43$. Maka $c\in\{0,1,2\}$, sebab $c\ge 3$ memberi $20c=60+20(c-3)\ge 60>43$. 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-6<n_0$, atau memakai $P(k-1)$ ketika $k=n_0$. Setiap pemakaian hipotesis harus disertai pemeriksaan $n_0\le j\le k$ (atau $n_0\le j<n$).
2. Basis yang kurang. Jika langkah hanya memakai indeks $n-d$, maka semua indeks $n_0,\dots,n_0+d-1$ harus ditangani langsung, karena untuk indeks-indeks itu $n-d$ berada di bawah $n_0$.
3. Lupa kasus hampa. Dalam bentuk tanpa basis, kasus $n=n_0$ harus dibuktikan langsung. Menulis "menurut hipotesis" pada kasus itu tidak membuktikan apa pun.
4. Sirkularitas. Hipotesis induksi kuat memuat $P(j)$ untuk $n_0\le j\le k$, dan tidak memuat $P(k+1)$. Memakai kesimpulan sebagai premis yang belum terbukti membuat argumen sirkular. Klaim $P(j)$ untuk $j>k$ 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 j<n$. Indeks $n-6$ termasuk jangkauan tepat ketika $n-6\ge44$, yakni $n\ge50$ (syarat $n-6<n$ selalu dipenuhi). Untuk $n=45,46,47,48,49$, indeks $n-6\in\{39,\dots,43\}$ berada di bawah 44, sehingga langkahnya tidak sah. Pada $n=49$, indeks yang dipakai adalah 43, yang menurut 7.2.5 bahkan tidak dapat ditulis. Pada indeks lain, kegagalannya terletak pada argumennya, bukan pada klaimnya: $39=6\cdot5+9$, $40=20\cdot2$, $41=6\cdot2+9+20$, dan $42=6\cdot7$ semuanya dapat ditulis, tetapi tidak satu pun termuat dalam hipotesis. (b) Tangani $45,\dots,49$ langsung dengan saksi pada tabel 7.2.4, dan pakai langkah $n-6$ hanya untuk $n\ge50$. Hasilnya adalah bukti 7.2.4.

Latihan 7.2.7 (jumlah basis). (a) Mengapa bukti 7.2.4 tidak dapat menghapus salah satu basis $44,\dots,49$ tanpa mengubah argumennya? (b) Misalkan langkahnya diganti menjadi "kurangi 9, tambah satu pada $b$". Berapa basis yang diperlukan, dan apa saksinya?

Pembahasan. (a) Jika suatu $m\in\{44,\dots,49\}$ dihapus dari kasus langsung, implikasi langkah pada $n=m$ tidak terbukti, karena $m-6\le43$ berada di luar jangkauan. Hipotesis prinsip 7.2.3 menuntut implikasi itu untuk setiap $n\ge44$. Jadi prinsipnya tidak dapat diterapkan, dan bukti seluruhnya runtuh, bukan hanya untuk $m$. Ini kegagalan argumen, bukan kesalahan klaim: $P(m)$ tetap benar (tabel 7.2.4). (b) Langkah $n-9$ sah tepat bila $n-9\ge44$, yakni $n\ge53$. Diperlukan sembilan kasus langsung $44,\dots,52$. Saksi $44,\dots,49$ ada di tabel 7.2.4, ditambah $50=6\cdot5+20\cdot1$, $51=6\cdot1+9\cdot5$, dan $52=6\cdot2+20\cdot2$. Untuk $n\ge53$: dari $n-9=6a'+9b'+20c'$ diperoleh $n=6a'+9(b'+1)+20c'$. Secara umum, untuk $d$ bilangan asli positif dan argumen yang hanya memakai $n-d$, seluruh $n_0,\dots,n_0+d-1$ harus ditangani langsung.

Latihan 7.2.8 (saksi 50–55). Dengan aturan pada 7.2.4, tentukan saksi untuk $n=50,\dots,55$ dan periksa aritmetikanya.

Pembahasan. Setiap $n$ memakai saksi $n-6$ dengan $a$ ditambah 1:

Setiap $n-6$ berada di $[44,49]\subseteq[44,n-1]$, jadi berada dalam jangkauan hipotesis.

Latihan 7.2.9 (ketidakunikan). Tunjukkan bahwa 18 mempunyai dua representasi berbeda. Apakah hal ini mengganggu bukti 7.2.4?

Pembahasan. $18=6\cdot3+9\cdot0+20\cdot0$ dan $18=6\cdot0+9\cdot2+20\cdot0$. Kedua tripel $(3,0,0)$ dan $(0,2,0)$ berbeda. Hal ini tidak mengganggu bukti, karena $P(n)$ adalah pernyataan keberadaan. Bukti hanya memerlukan satu saksi untuk $n-6$, dan saksi mana pun cukup. Yang keliru adalah menyebut "representasi dari $n$" seolah-olah tunggal. Ketidakunikan juga muncul pada sebagian $n\ge44$, misalnya $54=6\cdot9=9\cdot6$ dan $44=6\cdot4+20\cdot1=6\cdot1+9\cdot2+20\cdot1$. Namun tidak semua $n$ demikian. Untuk 46, ketaksamaan $20c\le46$ memaksa $c\le2$. Jika $c=0$, diperlukan $3t=46$, padahal $t\le15$ memberi $3t\le45$ dan $t\ge16$ memberi $3t\ge48$. Jika $c=1$, diperlukan $3t=26$, padahal $t\le8$ memberi $3t\le24$ dan $t\ge9$ memberi $3t\ge27$. Jika $c=2$, tersisa $6a+9b=6$. Nilai $b\ge1$ mustahil karena ruas kiri paling sedikit 9, sehingga $b=0$ dan $6a=6$. Nilai $a=0$ memberi 0, sedangkan $a\ge2$ memberi paling sedikit 12; maka $a=1$. Jadi 46 hanya mempunyai representasi $(1,0,2)$.

Latihan 7.2.10 (basis hampa dan sirkularitas). Seorang mahasiswa menulis: "Dalam bentuk tanpa basis, hipotesis untuk $n=n_0$ selalu benar, jadi $P(n_0)$ tidak perlu dibuktikan." Ia juga menulis: "Karena hipotesis kuat mencakup semua indeks sebelumnya, untuk membuktikan $P(n)$ saya boleh memakai $P(n)$." Diagnosislah kedua pernyataan.

Pembahasan. Pernyataan pertama membalik logikanya. Karena antesedennya benar secara hampa, implikasi $(\text{benar})\Rightarrow P(n_0)$ ekuivalen dengan $P(n_0)$ itu sendiri. Membuktikan langkah pada $n=n_0$ berarti membuktikan $P(n_0)$ secara langsung. Pernyataan kedua sirkular. Jangkauan hipotesis adalah $n_0\le j<n$, dan $n$ sendiri tidak termasuk, sehingga memakai $P(n)$ berarti mengasumsikan kesimpulan.

Transisi ke 7.3

Induksi kuat menurunkan $P(n)$ dari semua kasus yang lebih kecil. Dengan kata lain, prinsip ini bekerja "dari bawah ke atas". Prinsip urutan baik memandang hal yang sama dari arah sebaliknya. Kita tidak lagi membangun kebenaran ke atas. Kita mengandaikan ada kegagalan, lalu mengambil kegagalan terkecil. Unit 7.3 menyatakan prinsip itu: setiap himpunan bagian tak kosong dari $\mathbb{N}$ mempunyai unsur terkecil. Prinsip ini akan dibuktikan dari induksi kuat dalam bentuk $(\forall j<n\,P(j))\Rightarrow P(n)$, dengan anteseden hampa pada $n=0$ yang telah dibahas pada 7.2.3. Kemudian induksi lemah akan diturunkan kembali darinya. Dengan begitu ketiga prinsip tersusun tanpa lingkaran asumsi, dan prinsip urutan baik siap dipakai untuk membuktikan pembagian Euclid, termasuk pembagian bersisa yang pada unit ini hanya muncul sebagai intuisi.

7.3 Prinsip Urutan Baik (Well-Ordering Principle)

Motivasi

Induksi pada Subbab 7.1 dan 7.2 bergerak naik. Kita mulai dari basis, lalu melangkah ke indeks berikutnya. Banyak argumen justru lebih alami bila bergerak turun. Misalkan suatu klaim gagal. Ambil kegagalan yang paling kecil, lalu tunjukkan bahwa kegagalan itu mustahil, misalnya karena darinya dapat dibentuk kegagalan yang lebih kecil lagi.

Pola "ambil yang terkecil" baru sah bila ada jaminan bahwa himpunan kegagalan, asalkan tidak kosong, memang mempunyai anggota terkecil. Jaminan itu adalah Prinsip Urutan Baik.

Subbab ini membahas empat hal:

1. definisi unsur terkecil beserta ketunggalannya;
2. status logis Prinsip Urutan Baik terhadap induksi, dengan asumsi setiap arah dipisahkan secara tegas;
3. contoh himpunan terurut yang tidak berurut baik;
4. satu aplikasi lengkap, yaitu teorema pembagian Euclid.

Konvensi dan bahan pinjaman. Seperti pada 7.1-7.2, $\mathbb{N}=\{0,1,2,\dots\}$ dengan urutan biasa $\le$. Sifat-sifat berikut termasuk aritmetika yang dipinjam. Sifat-sifat ini bukan akibat logika murni, dan Bab 8 membahas aksioma serta perluasan sistem bilangan dengan tetap mengasumsikan keberadaan struktur Peano. Hukum yang belum diturunkan tetap diberi status pinjaman.

• (A1) Urutan total. $\le$ bersifat refleksif, antisimetris, dan transitif. Untuk setiap $a,b\in\mathbb{N}$ berlaku $a\le b$ atau $b\le a$. Notasi $a<b$ berarti $a\le b$ dan $a\ne b$.
• (A2) Nol terbawah. $0\le n$ untuk setiap $n\in\mathbb{N}$.
• (A3) Diskret. Untuk $j,k\in\mathbb{N}$, jika $j\le k+1$ maka $j\le k$ atau $j=k+1$. Setara dengan itu, $j<k+1$ mengakibatkan $j\le k$.
• (A4) Pendahulu. Setiap $n>0$ mempunyai pendahulu $n-1\in\mathbb{N}$ dengan $(n-1)+1=n$ dan $n-1<n$.
• (A5) Aritmetika $\mathbb{Z}$ dan $\mathbb{R}$.
  • Penjumlahan menjaga urutan.
  • Perkalian dengan bilangan taknegatif menjaga $\le$, dan perkalian dengan bilangan positif menjaga $<$.
  • Nilai mutlak memenuhi $|x|\ge0$, $|x|\ge x$, $|x|\ge -x$, $|ab|=|a|\,|b|$, dan $|a|=a$ untuk $a\ge0$.
  • Jika $z\in\mathbb{Z}$ dan $z\ne0$, maka $|z|\ge1$. Khususnya, bilangan bulat $m>0$ 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 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 j<n\ P(j))\Rightarrow P(n)]$. Dalam bentuk ini, langkahnya berbunyi sebagai berikut. Misalkan tidak ada $j<n$ yang anggota $S$, dan $n\in S$. Untuk setiap $s\in S$, kemungkinan $s<n$ tertutup, sehingga $n\le s$ menurut keterbandingan. Akibatnya $n$ menjadi unsur terkecil, dan terjadi kontradiksi.

Untuk $n=0$, tidak ada $j\in\mathbb{N}$ dengan $j<0$, menurut (A2) dan antisimetri. Jadi hipotesisnya benar secara hampa, dan argumen yang sama tetap harus dijalankan untuk menyimpulkan $0\notin S$. Basis tidak hilang. Basis hanya terserap ke dalam langkah, sehingga langkah itu sendiri mewajibkan pembuktian $P(0)$.

Arah kedua

Teorema 7.3.5 (urutan baik mengakibatkan induksi lemah). Asumsikan Prinsip Urutan Baik beserta (A1)-(A4), dan jangan asumsikan induksi dalam bentuk apa pun. Misalkan $n_0\in\mathbb{N}$ dan $P$ suatu predikat pada $\mathbb{N}$ yang dapat dirumuskan dalam bahasa himpunan dengan parameter, sehingga separasi berlaku, dan yang memenuhi dua syarat:

1. $P(n_0)$;
2. untuk setiap $k\ge n_0$, berlaku $P(k)\Rightarrow P(k+1)$.

Maka $P(n)$ berlaku untuk setiap $n\ge n_0$.

Bukti. Bentuk himpunan kontra-contoh melalui separasi pada $\mathbb{N}$:

$$C=\{\,n\in\mathbb{N} : n_0\le n \ \text{dan}\ \neg P(n)\,\}.$$

Andaikan $C\ne\varnothing$. Menurut Prinsip Urutan Baik, $C$ mempunyai unsur terkecil $m$.

1. $m>n_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_0<m$ diperoleh $m>0$. 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-1<m$.
4. $P(m-1)$. Bilangan $m-1$ memenuhi $m-1\ge n_0$ tetapi bukan anggota $C$. Menurut definisi $C$, ini berarti $P(m-1)$.
5. Kontradiksi. Syarat langkah dengan $k=m-1\ge n_0$ memberi $P(m)$, padahal $\neg P(m)$.

Jadi $C=\varnothing$. Untuk setiap $n\ge n_0$, karena $n\notin C$, berlaku $P(n)$. $\blacksquare$

Basis berperan tepat pada butir 1. Tanpa basis, kontra-contoh terkecil bisa saja $m=n_0$. Dalam keadaan itu, tidak ada indeks $k=m-1\ge n_0$ yang dapat diumpankan ke langkah induksi (lihat Latihan 7.3.14).

Menghindari sirkularitas

Kedua teorema di atas bersyarat. Teorema 7.3.4 mengasumsikan induksi kuat, yang pada 7.2 diturunkan dari induksi lemah. Teorema 7.3.5 mengasumsikan urutan baik. Jika keduanya dirangkai, hasilnya hanyalah "induksi lemah $\Rightarrow$ induksi lemah". Rangkaian itu tidak membuktikan prinsip mana pun dari ketiadaan.

Kesimpulan yang sah adalah sebagai berikut. Relatif terhadap aritmetika pinjaman 7.1–7.2, (A1)-(A4), dan separasi, induksi lemah, induksi kuat, dan urutan baik saling ekuivalen. Salah satunya harus diterima sebagai titik awal. Pada buku ini, titik awal itu adalah induksi lemah (7.1), dan urutan baik berstatus teorema.

Ada satu ketergantungan lagi yang perlu dinyatakan secara jujur. Sifat (A1)-(A4) sendiri masih dipinjam. Bab 8 menurunkan sebagian hukum dari aksioma Peano dan tetap menandai hukum yang belum diturunkan. Ekuivalensi di atas berdiri di atas aritmetika pinjaman; pembahasan berikutnya tidak boleh dianggap otomatis menghapus semua pinjaman itu.

---

Himpunan terurut yang tidak berurut baik

Proposisi 7.3.6. Dengan urutan biasa, $\mathbb{Z}$ tidak berurut baik. Artinya, ada himpunan bagian tak kosong dari $\mathbb{Z}$ yang tidak mempunyai unsur terkecil.

Bukti. Ambil $\mathbb{Z}$ itu sendiri, yang tak kosong karena $0\in\mathbb{Z}$. Untuk sembarang $z\in\mathbb{Z}$, berlaku $z-1\in\mathbb{Z}$ dan $z-1<z$ (A5). Seandainya $z$ unsur terkecil, maka $z\le z-1$, dan ini bertentangan dengan $z-1<z$.

Argumen yang sama berlaku untuk $\{z\in\mathbb{Z}: z<0\}$, yang memuat $-1$, sebab $z<0$ mengakibatkan $z-1<z<0$. $\blacksquare$

Proposisi 7.3.7. Himpunan $\mathbb{R}_{>0}=\{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/2<x$, sehingga $x$ bukan unsur terkecil. $\blacksquare$

Kedua contoh ini terurut total. Jadi keterurutan total saja tidak cukup untuk menjamin adanya unsur terkecil. Pada $\mathbb{R}_{>0}$, 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 a<m$. Itulah ciri khas versi "kuat" dari pola ini.

---

Aplikasi: pembagian Euclid

Pembagian Euclid dipakai sebagai pinjaman pada Teorema 4.3.9; domainnya sama, yaitu bilangan bulat dengan pembagi positif. Sekarang kita membuktikannya secara mandiri dengan Prinsip Urutan Baik.

Teorema 7.3.8 (pembagian Euclid). Untuk setiap $x\in\mathbb{Z}$ dan $m\in\mathbb{Z}$ dengan $m>0$, terdapat tepat satu pasangan $(q,r)\in\mathbb{Z}\times\mathbb{Z}$ dengan

$$x=mq+r\qquad\text{dan}\qquad 0\le r<m .$$

Bukti.

Langkah 1: himpunan calon sisa. Definisikan, melalui separasi pada $\mathbb{N}$,

$$S=\{\,r\in\mathbb{N} : \text{ada } q\in\mathbb{Z} \text{ dengan } r=x-mq\,\}.$$

Kuantor "ada $q$" dibatasi pada himpunan $\mathbb{Z}$, dan anggota $S$ diambil dari himpunan $\mathbb{N}$ yang sudah tersedia.

Bandingkan dengan $\{x-mq: q\in\mathbb{Z}\}$. Untuk setiap anggotanya $x-mq$, anggota $x-m(q+1)=x-mq-m$ lebih kecil karena $m>0$. 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: $r<m$. Andaikan $r\ge m$. Maka $r-m\ge 0$, sehingga $r-m\in\mathbb{N}$. Selain itu,

$$r-m = x-mq-m = x-m(q+1),\qquad q+1\in\mathbb{Z},$$

sehingga $r-m\in S$. Karena $m>0$, berlaku $r-m<r$. Ini bertentangan dengan minimalitas $r$. Jadi $0\le r<m$, dan keberadaan pasangan terbukti.

Langkah 5: ketunggalan. Misalkan $x=mq+r=mq'+r'$ dengan $0\le r<m$ dan $0\le r'<m$. Maka

$$r-r'=m(q'-q).$$

Dari batas-batas $r$ dan $r'$ diperoleh $r-r'<m-0=m$ dan $r-r'>0-m=-m$. Jadi $|r-r'|<m$.

Andaikan $q'\ne q$. Maka $q'-q$ adalah bilangan bulat tak nol, sehingga $|q'-q|\ge 1$ (A5). Akibatnya

$$|r-r'|=|m|\,|q'-q|=m\,|q'-q|\ge m\cdot 1=m,$$

dan ini kontradiksi. Jadi $q=q'$, dan $r=x-mq=x-mq'=r'$. $\blacksquare$

Contoh 7.3.9 ($x=-7$, $m=5$). Di sini

$$S=\{\,r\in\mathbb{N}: \text{ada } q\in\mathbb{Z},\ r=-7-5q\,\}.$$

Syarat $-7-5q\ge 0$ setara dengan $5q\le -7$. Kedua arah kesetaraan dengan $q\le-2$ diperiksa sebagai berikut:

• jika $q\ge-1$, maka $5q\ge-5>-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-0<r$ salah.

Jika hanya batas atas $r<m$ dibuang tetapi $0\le r$ tetap disyaratkan, untuk $x\ge0$ semua pasangan $(q,x)$ dengan $q\in\mathbb{Z}$ menjadi solusi, sehingga tidak tunggal. Untuk $x<0$ tetap tidak ada solusi. Jadi syarat $m\ne0$ hakiki bagi keberadaan dan ketunggalan seperti dalam teorema.

Kasus $m<0$. Syarat $0\le r<m$ mustahil, karena $m<0\le r$. Jadi teorema dengan batas $r<m$ tidak berlaku tanpa perubahan. Salah satu bentuk yang lazim memakai batas $0\le r<|m|$. Bentuk ini diturunkan dari Teorema 7.3.8 dengan pembagi $-m>0$ (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}: 0<x\le1\}$; (f) $\{x\in\mathbb{R}: 0\le x\le 1\}$.

Latihan 7.3.12 (basis lain, kontra-contoh terkecil). Dengan argumen kontra-contoh terkecil, buktikan $2^n\ge n^2$ untuk setiap $n\ge 4$. Pangkat dipinjam sampai 7.4. Tunjukkan pula bahwa klaim yang sama untuk semua $n\ge 3$ salah.

Latihan 7.3.13 (kontra-contoh terkecil, bentuk kuat). Buktikan bahwa setiap $n\in\mathbb{N}$ dengan $n\ge 2$ mempunyai pembagi prima. Gunakan definisi pinjaman berikut:

• $a\mid b$ berarti ada $c\in\mathbb{Z}$ dengan $b=ac$;
• $p$ prima berarti $p\ge2$ dan pembagi positif $p$ hanyalah $1$ dan $p$.

Latihan 7.3.14 (peran basis). Ambil $n_0=3$ dan $P(n): n=n+1$. (a) Tunjukkan bahwa syarat langkah Teorema 7.3.5 berlaku, tetapi kesimpulannya salah. (b) Tunjuk butir bukti yang gagal.

Latihan 7.3.15 (semua solusi). (a) Tentukan semua $(q,r)\in\mathbb{Z}\times\mathbb{Z}$ dengan $-7=5q+r$, tanpa syarat apa pun pada $r$. (b) Dari himpunan solusi itu, tentukan semua solusi dengan $0\le r<5$, lalu cocokkan dengan Contoh 7.3.9. (c) Ulangi untuk $x=23$, $m=5$.

Latihan 7.3.16 (pembagi negatif). (a) Buktikan: untuk $x\in\mathbb{Z}$ dan $m\in\mathbb{Z}$ dengan $m<0$, terdapat tepat satu $(q,r)\in\mathbb{Z}\times\mathbb{Z}$ dengan $x=mq+r$ dan $0\le r<|m|$. (b) Hitung pasangan itu untuk $x=-7, m=-5$ dan untuk $x=7, m=-5$. (c) Jelaskan mengapa saksi $q_0=-|x|$ dari Langkah 2 gagal di sini, dan berikan saksi pengganti.

Latihan 7.3.17 (pembagi nol). Untuk $m=0$, tunjukkan bahwa tidak ada $x\in\mathbb{Z}$ yang mempunyai pasangan $(q,r)$ dengan $x=mq+r$ dan $0\le r<m$. Jelaskan nasib setiap langkah bukti Teorema 7.3.8.

Latihan 7.3.18 (diagnosis sirkularitas). Seorang penulis menyusun dua bukti.

• Bukti A: "Induksi lemah benar, sebab bila ada kontra-contoh, ambil yang terkecil menurut urutan baik, lalu turunkan kontradiksi."
• Bukti B: "Urutan baik benar, sebab dengan induksi kuat kita buktikan $n\notin S$ untuk semua $n$."

Penulis itu lalu menyatakan bahwa kedua prinsip telah dibuktikan tanpa asumsi. Diagnosis kesalahannya, lalu nyatakan kesimpulan yang sah.

Latihan 7.3.19 (himpunan bagian $\mathbb{Z}$ yang terbatas di bawah). Misalkan $S\subseteq\mathbb{Z}$ tak kosong dan ada $b\in\mathbb{Z}$ dengan $b\le s$ untuk setiap $s\in S$. Buktikan bahwa $S$ mempunyai unsur terkecil.

---

Pembahasan

Latihan 7.3.10.

(a) Unsur terkecil harus memenuhi $m\in\varnothing$, dan itu mustahil. Syarat batas bawah "untuk setiap $s\in\varnothing$, $m\le s$" benar secara hampa untuk setiap $m$. Jadi $\varnothing$ mempunyai banyak batas bawah, tetapi tidak mempunyai unsur terkecil.

(b) Syarat $S\ne\varnothing$ hanya dipakai pada kalimat terakhir: "$S=\varnothing$ bertentangan dengan $S\ne\varnothing$". Untuk $S=\varnothing$, seluruh induksi tetap berjalan dan menghasilkan "$n\notin S$ untuk semua $n$". Pernyataan itu benar dan tidak menimbulkan kontradiksi. Teorema memang tidak mengklaim apa pun tentang $\varnothing$.

(c) Prinsip Urutan Baik hanya diterapkan di bawah pengandaian $C\ne\varnothing$. Kasus $C=\varnothing$ justru adalah kesimpulan yang dituju. Kedua kasus dipisah menurut hukum penyisihan tengah, sehingga tidak ada kasus yang terlewat.

Latihan 7.3.11.

(a) Himpunan ini memuat $8$, karena $64>50$. 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 $0<x\le 1$, berlaku $0<x/2<x$ dan $x/2\le 1/2\le 1$.

(f) Unsur terkecilnya $0$, karena $0$ anggota himpunan dan $0\le x$ untuk setiap anggota $x$.

Pelajarannya: di luar $\mathbb{N}$, keberadaan minimum tidak otomatis dan harus diperiksa kasus demi kasus.

Latihan 7.3.12. Misalkan $P(n): 2^n\ge n^2$ dan $C=\{n\in\mathbb{N}: n\ge4,\ \neg P(n)\}$. Andaikan $C\ne\varnothing$ dan ambil $m=\min C$.

• Karena $2^4=16\ge16$, berlaku $m\ne 4$. Jadi $m>4$, 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 $a<m$, minimalitas memberi $a\notin C$. Maka $a$ mempunyai pembagi prima $p$, misalnya $a=pc$.
• Akibatnya $m=p(cb)$, sehingga $p\mid m$. Ini kontradiksi.

Objek pembanding di sini adalah faktor $a$, bukan $m-1$. Itulah sebabnya argumen ini sejalan dengan induksi kuat, bukan dengan langkah lemah $k\to k+1$.

Latihan 7.3.14.

(a) Untuk setiap $k$, pernyataan $P(k)$ salah, sehingga implikasi $P(k)\Rightarrow P(k+1)$ benar secara hampa. Namun $P(n)$ salah untuk setiap $n\ge3$.

(b) Basis $P(3)$ tidak berlaku. Dengan $C=\{n\in\mathbb{N}: n\ge3\}$, diperoleh $m=\min C=3=n_0$, sehingga butir 1 ($m>n_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-0<r$ salah, sehingga tidak ada penurunan.
• Langkah 5 tidak runtuh, tetapi menjadi hampa. Tidak ada pasangan yang memenuhi $0\le r<0$, sehingga implikasi ketunggalan benar tanpa isi. Jika hanya batas atas $r<m$ dibuang dan $0\le r$ dipertahankan, persamaan memaksa $r=x$. Untuk $x\ge0$, setiap $q\in\mathbb{Z}$ memberi solusi $(q,x)$ sehingga tidak tunggal; untuk $x<0$ tidak ada solusi.

Latihan 7.3.18. Bukti A mengasumsikan urutan baik, sedangkan Bukti B mengasumsikan induksi kuat, yang bertumpu pada induksi lemah. Jika keduanya dirangkai, hasilnya adalah "induksi lemah $\Rightarrow$ induksi lemah", yang tidak menetapkan salah satu prinsip tanpa asumsi awal. Yang sah hanyalah pernyataan bahwa kedua prinsip ekuivalen relatif terhadap aritmetika pinjaman 7.1–7.2, (A1)-(A4), dan separasi.

Di buku ini, induksi lemah diambil sebagai asumsi (7.1), dan urutan baik adalah teorema yang diturunkan darinya (Teorema 7.3.4). Teorema 7.3.5 hanya menunjukkan bahwa urutan baik tidak lebih lemah daripada asumsi itu. Status pinjaman (A1)-(A4) tetap berlaku sampai masing-masing sifat benar-benar diturunkan; pengantar Bab 8 bukan bukti bagi seluruh daftar itu.

Latihan 7.3.19. Bentuk himpunan berikut melalui separasi pada $\mathbb{N}$:

$$T=\{t\in\mathbb{N}: t+b\in S\}.$$

• $T$ tak kosong. Ambil $s\in S$. Maka $s-b\ge0$, sehingga $t=s-b\in\mathbb{N}$ dan $t+b=s\in S$.
• Ambil minimum. Menurut Prinsip Urutan Baik, $T$ mempunyai unsur terkecil $t_0$. Tulis $s_0=t_0+b$, sehingga $s_0\in S$.
• $s_0$ unsur terkecil $S$. Untuk sembarang $s\in S$, berlaku $s-b\in T$, sehingga $t_0\le s-b$, yaitu $s_0\le s$.

Jadi $s_0$ adalah unsur terkecil $S$.

Notasi citra $\{s-b:s\in S\}$ juga sah: himpunan yang sama dapat ditulis secara berpembatas sebagai $\{t\in\mathbb{N}:\exists s\in S,\ t=s-b\}$. Bentuk $T$ di atas langsung menampilkan himpunan pembatas $\mathbb{N}$ yang diperlukan untuk menerapkan urutan baik.

---

Menuju 7.4

Sejauh ini, induksi dan Prinsip Urutan Baik dipakai untuk membuktikan sifat objek yang sudah ada: jumlah, pangkat, dan sisa pembagian. Beberapa objek itu, khususnya jumlah berhingga dan pangkat, masih dipinjam. Keberadaannya justru bergantung pada definisi rekursif seperti $u(0)=a$ dan $u(n+1)=F(n,u(n))$.

Subbab 7.4 menutup celah itu. Di sana akan dibuktikan bahwa definisi semacam itu memang menentukan tepat satu fungsi $u:\mathbb{N}\to X$. Terminasi algoritme rekursif sederhana yang argumennya turun satu di $\mathbb{N}$ juga akan dibuktikan di sana, dengan urutan baik atau induksi terminasi.

7.4 Definisi Rekursif dan Analisis Barisan Rekursif

Motivasi: tiga hal yang sering tercampur

Pada 7.1 kita memakai lambang $\sum_{i=1}^{n} i$ dengan kesepakatan "jumlah kosong bernilai $0$, dan jumlah sampai $n+1$ diperoleh dengan menambahkan suku ke-$(n+1)$". Pada latihan kontra-contoh terkecil di 7.3 kita memakai $2^n$ dengan kesepakatan "$2^0=1$ dan $2^{n+1}=2\cdot 2^n$". Saat itu kedua kesepakatan dinyatakan sebagai pinjaman. Unit ini membayar pinjaman tersebut.

Ada tiga hal berbeda yang perlu dipisahkan.

1. Definisi rekursif adalah resep: nilai di $0$ ditetapkan, dan nilai di $n+1$ ditetapkan dari $n$ serta nilai di $n$. Resep belum tentu menghasilkan objek. Kalimat "mulai dari $a$, terapkan aturan, lalu lanjutkan selamanya" tidak menunjuk himpunan apa pun.
2. Teorema rekursi menjamin bahwa, dengan syarat tipe yang tepat, ada tepat satu fungsi $u:\mathbb{N}\to X$ yang memenuhi resep tersebut. Pernyataan inilah yang mengubah resep menjadi objek.
3. Induksi membuktikan sifat suatu objek yang sudah ada, misalnya bahwa barisan yang sudah terdefinisi memenuhi rumus eksplisit. Induksi tidak menciptakan fungsi. Prinsip induksi 7.1 berbicara tentang predikat $P(n)$, sedangkan "fungsi $u$" dalam predikat $P(n)$ harus sudah tersedia sebagai himpunan sebelum predikat itu dapat ditulis.

Kesalahan yang hendak dicegah adalah lingkaran berikut: "fungsi $u$ ada karena kita dapat menghitung $u(0)$, lalu $u(1)$, dan seterusnya, dan induksi menjamin kita dapat terus." Induksi memang menjamin bahwa untuk setiap $n$ ada potongan perhitungan sampai $n$ (Lema 7.4.4 di bawah). Namun dari "untuk setiap $n$ ada potongan" ke "ada satu fungsi pada seluruh $\mathbb{N}$" masih diperlukan langkah himpunan yang eksplisit, dan langkah itulah inti unit ini.

Konvensi dan bahan yang dipinjam

Seperti di seluruh Bab 7, $\mathbb{N}=\{0,1,2,\dots\}$, sedangkan bilangan asli beserta aritmetika dan urutannya diasumsikan. Bab 8 membahas aksioma Peano dan perluasan sistem bilangan; keberadaan struktur Peano tetap diasumsikan. Unit ini memakai bahan berikut.

Dari bab terdahulu. Aksioma separasi, pasangan, gabungan, dan himpunan kuasa (Bab 3). Pasangan terurut dan produk Kartesius $A\times B$ (Bab 4). Dari Bab 5: fungsi bertipe $A\to B$ ditentukan oleh grafiknya, yaitu himpunan bagian $G\subseteq A\times B$ yang

• total: untuk setiap $x\in A$ ada $y\in B$ dengan $(x,y)\in G$, dan
• bernilai tunggal: jika $(x,y)\in G$ dan $(x,y')\in G$, maka $y=y'$,

serta prinsip kesamaan titik demi titik: dua fungsi $A\to B$ sama bila nilainya sama di setiap $x\in A$. Induksi lemah (7.1, diasumsikan), induksi kuat (7.2, diturunkan), dan urutan baik (7.3, diturunkan).

Fakta aritmetika dan urutan yang dipinjam. Fakta-fakta ini bukan konsekuensi logika murni.

• (A1) $\le$ adalah urutan total pada $\mathbb{N}$, dan $0\le n$ untuk setiap $n$.
• (A2) Untuk $k,n\in\mathbb{N}$: $k\le 0 \iff k=0$; $k\le n+1 \iff (k\le n \text{ atau } k=n+1)$; $k<n+1\iff k\le n$; $k<n\iff k+1\le n$; dan $n<n+1$, sehingga $n+1\not\le n$.
• (A3) Setiap $n>0$ 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 $k<n$ maka $k+1\le n$, jadi $k+1\in I_n$ (A2).

Definisi 7.4.3 (aproksimasi pada ruas awal $I_n$). Himpunan $G$ disebut aproksimasi pada $I_n$ bila $G$ adalah grafik suatu fungsi $v:I_n\to X$ dengan

1. $v(0)=a$, dan
2. $v(k+1)=F(k,v(k))$ untuk setiap $k\in\mathbb{N}$ dengan $k<n$.

Pada syarat 2, $k$ dan $k+1$ keduanya di $I_n$, jadi kedua ruas bermakna. Karena $I_n\subseteq\mathbb{N}$, setiap aproksimasi memenuhi $G\subseteq I_n\times X\subseteq\mathbb{N}\times X$, sehingga $G\in\mathcal{P}(\mathbb{N}\times X)$. Seluruh syarat definisi ini dapat ditulis sebagai rumus dengan parameter $n,X,a,F$, dan rumus itu hanya berbicara tentang anggota himpunan yang sudah ada. Rumus semacam ini sah dipakai dalam separasi. Dengan $\Gamma_F$ grafik fungsi bertipe $F$, rumusnya dapat ditulis eksplisit:

$$\begin{aligned} \operatorname{Apr}(G,n):\quad &G\subseteq\mathbb{N}\times X\\ &\wedge\ \forall k\in\mathbb{N}\,\forall x\in X\ ((k,x)\in G\Rightarrow k\le n)\\ &\wedge\ \forall k\in\mathbb{N}\ (k\le n\Rightarrow\exists x\in X\ (k,x)\in G)\\ &\wedge\ \forall k\in\mathbb{N}\,\forall x,y\in X\ (((k,x)\in G\wedge(k,y)\in G)\Rightarrow x=y)\\ &\wedge\ (0,a)\in G\\ &\wedge\ \forall k\in\mathbb{N}\,\forall x,y\in X\ ((k<n\wedge(k,x)\in G\wedge(k+1,y)\in G)\Rightarrow((k,x),y)\in\Gamma_F). \end{aligned}$$

Totalitas dan ketunggalan memastikan bahwa baris terakhir tepat menyatakan aturan rekursi, bukan sekadar implikasi hampa. Semua parameter telah tersedia sebagai himpunan.

Lema 7.4.4 (eksistensi aproksimasi). Untuk setiap $n\in\mathbb{N}$ terdapat aproksimasi pada $I_n$.

Bukti. Induksi lemah pada $n$ dengan $P(n)$: "terdapat aproksimasi pada $I_n$".

Basis $n=0$. Oleh aksioma pasangan, $(0,a)$ ada dan $\{(0,a)\}$ ada. Karena $0\in I_0$ dan $a\in X$, berlaku $G_0=\{(0,a)\}\subseteq I_0\times X$. Kita periksa syaratnya:

• Total: satu-satunya anggota $I_0$ adalah $0$, dan $(0,a)\in G_0$.
• Bernilai tunggal: $G_0$ hanya memuat satu pasangan.
• Basis: $v(0)=a$.
• Rekursi: tidak ada $k\in\mathbb{N}$ dengan $k<0$ (A1), jadi syarat 2 benar secara hampa.

Maka $P(0)$ berlaku.

Langkah. Misalkan $n\in\mathbb{N}$ dan, sebagai hipotesis induksi lokal, $G$ aproksimasi pada $I_n$ dengan fungsi $v$. Karena $n\in I_n$, nilai $v(n)\in X$ ada. Karena $F$ bertipe $\mathbb{N}\times X\to X$, nilai

$$b=F(n,v(n))$$

ada dan $b\in X$. Definisikan

$$G'=G\cup\{(n+1,b)\},$$

yang ada oleh aksioma pasangan dan gabungan. Kita periksa bahwa $G'$ aproksimasi pada $I_{n+1}$.

• $G'\subseteq I_{n+1}\times X$. Dari $G\subseteq I_n\times X$ dan $I_n\subseteq I_{n+1}$ oleh (I), diperoleh $G\subseteq I_{n+1}\times X$. Selain itu $n+1\in I_{n+1}$ dan $b\in X$.

• Total. Ambil $k\in I_{n+1}$. Oleh (I), $k\in I_n$ atau $k=n+1$. Jika $k\in I_n$, maka $(k,v(k))\in G\subseteq G'$. Jika $k=n+1$, maka $(n+1,b)\in G'$.

• Bernilai tunggal. Misalkan $(k,x),(k,y)\in G'$. Ada tiga kasus.

  • Keduanya di $G$: maka $x=y$ karena $G$ bernilai tunggal.
  • Keduanya sama dengan $(n+1,b)$: maka $x=y=b$.
  • Satu di $G$ dan satu sama dengan $(n+1,b)$: maka $k\in I_n$ dan $k=n+1$, bertentangan dengan $n+1\notin I_n$ dari (I). Jadi kasus ini tidak terjadi.

  Akibatnya, fungsi $v'$ dengan grafik $G'$ memenuhi $v'(k)=v(k)$ untuk $k\in I_n$, sebab $(k,v(k))\in G'$, dan $v'(n+1)=b$.

• Basis. $v'(0)=v(0)=a$.

• Rekursi. Ambil $k<n+1$, yaitu $k\le n$ oleh (A2).

  • Jika $k<n$, maka $k,k+1\in I_n$, sehingga $v'(k+1)=v(k+1)=F(k,v(k))=F(k,v'(k))$.
  • Jika $k=n$, maka $v'(n+1)=b=F(n,v(n))=F(n,v'(n))$.

Jadi $P(n+1)$ berlaku. Oleh induksi lemah, $P(n)$ berlaku untuk semua $n$. $\blacksquare$

Perhatikan apa yang tidak dikatakan Lema 7.4.4. Lema 7.4.4 tidak memberikan satu fungsi pada $\mathbb{N}$, dan tidak memberikan barisan aproksimasi $(G_n)_{n\in\mathbb{N}}$ sebagai satu objek. Isinya hanya: untuk setiap $n$, himpunan aproksimasi pada $I_n$ tidak kosong.

Kompatibilitas

Lema 7.4.5 (kompatibilitas). Misalkan $G$ aproksimasi pada $I_m$ dengan fungsi $v$, dan $H$ aproksimasi pada $I_n$ dengan fungsi $w$. Maka $v(k)=w(k)$ untuk setiap $k\le\min(m,n)$.

Bukti. Tulis $p=\min(m,n)$ (A4). Jika $k\le p$, maka $k\le m$ dan $k\le n$, jadi $k$ berada di kedua domain. Kita buktikan untuk semua $k\in\mathbb{N}$ predikat

$$Q(k):\quad k\le p\ \Rightarrow\ \forall x,y\in X\ (((k,x)\in G\wedge(k,y)\in H)\Rightarrow x=y).$$

dengan induksi lemah pada $k$. Rumus ini tetap bermakna saat $k$ di luar domain kedua aproksimasi; jika $k\le p$, totalitas membuatnya setara dengan $v(k)=w(k)$.

Basis. $v(0)=a=w(0)$.

Langkah. Misalkan $Q(k)$ berlaku. Kita buktikan $Q(k+1)$; andaikan $k+1\le p$, karena jika tidak, $Q(k+1)$ benar secara hampa. Maka $k<k+1\le p$, sehingga $k\le p$, dan oleh $Q(k)$ berlaku $v(k)=w(k)$. Karena $k<p\le m$, syarat rekursi untuk $v$ memberi $v(k+1)=F(k,v(k))$. Karena $k<p\le n$, syarat rekursi untuk $w$ memberi $w(k+1)=F(k,w(k))$. Pasangan $(k,v(k))$ dan $(k,w(k))$ sama, dan $F$ adalah fungsi, sehingga nilai $F$ pada keduanya sama. Jadi $v(k+1)=w(k+1)$. $\blacksquare$

Akibat 7.4.6 (keunikan aproksimasi). Jika $G$ dan $H$ keduanya aproksimasi pada $I_n$ yang sama, maka Lema 7.4.5 dengan $m=n$ memberi kesamaan titik demi titik pada $I_n$, sehingga $G=H$. Akibat ini tidak diperlukan dalam bukti di bawah. Yang diperlukan hanya Lema 7.4.5, yaitu kecocokan pada irisan domain. Akibat ini juga belum merupakan keunikan global fungsi $u$; keunikan global dibuktikan terpisah di bagian keunikan Teorema Rekursi.

Pengumpulan, gabungan, dan verifikasi

Lema 7.4.7 (himpunan semua aproksimasi). Himpunan

$$\mathcal{C}=\{G\in\mathcal{P}(\mathbb{N}\times X): \text{ada } n\in\mathbb{N} \text{ sehingga } G \text{ aproksimasi pada } I_n\}$$

ada, dan $U=\bigcup\mathcal{C}$ ada serta $U\subseteq\mathbb{N}\times X$.

Bukti. $\mathbb{N}\times X$ ada (Bab 4) dan $\mathcal{P}(\mathbb{N}\times X)$ ada (aksioma himpunan kuasa). $\mathcal{C}$ diperoleh dengan separasi pada $\mathcal{P}(\mathbb{N}\times X)$ memakai rumus "ada $n\in\mathbb{N}$ sehingga $G$ aproksimasi pada $I_n$", yang berparameter $X,a,F,\mathbb{N}$. Oleh aksioma gabungan, $U=\bigcup\mathcal{C}$ ada. Setiap anggota $U$ adalah anggota suatu $G\in\mathcal{C}$, dan $G\subseteq\mathbb{N}\times X$. Jadi $U\subseteq\mathbb{N}\times X$. $\blacksquare$

Pembentukan $\mathcal{C}$ tidak memerlukan pengetahuan bahwa aproksimasi ada. Seandainya tidak ada, $\mathcal{C}$ hanya akan kosong. Lema 7.4.4 dipakai sesudahnya untuk menunjukkan bahwa $\mathcal{C}$ cukup kaya.

Lema 7.4.8 ($U$ grafik fungsi $\mathbb{N}\to X$). $U$ total dan bernilai tunggal sebagai himpunan bagian $\mathbb{N}\times X$.

Bukti.

Total. Ambil $n\in\mathbb{N}$. Oleh Lema 7.4.4 ada aproksimasi $G$ pada $I_n$, dan $G\in\mathcal{P}(\mathbb{N}\times X)$, sehingga $G\in\mathcal{C}$. Karena $n\in I_n$, ada $x\in X$ dengan $(n,x)\in G\subseteq U$.

Bernilai tunggal. Misalkan $(n,x)\in U$ dan $(n,y)\in U$. Menurut definisi gabungan, ada $G\in\mathcal{C}$ dengan $(n,x)\in G$ dan ada $H\in\mathcal{C}$ dengan $(n,y)\in H$. Menurut definisi $\mathcal{C}$, ada $m$ sehingga $G$ aproksimasi pada $I_m$ (dengan fungsi $v$), dan ada $q$ sehingga $H$ aproksimasi pada $I_q$ (dengan fungsi $w$). Dari $G\subseteq I_m\times X$ diperoleh $n\le m$, dan dari $H\subseteq I_q\times X$ diperoleh $n\le q$. Jadi $n\le\min(m,q)$ (A4), dan Lema 7.4.5 memberi $v(n)=w(n)$. Karena $G$ dan $H$ bernilai tunggal, $x=v(n)$ dan $y=w(n)$. Jadi $x=y$. $\blacksquare$

Sebut $u:\mathbb{N}\to X$ fungsi yang grafiknya $U$.

Dalam bukti Lema 7.4.8 kita "mengambil" $G$, $H$, $m$, $q$. Ini eliminasi kuantor eksistensial yang biasa (Bab 6): dari satu pernyataan "ada", kita menamai satu saksi untuk satu argumen. Persoalan fungsi pilihan dapat muncul ketika banyak saksi hendak dirangkai serentak tanpa aturan yang sudah dibenarkan. Di sini kita hanya mengeliminasi beberapa kuantor eksistensial dalam argumen lokal; tidak ada fungsi pilihan yang diminta.

Fakta penghubung. Jika $G\in\mathcal{C}$ adalah aproksimasi pada $I_m$ dengan fungsi $v$, maka $v(k)=u(k)$ untuk setiap $k\in I_m$. Alasannya: $(k,v(k))\in G\subseteq U$, dan $U$ bernilai tunggal.

Lema 7.4.9 ($u$ memenuhi basis dan rekursi). $u(0)=a$ dan $u(n+1)=F(n,u(n))$ untuk setiap $n\in\mathbb{N}$.

Bukti.

Basis. $G_0=\{(0,a)\}$ adalah aproksimasi pada $I_0$ (basis Lema 7.4.4), jadi $G_0\in\mathcal{C}$ dan $(0,a)\in U$. Maka $u(0)=a$.

Rekursi. Ambil $n\in\mathbb{N}$. Oleh Lema 7.4.4 ada aproksimasi $H$ pada $I_{n+1}$ dengan fungsi $w$, dan $H\in\mathcal{C}$. Karena $n,n+1\in I_{n+1}$, fakta penghubung memberi $u(n)=w(n)$ dan $u(n+1)=w(n+1)$. Karena $n<n+1$, syarat rekursi untuk $w$ memberi $w(n+1)=F(n,w(n))$. Maka

$$u(n+1)=w(n+1)=F(n,w(n))=F(n,u(n)).\qquad\blacksquare$$

Lema 7.4.7, Lema 7.4.8, dan Lema 7.4.9 bersama-sama membuktikan bagian eksistensi Teorema Rekursi.

Keunikan

Bukti bagian keunikan. Misalkan $u,u':\mathbb{N}\to X$ keduanya memenuhi $u(0)=a=u'(0)$ dan $u(n+1)=F(n,u(n))$, $u'(n+1)=F(n,u'(n))$ untuk semua $n$. Kita buktikan $R(n): u(n)=u'(n)$ dengan induksi lemah.

• Basis: $u(0)=a=u'(0)$.
• Langkah: jika $u(k)=u'(k)$, maka $(k,u(k))=(k,u'(k))$, sehingga

$$u(k+1)=F(k,u(k))=F(k,u'(k))=u'(k+1),$$

karena $F$ fungsi.

Jadi $u(n)=u'(n)$ untuk semua $n\in\mathbb{N}$. Keduanya bertipe $\mathbb{N}\to X$, sehingga kesamaan titik demi titik (Bab 5) memberi $u=u'$. Setara dengan itu, grafiknya sama oleh ekstensionalitas. $\blacksquare$

Teorema Rekursi terbukti lengkap.

Kesalahan umum.

• "Definisikan $u$ dengan induksi." Induksi membuktikan $P(n)$ untuk semua $n$, dengan $P$ predikat tentang objek yang sudah ada. Pada bukti di atas, induksi dipakai hanya untuk tiga hal: eksistensi aproksimasi (Lema 7.4.4), kompatibilitas (Lema 7.4.5), dan keunikan. Fungsi $u$ sendiri lahir dari separasi dan gabungan.
• Menggabungkan tanpa kompatibilitas. Tanpa Lema 7.4.5, $U$ bisa memuat $(n,x)$ dan $(n,y)$ dengan $x\ne y$, sehingga $U$ bukan grafik fungsi.
• "Untuk tiap $n$ pilih $v_n$, lalu $u(n)=v_n(n)$." Kalimat itu belum menunjukkan himpunan yang dibentuk. Dalam situasi ini separasi pada $\mathcal{P}(\mathbb{N}\times X)$ cukup untuk mengumpulkan seluruh grafik; tidak diperlukan Aksioma Pilihan atau Penggantian. Rute $\mathcal{C}$ membuat alasan itu terlihat.
• Lupa syarat tipe $F$. Bila $F(n,x)$ dapat keluar dari $X$, langkah Lema 7.4.4 gagal tepat di kalimat "$b\in X$". Lihat bagian kasus batas.

Kasus batas: aturan yang keluar domain

Totalitas dan kodomain $F$ memastikan nilai baru $b=F(n,v(n))$ ada dan berada di $X$ pada langkah Lema 7.4.4. Ketunggalan nilai $F$ juga dipakai pada Lema 7.4.5 dan bukti keunikan global. Tiga contoh berikut menunjukkan apa yang terjadi bila syarat ini dilanggar.

(a) Aturan keluar dari himpunan. Ambil $X=\mathbb{N}$, $u(0)=0$, dan $u(n+1)=u(n)-1$. Rumus $F(n,x)=x-1$ bukan fungsi $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$, karena $0-1\notin\mathbb{N}$. Akibatnya bukan sekadar teorema tidak berlaku; memang tidak ada $u:\mathbb{N}\to\mathbb{N}$ yang memenuhi resep. Seandainya ada, $u(1)=u(0)-1=-1\in\mathbb{N}$, mustahil. Dengan $X=\mathbb{Z}$ aturan yang sama bertipe benar dan menghasilkan $u(n)=-n$: basisnya $u(0)=0=-0$, sedangkan langkah dari $u(k)=-k$ memberi $u(k+1)=-k-1=-(k+1)$.

(b) Aturan tidak terdefinisi di sebagian $X$. Pada $X=\mathbb{Q}$, rumus $x\mapsto 1/x$ tidak terdefinisi di $0$. Dengan $u(0)=0$, resep $u(n+1)=1/u(n)$ macet di $n=0$. Perbaikannya adalah memilih domain yang tertutup: $X=\mathbb{Q}\setminus\{0\}$, $g(x)=1/x$, dan $a\in X$ (Latihan 7.4.16). Pelanggaran tipe pada domain yang terlalu besar tidak selalu berarti tidak ada solusi: untuk nilai awal $2$, resep yang sama berjalan dalam $\mathbb{Q}\setminus\{0\}$. Yang gagal adalah penerapan langsung teorema pada $X=\mathbb{Q}$ sebelum domain diperbaiki.

(c) Pemanggilan keluar dari $\mathbb{N}$. Prosedur dengan aturan "jika $n=0$ kembalikan $0$, selain itu panggil diri pada $n-2$" memanggil argumen $-1$ ketika $n=1$. Ini di luar domain $\mathbb{N}$, dan model eksekusi Count di unit ini tidak memberinya makna (Latihan 7.4.21).

Contoh terhitung: $a_0=0$, $a_{n+1}=2a_n+3^n$

Definisi melalui teorema. Ambil $X=\mathbb{Z}$, $a=0$, dan

$$F(n,x)=2x+3^n.$$

Di sini $3^n$ adalah barisan pangkat yang didefinisikan oleh (Pw) dengan $c=3$, sehingga $3^n\in\mathbb{Z}$. Oleh (A5), $2x+3^n\in\mathbb{Z}$ untuk setiap $n\in\mathbb{N}$ dan $x\in\mathbb{Z}$. Grafik $F$ diperoleh dengan separasi pada $(\mathbb{N}\times\mathbb{Z})\times\mathbb{Z}$ dan total serta bernilai tunggal. Jadi $F:\mathbb{N}\times\mathbb{Z}\to\mathbb{Z}$, dan Teorema Rekursi memberi tepat satu barisan $(a_n)$ dengan $a_0=0$ dan $a_{n+1}=2a_n+3^n$.

Nilai awal, dihitung langsung dari resep:

Tabel ini adalah perhitungan, bukan bukti rumus umum. Lima nilai yang cocok tidak menjamin nilai keenam cocok.

Menemukan rumus (heuristik, bukan bagian bukti). Coba barisan $3^n$: $2\cdot 3^n+3^n=3\cdot 3^n=3^{n+1}$, jadi $3^n$ memenuhi aturan rekursi, tetapi dengan nilai awal $1$, bukan $0$. Selisih $d_n=a_n-3^n$ tampaknya memenuhi $d_{n+1}=2d_n$ dengan $d_0=-1$, sehingga diduga $d_n=-2^n$. Dugaan yang dihasilkan: $a_n=3^n-2^n$.

Proposisi 7.4.10. Untuk setiap $n\in\mathbb{N}$, $a_n=3^n-2^n$.

Bukti. Induksi lemah pada $n$.

Basis $n=0$. $a_0=0$ dan $3^0-2^0=1-1=0$ oleh (Pw).

Langkah. Misalkan $a_k=3^k-2^k$ (hipotesis induksi untuk $k$ yang tetap). Maka

$$\begin{aligned} a_{k+1} &= 2a_k+3^k &&\text{(resep)}\\ &= 2(3^k-2^k)+3^k &&\text{(hipotesis induksi)}\\ &= (2\cdot 3^k+3^k)-2\cdot 2^k &&\text{(distributif, komutatif, asosiatif; A5)}\\ &= 3\cdot 3^k-2\cdot 2^k &&\text{(distributif: } (2+1)3^k\text{)}\\ &= 3^{k+1}-2^{k+1} &&\text{(Pw untuk } c=3 \text{ dan } c=2\text{)}. \end{aligned}$$

$\blacksquare$

Pemeriksaan silang. $3-2=1$, $9-4=5$, $27-8=19$, $81-16=65$, sesuai tabel.

Cara kedua melalui keunikan. Grafik $\{(n,y)\in\mathbb{N}\times\mathbb{Z}:y=3^n-2^n\}$ ada oleh separasi dan menentukan barisan $b_n=3^n-2^n$ bertipe $\mathbb{N}\to\mathbb{Z}$, dan perhitungan langkah di atas, yang tidak memakai hipotesis induksi, menunjukkan $b_{n+1}=2b_n+3^n$ untuk setiap $n$, serta $b_0=0$. Jadi $b$ memenuhi resep yang sama dengan $a$, dan bagian keunikan teorema memberi $a=b$. Kedua cara sah. Cara kedua memperlihatkan bahwa memeriksa sebuah calon solusi terhadap resep ditambah keunikan sudah merupakan bukti.

Batas analisis. Analisis barisan pada unit ini dibatasi pada eksistensi, keunikan, rumus eksplisit, invarian, dan terminasi. Perilaku "$a_n$ untuk $n$ besar", kekonvergenan, dan limit belum dibahas. Pengertian itu memerlukan struktur bilangan real yang dibahas pada bab lanjut.

Analisis algoritme rekursif linear: Count

Pernyataan tentang "berhenti", "banyak pemanggilan", dan "biaya" hanya bermakna relatif terhadap model eksekusi yang dinyatakan. Kita tetapkan model berikut.

• (M1) Pemanggilan Count(n) hanya sah bila $n\in\mathbb{N}$.
• (M2) Jika $n=0$, pemanggilan selesai dan mengembalikan $0$ tanpa memicu pemanggilan lain.
• (M3) Jika $n>0$, 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)<s(i)$ untuk setiap $i$.

Bukti. Andaikan ada. Himpunan $R=\{y\in\mathbb{N}:\text{ada } i\in\mathbb{N},\ s(i)=y\}$ ada oleh separasi dan tak kosong, karena $s(0)\in R$. Oleh urutan baik (7.3), $R$ mempunyai unsur terkecil $m$, dan ada $j$ dengan $s(j)=m$. Tetapi $s(j+1)\in R$ dan $s(j+1)<m$, bertentangan dengan minimalitas $m$. $\blacksquare$

Untuk menerapkan lema ini secara tepat, definisikan fungsi total $p:\mathbb{N}\to\mathbb{N}$ dengan $p(0)=0$ dan $p(x)=x-1$ bila $x>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<s(i)$ untuk semua $i$, bertentangan dengan lema. Jadi ada indeks yang nilainya $0$; sebelum indeks pertama itu, nilai-nilai $s$ persis argumen subpemanggilan Count menurut (M3). Lema menjamin rantai turun mencapai basis. Bahwa seluruh pemanggilan yang tertunda kemudian selesai, beserta nilai, banyak pemanggilan, dan biayanya, telah dibuktikan oleh induksi dalam proposisi di atas. Untuk lompatan yang lebih besar, induksi kuat dapat dipakai setelah ukuran argumen terbukti turun dan tetap berada di $\mathbb{N}$ (Latihan 7.4.20).

Catatan pembeda. Teorema Rekursi menjamin adanya fungsi $f$ dengan $f(0)=0$ dan $f(n+1)=f(n)+1$, yaitu fungsi yang "dihitung" Count. Terminasi adalah klaim tentang prosedur dalam model eksekusi. Pada Count keduanya selaras, tetapi pembuktiannya terpisah. Teorema Rekursi tidak dengan sendirinya membuktikan bahwa setiap program rekursif berhenti.

Latihan

Latihan 7.4.14 (jumlah 7.1 sebagai instans teorema). Tuliskan $X$, $a$, dan $F$ sehingga Teorema Rekursi menghasilkan $S(n)=\sum_{i=1}^{n} i$. Periksa tipe $F$, lalu hitung $S(4)$ langsung dari resep.

Strategi. Cocokkan dengan bentuk $u(n+1)=F(n,u(n))$; indeks $n$ boleh muncul di $F$.

Solusi. $X=\mathbb{N}$, $a=0$, $F(n,x)=x+(n+1)$. Untuk $n,x\in\mathbb{N}$, $x+(n+1)\in\mathbb{N}$, jadi $F:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$. Grafiknya diperoleh dengan separasi pada $(\mathbb{N}\times\mathbb{N})\times\mathbb{N}$. Teorema memberi tepat satu $S$ dengan $S(0)=0$ dan $S(n+1)=S(n)+(n+1)$. Perhitungan: $S(1)=0+1=1$, $S(2)=1+2=3$, $S(3)=3+3=6$, $S(4)=6+4=10$. Ini sesuai dengan $4\cdot5/2=10$ pada 7.1.

Latihan 7.4.15 (domain tertutup). Tunjukkan bahwa tidak ada $u:\mathbb{N}\to\mathbb{N}$ dengan $u(0)=5$ dan $u(n+1)=u(n)-1$. Kemudian tunjukkan bahwa pada $X=\mathbb{Z}$ ada tepat satu solusi, dan buktikan $u(n)=5-n$.

Strategi. Iterasi resep sampai keluar dari $\mathbb{N}$. Untuk bagian kedua, terapkan teorema lalu induksi.

Solusi. Andaikan $u$ seperti itu ada. Maka berturut-turut $u(1)=4$, $u(2)=3$, $u(3)=2$, $u(4)=1$, $u(5)=0$, dan $u(6)=-1$. Padahal $u(6)\in\mathbb{N}$ sedangkan $-1\notin\mathbb{N}$, kontradiksi. (Sebabnya: $x\mapsto x-1$ tidak bertipe $\mathbb{N}\to\mathbb{N}$.)

Pada $X=\mathbb{Z}$, $g(x)=x-1$ bertipe $\mathbb{Z}\to\mathbb{Z}$ dan $5\in\mathbb{Z}$, jadi ada tepat satu $u$. Induksi untuk $u(n)=5-n$: basis $u(0)=5=5-0$; langkah $u(k+1)=(5-k)-1=5-(k+1)$.

Latihan 7.4.16 (aturan tidak terdefinisi di sebagian domain). Misalkan $a\in\mathbb{Q}$ dan $a\ne 0$. Tunjukkan bahwa ada tepat satu $u:\mathbb{N}\to\mathbb{Q}\setminus\{0\}$ dengan $u(0)=a$ dan $u(n+1)=1/u(n)$, lalu buktikan $u(2n)=a$ dan $u(2n+1)=1/a$ untuk semua $n$. Jelaskan apa yang gagal bila $a=0$.

Strategi. Pilih $X$ yang tertutup terhadap $x\mapsto 1/x$. Buktikan pernyataan berpasangan dengan induksi pada $n$.

Solusi. Untuk $x\in\mathbb{Q}$ dengan $x\ne0$, $1/x\in\mathbb{Q}$ dan $1/x\ne 0$ (aritmetika $\mathbb{Q}$ dipinjam). Jadi $g:X\to X$ dengan $X=\mathbb{Q}\setminus\{0\}$, dan $a\in X$. Teorema memberi tepat satu $u$.

Induksi untuk $P(n)$: "$u(2n)=a$ dan $u(2n+1)=1/a$".

• Basis: $u(0)=a$ dan $u(1)=1/a$.
• Langkah: dari $P(k)$, $u(2k+2)=1/u(2k+1)=1/(1/a)=a$, dan $u(2k+3)=1/u(2k+2)=1/a$. Ini $P(k+1)$, karena $2(k+1)=2k+2$ dan $2(k+1)+1=2k+3$.

Bila $a=0$, $a\notin X$, dan pada $\mathbb{Q}$ resep tidak dapat menghitung $u(1)=1/0$. Tidak ada fungsi $u:\mathbb{N}\to\mathbb{Q}$ yang memenuhinya.

Latihan 7.4.17 (keunikan sebagai alat). Misalkan $u:\mathbb{N}\to\mathbb{Z}$ memenuhi $u(0)=1$ dan $u(n+1)=2u(n)-1$. Buktikan $u(n)=1$ untuk semua $n$ tanpa induksi baru, hanya dengan memakai bagian keunikan teorema.

Strategi. Tebak solusi, periksa bahwa tebakan memenuhi resep, lalu bandingkan dua solusi.

Solusi. Fungsi konstan $v(n)=1$ memenuhi $v(0)=1$ dan $v(n+1)=1=2\cdot1-1=2v(n)-1$. Dengan $X=\mathbb{Z}$, $a=1$, $g(x)=2x-1$ bertipe benar, $u$ dan $v$ keduanya solusi, sehingga bagian keunikan memberi $u=v$. Induksi tetap ada, tetapi sudah terbungkus dalam bukti keunikan pada bagian keunikan Teorema Rekursi.

Latihan 7.4.18 (nilai awal umum). Untuk $c\in\mathbb{Z}$, misalkan $b_0=c$ dan $b_{n+1}=2b_n+3^n$. Buktikan $b_n=3^n+(c-1)2^n$. Periksa kasus $c=0$ dan $c=1$.

Strategi. Ulangi pola Proposisi 7.4.10 dengan konstanta $c-1$ yang ikut terbawa.

Solusi. Basis: $3^0+(c-1)2^0=1+c-1=c$. Langkah: jika $b_k=3^k+(c-1)2^k$, maka

$$b_{k+1}=2\cdot3^k+2(c-1)2^k+3^k=3\cdot3^k+(c-1)(2\cdot2^k)=3^{k+1}+(c-1)2^{k+1},$$

dengan (A5) dan (Pw). Untuk $c=0$ diperoleh $3^n-2^n$, sesuai Proposisi 7.4.10. Untuk $c=1$ diperoleh $b_n=3^n$, sesuai heuristik bahwa $3^n$ memenuhi aturan dengan nilai awal $1$.

Latihan 7.4.19 (invarian paritas). Untuk barisan $a_n$ dari Proposisi 7.4.10, buktikan bahwa $a_n$ ganjil untuk setiap $n\ge1$. Mengapa klaim itu tidak dimulai dari $n=0$?

Strategi. Buktikan dulu bahwa $3^n$ ganjil untuk semua $n$, lalu baca resep.

Solusi. Pertama, $3^n$ ganjil untuk semua $n$. Basis: $3^0=1$ ganjil. Langkah: $3^{k+1}=3\cdot 3^k$, hasil kali dua bilangan ganjil, jadi ganjil (A5).

Kedua, untuk setiap $n\ge0$, $a_{n+1}=2a_n+3^n$ adalah genap ditambah ganjil, jadi ganjil. Untuk $m\ge1$, tulis $m=(m-1)+1$ (A3). Maka $a_m$ ganjil.

Klaim tidak dimulai dari $0$ karena $a_0=0$ genap. Basis yang benar untuk klaim ini adalah $1$. Pada argumen ini kebetulan tidak diperlukan hipotesis induksi tentang $a$ sendiri.

Latihan 7.4.20 (terminasi dengan ukuran menurun). Dalam model analog dengan (M1)-(M3), prosedur Half(n) mengembalikan $0$ bila $n=0$, dan selain itu memanggil Half(q) dengan $n=2q+r$, $r\in\{0,1\}$ (pembagian Euclid 7.3). Buktikan bahwa Half(n) berhenti untuk setiap $n\in\mathbb{N}$.

Strategi. Argumen tidak turun tepat satu, jadi pakai induksi kuat dengan ukuran $n$ sendiri. Buktikan $q<n$ untuk $n\ge1$.

Solusi. Untuk $n\ge 1$: $q\in\mathbb{N}$ (karena $2q=n-r\ge0$) dan $q<n$. Andaikan $q\ge n$; maka $n=2q+r\ge 2n\ge n+1$, kontradiksi.

Induksi kuat (7.2) dengan $P(n)$: "Half(n) berhenti".

• $n=0$ berhenti langsung.
• Untuk $n\ge1$, anggap $P(j)$ untuk semua $j<n$. Karena $q<n$, Half(q) berhenti, sehingga Half(n) berhenti.

Hipotesis hanya dipakai pada indeks $q$ yang sah: $0\le q<n$.

Latihan 7.4.21 (pemanggilan keluar domain). Prosedur Skip(n): jika $n=0$ kembalikan $0$, selain itu kembalikan Skip(n-2)+1. (a) Tunjukkan bahwa Skip(1) tidak bermakna dalam model analog dengan (M1)-(M3) untuk Skip. (b) Perbaiki dengan basis tambahan Skip(1)$\,=1$, lalu buktikan bahwa Skip(n) berhenti untuk setiap $n$.

Strategi. Periksa argumen subpemanggilan terhadap $\mathbb{N}$. Lompatan dua langkah membutuhkan dua basis (bandingkan dengan lompatan 6 pada 7.2).

Solusi. (a) Skip(1) memicu Skip(-1), dan $-1\notin\mathbb{N}$. Pemanggilan ini tidak sah menurut (M1), jadi model tidak memberi Skip(1) hasil apa pun.

(b) Dengan basis $n=0$ dan $n=1$ yang berhenti langsung: untuk $n\ge2$ berlaku $n-2\in\mathbb{N}$ dan $n-2<n$. Induksi kuat dengan $P(n)$: "Skip(n) berhenti" memberi hasilnya. Kasus $n=0,1$ berhenti langsung. Untuk $n\ge2$, $P(n-2)$ termasuk dalam hipotesis. Kedua basis diperlukan karena langkah $n\mapsto n-2$ dari $n=1$ keluar domain, sehingga $1$ tidak dapat ditangani oleh langkah.

Latihan 7.4.22 (rekursi dua suku melalui pasangan). Buktikan bahwa ada tepat satu $f:\mathbb{N}\to\mathbb{N}$ dengan $f(0)=0$, $f(1)=1$, dan $f(n+2)=f(n+1)+f(n)$.

Strategi. Teorema hanya mengizinkan ketergantungan pada satu nilai sebelumnya. Kemas dua nilai berurutan menjadi satu anggota $X=\mathbb{N}\times\mathbb{N}$.

Solusi.

Eksistensi. Ambil $X=\mathbb{N}\times\mathbb{N}$, $a=(0,1)$, dan $g(x,y)=(y,x+y)$, yang bertipe $X\to X$. Teorema memberi $w:\mathbb{N}\to X$ dengan $w(0)=(0,1)$ dan $w(n+1)=g(w(n))$. Definisikan $f(n)$ sebagai komponen pertama $w(n)$; grafiknya diperoleh dengan separasi.

Klaim $Q(n)$: $w(n)=(f(n),f(n+1))$. Buktikan dengan induksi.

• Basis: komponen pertama $w(0)$ adalah $0=f(0)$. Komponen pertama $w(1)=g(0,1)=(1,1)$ adalah $1$, jadi $f(1)=1$, dan komponen kedua $w(0)$ adalah $1=f(1)$.
• Langkah: jika $w(k)=(f(k),f(k+1))$, maka $w(k+1)=(f(k+1),f(k)+f(k+1))$. Komponen pertamanya sama dengan $f(k+1)$ menurut definisi $f$. Komponen pertama $w(k+2)=g(w(k+1))$ adalah komponen kedua $w(k+1)$, yaitu $f(k)+f(k+1)$. Jadi $f(k+2)=f(k)+f(k+1)$, dan $w(k+1)=(f(k+1),f(k+2))$.

Dari basis telah diperoleh $f(0)=0$ dan $f(1)=1$. Untuk setiap $n$, $Q(n)$ memberi $w(n+1)=(f(n+1),f(n)+f(n+1))$, sedangkan $Q(n+1)$ memberi $w(n+1)=(f(n+1),f(n+2))$. Kesamaan pasangan terurut dan komutativitas memberi $f(n+2)=f(n+1)+f(n)$.

Keunikan. Jika $f,h$ keduanya solusi, buktikan dengan induksi bahwa "$f(n)=h(n)$ dan $f(n+1)=h(n+1)$".

• Basis dari $f(0)=h(0)=0$ dan $f(1)=h(1)=1$.
• Langkah: konjungsi pertama pada indeks $k+1$, yaitu $f(k+1)=h(k+1)$, sudah termasuk hipotesis. Konjungsi kedua mengikuti dari $f(k+2)=f(k+1)+f(k)=h(k+1)+h(k)=h(k+2)$.

Kesamaan titik demi titik memberi $f=h$.

Latihan 7.4.23 (diagnosis bukti cacat). Kritik "bukti" berikut: "Untuk setiap $n$, Lema 7.4.4 memberi aproksimasi $v_n$ pada $I_n$. Definisikan $u(n)=v_n(n)$. Maka $u$ fungsi pada $\mathbb{N}$." Tunjukkan dua celahnya dan bagaimana bagian pengumpulan dan gabungan menutupnya.

Strategi. Tanyakan: objek apa yang sebenarnya dibentuk, dengan aksioma apa, dan mengapa nilainya tak bergantung pada pilihan.

Solusi.

1. Rumusan "untuk setiap $n$ beri $v_n$" belum menunjukkan satu himpunan atau fungsi penugasan yang dibentuk. Dalam situasi ini semua grafik aproksimasi berada di $\mathcal{P}(\mathbb{N}\times X)$, sehingga separasi langsung membentuk $\mathcal{C}$. Sesudah keunikan aproksimasi diketahui, grafik penugasan $n\mapsto G_n$ pun dapat dibentuk dengan separasi di $\mathbb{N}\times\mathcal{P}(\mathbb{N}\times X)$. Jadi celahnya adalah langkah pembentukan himpunan yang belum ditulis, bukan kebutuhan Aksioma Pilihan atau Penggantian.
2. Tanpa kompatibilitas, tidak ada jaminan bahwa $u$ memenuhi rekursi: $u(n+1)=v_{n+1}(n+1)$ dihitung dari $v_{n+1}(n)$, bukan dari $v_n(n)=u(n)$.

bagian pengumpulan dan gabungan menutup celah pertama dengan separasi (membentuk $\mathcal{C}$ yang memuat semua aproksimasi) dan gabungan. Celah kedua ditutup oleh Lema 7.4.5, yang memastikan $v_{n+1}(n)=v_n(n)$ sebagai kasus khusus dan sekaligus menjadikan $U$ bernilai tunggal.

Penutup Bagian I: menuju Bab 8

Bab 3 sampai Bab 7 menyusun bahasa kerja buku ini:

• Bab 3: himpunan dan aksioma pembentuknya.
• Bab 4: pasangan terurut, produk, dan relasi.
• Bab 5: fungsi bertipe beserta kesamaan titik demi titiknya.
• Bab 6: metode pembuktian.
• Bab 7: induksi lemah sebagai prinsip yang diasumsikan, induksi kuat dan urutan baik sebagai turunannya, dan akhirnya Teorema Rekursi yang mengubah resep rekursif menjadi fungsi yang ada dan tunggal.

Status pinjaman kini lebih jelas. Induksi lemah tetap diasumsikan; induksi kuat dan urutan baik telah diturunkan darinya. Jumlah berhingga pada 7.1 dan pangkat pada latihan 7.3 kini mempunyai dasar eksistensi dan ketunggalan melalui Teorema Rekursi.

Satu pinjaman besar sengaja dibiarkan terbuka, yaitu $\mathbb{N}$ itu sendiri. Seluruh Bab 7 mengandaikan himpunan $\mathbb{N}$ dengan $0$, operasi penerus, penjumlahan, perkalian, urutan, dan fakta (A1)-(A5). Bab 8 membahas struktur Peano dan konstruksi perluasan ke bilangan bulat serta rasional; keberadaan struktur Peano tetap diasumsikan.

Ada satu kehati-hatian untuk perjalanan itu. Bukti Teorema Rekursi di atas memakai fakta urutan (A1)-(A4), misalnya $I_{n+1}=I_n\cup\{n+1\}$. Bila kelak Teorema Rekursi dipakai untuk mendefinisikan operasi aritmetika pada $\mathbb{N}$ yang dikonstruksi, fakta-fakta urutan yang dipakai dalam buktinya harus lebih dulu diturunkan tanpa operasi yang hendak didefinisikan. Jika tidak, lingkaran asumsi yang kita hindari sepanjang Bab 7 akan masuk kembali melalui pintu belakang.

Rujukan Bab 7

[R7-1] James Aspnes. Induction Proofs, bagian 1–2, catatan Yale. Bacaan pembanding pola induksi. https://www.cs.yale.edu/homes/aspnes/pinewiki/InductionProofs.html

[R7-2] Gary Hardegree. Set Theory, Chapter4, The Natural Numbers, bagian7, halaman tercetak16, pembahasan rekursi. https://people.umass.edu/gmhwww/595t/pdf/Set-Theory-Chap4.pdf#page=16