Bab 20: Himpunan Hingga dan Prinsip Sarang Merpati

20.1 Definisi Formal Himpunan Hingga

Sepanjang Bab 11–19, kata "berhingga" dipakai dalam arti kerja: anggota himpunan dapat didaftar habis $a_1,\ldots,a_n$. Pemakaian itu selalu diberi label pinjaman maju dengan rencana penutupan di Bab 20.1. Unit ini menunaikan janji itu. Kita mendefinisikan himpunan hingga melalui bijeksi dengan himpunan standar $\{1,\ldots,n\}$, membuktikan bahwa bilangan $n$ itu tunggal, sehingga kardinalitas $|A|$ terdefinisi, lalu membuktikan sifat-sifat dasar yang dipakai pada bab-bab sebelumnya. Hasil kuncinya adalah lemma bahwa injeksi dari $\{1,\ldots,m\}$ ke $\{1,\ldots,n\}$ memaksa $m\leq n$. Lemma itu sekaligus inti Prinsip Sarang Merpati (Unit 20.2).

Prasyarat:

• himpunan, separasi, operasi himpunan (Bab 3);
• fungsi, injeksi, surjeksi, bijeksi, komposisi, invers, peta maju (Bab 5);
• induksi dan urutan baik (Bab 7);
• bilangan asli dengan $\mathbb{N}=\{0,1,2,\ldots\}$ (Bab 8).

Himpunan Standar dan Definisi

Definisi 20.1.1 (Himpunan Standar)

Untuk $n\in\mathbb{N}$, tetapkan

Jadi $[0]=\emptyset$, $[1]=\{1\}$, dan $[n+1]=[n]\cup\{n+1\}$ dengan $n+1\notin[n]$.

Definisi 20.1.2 (Himpunan Hingga dan Tak Hingga)

Himpunan $A$ disebut hingga (berhingga) jika terdapat $n\in\mathbb{N}$ dan bijeksi $f:[n]\to A$. Himpunan yang tidak hingga disebut tak hingga.

Untuk $n=0$, satu-satunya fungsi $[0]=\emptyset\to A$ adalah fungsi kosong. Fungsi kosong itu bijeksi tepat ketika $A=\emptyset$, karena surjektivitas mensyaratkan setiap anggota $A$ menjadi peta, dan tidak ada peta. Jadi $\emptyset$ hingga. Sebuah bijeksi $f:[n]\to A$ adalah cara formal menuliskan daftar $a_k=f(k)$ tanpa pengulangan (injektif) dan tanpa yang terlewat (surjektif).

Lemma Inti

Lemma 20.1.3 (Membuang Satu Titik)

Misalkan $m,n\in\mathbb{N}$ dan $f:[m+1]\to[n+1]$ injektif. Maka terdapat injeksi $g:[m]\to[n]$.

Bukti. Tulis $j=f(m+1)\in[n+1]$. Definisikan $g$ pada $[m]$ dengan

Nilai $g$ berada di $[n]$. Pada kasus pertama, $f(k)\in[n+1]\setminus\{n+1\}=[n]$. Pada kasus kedua, $f(k)=n+1$ dengan $k\ne m+1$, sehingga injektivitas $f$ memberi $j=f(m+1)\ne f(k)=n+1$, dan $j\in[n]$.

$g$ injektif. Misalkan $k\ne k'$ di $[m]$.

• Jika keduanya kasus pertama, $g(k)=f(k)\ne f(k')=g(k')$.
• Keduanya tidak mungkin kasus kedua sekaligus, karena $f(k)=f(k')=n+1$ bertentangan dengan injektivitas.
• Jika $k$ kasus pertama dan $k'$ kasus kedua, maka $g(k)=f(k)$ dan $g(k')=j=f(m+1)$. Karena $k\ne m+1$, injektivitas $f$ memberi $f(k)\ne f(m+1)$.

$\square$

Teorema 20.1.4 (Injeksi Antarhimpunan Standar)

Misalkan $m,n\in\mathbb{N}$. Jika terdapat injeksi $[m]\to[n]$, maka $m\leq n$.

Bukti. Induksi pada $m$, untuk pernyataan "untuk setiap $n\in\mathbb{N}$, jika ada injeksi $[m]\to[n]$, maka $m\leq n$".

Basis $m=0$: $0\leq n$ untuk setiap $n$.

Langkah: misalkan pernyataan benar untuk $m$, dan $f:[m+1]\to[n]$ injektif. Karena $m+1\in[m+1]$, $f(m+1)\in[n]$, sehingga $[n]\ne\emptyset$ dan $n\geq1$. Tulis $n=n'+1$. Lemma 20.1.3 memberi injeksi $[m]\to[n']$, dan hipotesis induksi memberi $m\leq n'$. Jadi $m+1\leq n'+1=n$. $\square$

Akibat 20.1.5 (Ketunggalan Banyak Anggota)

(a) Jika terdapat bijeksi $[m]\to[n]$, maka $m=n$.

(b) Jika $A$ hingga dengan bijeksi $f:[m]\to A$ dan $g:[n]\to A$, maka $m=n$.

Bukti. (a) Bijeksi $h$ dan inversnya $h^{-1}$ (Bab 5) adalah injeksi, sehingga Teorema 20.1.4 memberi $m\leq n$ dan $n\leq m$.

(b) $g^{-1}\circ f:[m]\to[n]$ adalah bijeksi, sebagai komposisi bijeksi; gunakan (a). $\square$

Definisi 20.1.6 (Kardinalitas Himpunan Hingga)

Untuk himpunan hingga $A$, bilangan tunggal $n$ pada Akibat 20.1.5(b) disebut kardinalitas $A$, ditulis $|A|$. Jadi $|[n]|=n$ dan $|\emptyset|=0$.

Notasi $|A|$ untuk kardinalitas tidak boleh dikacaukan dengan nilai mutlak; argumennya berupa himpunan, bukan bilangan. Akibat 20.1.5 adalah teorema yang membuat definisi ini sah. Tanpa teorema itu, satu himpunan mungkin dapat didaftar dengan $3$ unsur dan juga dengan $4$ unsur, dan "banyak anggota" tidak bermakna.

Sifat-Sifat Dasar

Teorema 20.1.7 (Subhimpunan)

Misalkan $A$ hingga dan $B\subseteq A$. Maka $B$ hingga dan $|B|\leq|A|$. Jika $B\ne A$, maka $|B|<|A|$.

Bukti. Cukup membuktikan untuk $A=[n]$. Untuk $A$ umum dengan bijeksi $f:[n]\to A$, terapkan hasilnya pada $f^{-1}[B]\subseteq[n]$; pembatasan $f$ memberi bijeksi $f^{-1}[B]\to B$.

Induksi pada $n$ untuk "setiap $B\subseteq[n]$ hingga dengan $|B|\leq n$". Basis $n=0$: $B=\emptyset$. Langkah: misalkan $B\subseteq[n+1]$.

• Jika $n+1\notin B$, maka $B\subseteq[n]$, sehingga $B$ hingga dengan $|B|\leq n<n+1$.
• Jika $n+1\in B$, maka $B'=B\setminus\{n+1\}\subseteq[n]$ hingga dengan bijeksi $h:[k]\to B'$, $k\leq n$. Perluas $h$ menjadi $h^*:[k+1]\to B$ dengan $h^*(k+1)=n+1$. Fungsi ini bijeksi karena $n+1\notin B'$. Jadi $|B|=k+1\leq n+1$.

Untuk bagian tegas: jika $B\subsetneq[n]$, ada $a\in[n]\setminus B$. Pemetaan $\sigma:[n]\to[n]$ yang menukar $a$ dan $n$ (dan tetap untuk lainnya) adalah bijeksi, dan $\sigma[B]\subseteq[n]\setminus\{n\}=[n-1]$. Jadi $|B|=|\sigma[B]|\leq n-1<n$ menurut bagian pertama. $\square$

Akibat 20.1.8 (Injeksi Diri Himpunan Hingga Surjektif)

Jika $A$ hingga dan $f:A\to A$ injektif, maka $f$ surjektif.

Bukti. $f$ adalah bijeksi $A\to f[A]$, sehingga $|f[A]|=|A|$. Bila $f[A]\subsetneq A$, Teorema 20.1.7 memberi $|f[A]|<|A|$, kontradiksi. $\square$

Akibat ini yang membedakan himpunan hingga dari himpunan tak hingga pada Unit 20.3. Fungsi $n\mapsto n+1$ pada $\mathbb{N}$ injektif tetapi tidak surjektif.

Teorema 20.1.9 (Gabungan)

(a) Jika $A,B$ hingga dan saling lepas, maka $A\cup B$ hingga dan $|A\cup B|=|A|+|B|$.

(b) Jika $A,B$ hingga, maka $A\cup B$ hingga dan $|A\cup B|=|A|+|B|-|A\cap B|\leq|A|+|B|$.

Bukti. (a) Dengan bijeksi $f:[m]\to A$ dan $g:[n]\to B$, definisikan $h:[m+n]\to A\cup B$ oleh $h(k)=f(k)$ untuk $k\leq m$ dan $h(k)=g(k-m)$ untuk $m<k\leq m+n$. Fungsi $h$ surjektif karena setiap anggota $A$ dan $B$ tercapai. $h$ injektif karena pada setiap bagian $f$ atau $g$ injektif, dan nilai dari dua bagian berbeda karena $A\cap B=\emptyset$.

(b) $A\cup B=A\cup(B\setminus A)$ adalah gabungan saling lepas, dan $B=(B\setminus A)\cup(A\cap B)$ juga saling lepas. Semua bagian hingga menurut Teorema 20.1.7. Terapkan (a) dua kali. $\square$

Teorema 20.1.10 (Daftar dengan Pengulangan)

Jika $f:[n]\to A$ surjektif, maka $A$ hingga dan $|A|\leq n$.

Bukti. Induksi pada $n$. Basis $n=0$: surjeksi dari $\emptyset$ memaksa $A=\emptyset$. Langkah: $A=f[[n]]\cup\{f(n+1)\}$. Himpunan $f[[n]]$ adalah peta surjektif dari $[n]$, sehingga hingga dengan $|f[[n]]|\leq n$ (hipotesis induksi). Singleton hingga dengan kardinalitas $1$. Teorema 20.1.9(b) memberi $|A|\leq n+1$. $\square$

Teorema ini adalah jembatan dari arti kerja ke arti formal: daftar $a_1,\ldots,a_n$ yang boleh berulang menghasilkan himpunan hingga dengan paling banyak $n$ anggota. Penghapusan pengulangan, yang dipakai di Lemma 14.3.1 dan di bukti-bukti sebelumnya, kini dijamin oleh teorema ini.

Teorema 20.1.11 (Himpunan Bilangan Asli Tak Hingga)

$\mathbb{N}$ tak hingga.

Bukti. Andaikan $f:[n]\to\mathbb{N}$ bijeksi. Bila $n=0$, $\mathbb{N}=\emptyset$, padahal $0\in\mathbb{N}$. Bila $n\geq1$, himpunan $f[[n]]=\mathbb{N}$ hingga dan tak kosong, terurut total oleh $\leq$, sehingga mempunyai maksimum $M$ (Teorema 11.1.14, yang kini sah secara formal; lihat bagian berikut). Tetapi $M+1\in\mathbb{N}$ dan $M+1>M$, kontradiksi. $\square$

Penutupan Pinjaman "Berhingga"

Dengan Definisi 20.1.2 dan Teorema 20.1.4–20.1.10, pemakaian arti kerja sebelumnya kini mempunyai dasar formal.

• Teorema 11.1.14 (maksimum dan minimum himpunan berhingga tak kosong terurut total): induksi atas $|S|$ kini sah, karena $|S|$ terdefinisi tunggal (Akibat 20.1.5). Langkah "hapus satu unsur" memberi $|S\setminus\{a\}|=|S|-1$ menurut Teorema 20.1.9(a) dengan $S=(S\setminus\{a\})\cup\{a\}$.
• Proposisi 13.2.11(b) dan Teorema 13.4.5: minimum daftar berhingga radius memakai Teorema 11.1.14 pada himpunan nilai daftar, yang hingga menurut Teorema 20.1.10.
• Contoh 14.1.6(d): himpunan berhingga sebagai gabungan berhingga singleton; induksi atas $|E|$.
• Lemma 14.2.6, Akibat 14.2.7, dan Contoh 14.2.8: "berhingga", "tak hingga", dan penghapusan berhingga kini mengikuti Definisi 20.1.2 dan Teorema 20.1.7, 20.1.9, 20.1.10.
• Lemma 14.3.1: Teorema 20.1.9(b).
• Teorema 12.4.12 (lemma pigeonhole di dalam buktinya): kasus khusus Teorema 20.1.4 (lihat Unit 20.2).
• Definisi 4.4.16 (poset berhingga untuk diagram Hasse): kini bermakna formal.

Status: penutupan ini bergantung pada Bab 3, 5, 7, dan 8 yang telah ditelaah, dan pada unit ini, yang ditulis dan diswa-telaah Claude dan masih menunggu persetujuan penulis.

Latihan

Latihan 20.1-1. Tuliskan bijeksi eksplisit $[3]\to\{a,b,c\}$ untuk tiga unsur berbeda, dan tentukan banyaknya bijeksi semacam itu.

Latihan 20.1-2. Buktikan bahwa $\emptyset$ hingga dengan $|\emptyset|=0$, dan bahwa setiap singleton hingga dengan kardinalitas $1$.

Latihan 20.1-3. Buktikan langsung, tanpa Teorema 20.1.4, bahwa tidak ada injeksi $[3]\to[2]$.

Latihan 20.1-4. Buktikan $|A\cup B|=|A|+|B|-|A\cap B|$ untuk himpunan hingga, lalu turunkan rumus untuk tiga himpunan.

Latihan 20.1-5. Buktikan bahwa jika $A$ hingga dan $f:A\to B$ fungsi, maka $f[A]$ hingga dengan $|f[A]|\leq|A|$. Kapan kesamaan berlaku?

Latihan 20.1-6. Buktikan bahwa $A\times B$ hingga dengan $|A\times B|=|A|\,|B|$ untuk himpunan hingga $A,B$.

Latihan 20.1-7. Buktikan bahwa $\mathbb{Z}$ dan setiap himpunan yang memuat $\mathbb{N}$ tak hingga.

Latihan 20.1-8. Buktikan bahwa setiap himpunan hingga tak kosong $S\subseteq\mathbb{R}$ mempunyai maksimum, dengan induksi atas $|S|$ yang memakai teorema-teorema unit ini secara eksplisit.

Solusi

Solusi 20.1-1. $f(1)=a$, $f(2)=b$, $f(3)=c$. Banyaknya bijeksi $3\cdot2\cdot1=6$: pilih peta $1$ dari tiga unsur, peta $2$ dari dua sisa, dan peta $3$ yang tersisa. Hitungan ini memakai Latihan 20.1-6 secara berulang, atau induksi pada banyak unsur. $\square$

Solusi 20.1-2. Fungsi kosong $[0]\to\emptyset$ adalah bijeksi (Definisi 20.1.2), sehingga $|\emptyset|=0$. Untuk $\{x\}$, fungsi $1\mapsto x$ adalah bijeksi $[1]\to\{x\}$. $\square$

Solusi 20.1-3. Misalkan $f:[3]\to[2]$. Ketiga nilai $f(1),f(2),f(3)$ masing-masing $1$ atau $2$. Bila $f(1)\ne f(2)$, maka $\{f(1),f(2)\}=\{1,2\}$, dan $f(3)$ sama dengan salah satunya. Jadi dua dari tiga nilai sama, dan $f$ tidak injektif. $\square$

Solusi 20.1-4. Teorema 20.1.9(b). Untuk tiga himpunan, terapkan dua kali:

Distributivitas memberi $(A\cup B)\cap C=(A\cap C)\cup(B\cap C)$, dengan kardinalitas $|A\cap C|+|B\cap C|-|A\cap B\cap C|$. Hasilnya $|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$. $\square$

Solusi 20.1-5. Dengan bijeksi $g:[n]\to A$, fungsi $f\circ g:[n]\to f[A]$ surjektif, sehingga Teorema 20.1.10 memberi $|f[A]|\leq n$. Kesamaan berlaku jika dan hanya jika $f$ injektif pada $A$.

• Jika injektif, $f:A\to f[A]$ bijeksi.
• Jika $f(x)=f(y)$ dengan $x\ne y$, maka $f[A]=f[A\setminus\{y\}]$, sehingga $|f[A]|\leq|A|-1$.

$\square$

Solusi 20.1-6. Induksi pada $|B|$. $|A\times\emptyset|=0$. Untuk $B=B'\cup\{b\}$ dengan $b\notin B'$: $A\times B=(A\times B')\cup(A\times\{b\})$, saling lepas. $|A\times\{b\}|=|A|$, lewat bijeksi $a\mapsto(a,b)$. Teorema 20.1.9(a) memberi $|A||B'|+|A|=|A|(|B'|+1)$. $\square$

Solusi 20.1-7. Bila $X\supseteq\mathbb{N}$ hingga, Teorema 20.1.7 membuat $\mathbb{N}$ hingga, bertentangan dengan Teorema 20.1.11. $\mathbb{Z}\supseteq\mathbb{N}$. $\square$

Solusi 20.1-8. Induksi pada $n=|S|\geq1$.

• $n=1$: $S=\{s\}$, maksimumnya $s$.
• Langkah: $|S|=n+1$, ambil $a\in S$. Teorema 20.1.9(a) pada $S=(S\setminus\{a\})\cup\{a\}$ memberi $|S\setminus\{a\}|=n\geq1$. Hipotesis induksi memberi $M'=\max(S\setminus\{a\})$. Maka $\max S=\max(M',a)$ menurut trikotomi, seperti pada bukti Teorema 11.1.14.

$\square$

Ringkasan

Himpunan hingga didefinisikan sebagai himpunan yang dalam bijeksi dengan suatu $[n]$. Lemma membuang satu titik memberi teorema inti: injeksi $[m]\to[n]$ memaksa $m\leq n$. Akibatnya, kardinalitas himpunan hingga tunggal. Subhimpunan himpunan hingga hingga, dan subhimpunan sejati lebih kecil. Injeksi diri himpunan hingga surjektif. Gabungan, peta, dan hasil kali himpunan hingga hingga, dengan rumus kardinalitasnya. $\mathbb{N}$ tak hingga. Pinjaman arti kerja "berhingga" sejak Bab 11 ditutup. Unit 20.2 merumuskan Prinsip Sarang Merpati dan penerapannya.

20.2 Prinsip Sarang Merpati (Pigeonhole Principle)

Penjelasan master: jika $n+1$ objek dimasukkan ke dalam $n$ kotak, maka setidaknya ada satu kotak yang memuat lebih dari satu objek. Pernyataan yang tampak remeh ini adalah alat pembuktian keberadaan yang sangat kuat. Ia menjamin bahwa sesuatu ada (dua objek sekotak) tanpa menunjukkan yang mana. Dalam bahasa Unit 20.1, prinsip ini tidak lain adalah Teorema 20.1.4: tidak ada injeksi dari himpunan yang lebih besar ke himpunan yang lebih kecil. Unit ini merumuskan versi dasar dan versi umumnya, lalu menerapkannya pada beberapa soal, termasuk teorema aproksimasi Dirichlet dalam analisis dan model tabrakan pada hashing sesuai implementasi master.

Prasyarat: Unit 20.1; Lema 8.3.3 (pembulatan, dengan Archimedes dari Teorema 11.3.9); jarak bidang (Unit 18.2); pembagian Euclid (Teorema 7.3.8).

Pernyataan

Teorema 20.2.1 (Prinsip Sarang Merpati)

Misalkan $A$ dan $B$ hingga dengan $|A|>|B|$, dan $f:A\to B$ fungsi. Maka $f$ tidak injektif: terdapat $a\ne a'$ di $A$ dengan $f(a)=f(a')$.

Bukti. Misalkan $|A|=m$ dan $|B|=n$, dengan bijeksi $\alpha:[m]\to A$ dan $\beta:[n]\to B$. Jika $f$ injektif, maka $\beta^{-1}\circ f\circ\alpha:[m]\to[n]$ injektif sebagai komposisi injeksi, dan Teorema 20.1.4 memberi $m\leq n$. Ini bertentangan dengan $m>n$. $\square$

Bentuk master adalah kasus $|A|=n+1$ dan $|B|=n$: objek-objek adalah $A$, kotak-kotak adalah $B$, dan $f$ memasukkan setiap objek ke kotaknya.

Teorema 20.2.2 (Sarang Merpati Umum)

Misalkan $A,B$ hingga dengan $B\ne\emptyset$, $f:A\to B$, dan $k\in\mathbb{N}$. Jika $|A|>k|B|$, maka terdapat $b\in B$ dengan $|f^{-1}[\{b\}]|\geq k+1$.

Bukti. Himpunan-himpunan $f^{-1}[\{b\}]$ untuk $b\in B$ saling lepas dan gabungannya $A$. Kita tunjukkan dengan induksi pada $|B|$ bahwa $|A|=\sum_{b\in B}|f^{-1}[\{b\}]|$. Untuk $B=\{b\}$, $f^{-1}[\{b\}]=A$. Untuk $B=B'\cup\{b_0\}$ dengan $b_0\notin B'$, $A$ adalah gabungan saling lepas dari $f^{-1}[B']$ dan $f^{-1}[\{b_0\}]$, lalu gunakan Teorema 20.1.9(a) dan hipotesis induksi pada $f$ yang dibatasi ke $f^{-1}[B']$. (Bila $f^{-1}[B']$ kosong, jumlahnya nol dan klaimnya tetap berlaku.)

Andaikan setiap $|f^{-1}[\{b\}]|\leq k$. Maka $|A|\leq k|B|$, kontradiksi. $\square$

Akibatnya, bila $|A|=q|B|+r$ dengan $1\leq r\leq|B|$, ada kotak yang memuat paling sedikit $q+1$ objek. Dengan pembulatan ke atas, paling sedikit $\bigl\lceil\tfrac{|A|}{|B|}\bigr\rceil$ objek.

Teorema 20.2.1 adalah kasus $k=1$.

Penerapan Elementer

Contoh 20.2.3 (Sisa Pembagian)

Di antara $n+1$ bilangan bulat $a_0,\ldots,a_n$, dengan $n\geq1$, ada dua yang selisihnya habis dibagi $n$.

Bukti. Pembagian Euclid (Teorema 7.3.8) memberi sisa $r_i\in\{0,\ldots,n-1\}$ dengan $a_i=q_in+r_i$. Fungsi $i\mapsto r_i$ memetakan $n+1$ indeks ke $n$ nilai. Teorema 20.2.1 memberi $i\ne j$ dengan $r_i=r_j$, sehingga $a_i-a_j=(q_i-q_j)n$. $\square$

Hal yang sama dipakai pada bukti Teorema 12.4.12 (periodisitas desimal rasional): $q+1$ sisa dari $\{0,\ldots,q-1\}$ memuat pengulangan.

Contoh 20.2.4 (Titik di Persegi)

Di antara lima titik di persegi $[0,1]^2$, ada dua yang jaraknya paling banyak $\tfrac{\sqrt2}2$.

Bukti. Bagi persegi menjadi empat subpersegi $[0,\tfrac12]^2$, $[\tfrac12,1]\times[0,\tfrac12]$, $[0,\tfrac12]\times[\tfrac12,1]$, dan $[\tfrac12,1]^2$. Untuk menjadikan pembagian ini fungsi, tetapkan setiap titik ke subpersegi pertama, dalam urutan di atas, yang memuatnya. Lima titik dan empat subpersegi: dua titik berada di subpersegi yang sama, misalnya $[a,a+\tfrac12]\times[b,b+\tfrac12]$. Selisih koordinatnya masing-masing paling banyak $\tfrac12$ (Lemma 13.1.2), sehingga jaraknya $\sqrt{\Delta_1^2+\Delta_2^2}\leq\sqrt{\tfrac14+\tfrac14}=\tfrac{\sqrt2}2$. Ketaksamaan terakhir memakai monotonisitas akar (Contoh 15.3.5(e)). $\square$

Aproksimasi Dirichlet

Untuk $x\in\mathbb{R}$, tulis $\lfloor x\rfloor$ untuk bilangan bulat $m-1$ dari Lema 8.3.3 ($m-1\leq x<m$), dan $\{x\}=x-\lfloor x\rfloor\in[0,1)$ untuk bagian pecahannya.

Teorema 20.2.5 (Dirichlet)

Untuk setiap $x\in\mathbb{R}$ dan $N\in\mathbb{N}_{+}$, terdapat bilangan bulat $p$ dan $q$ dengan $1\leq q\leq N$ dan

Bukti. Tinjau $N+1$ bilangan $\{kx\}$ untuk $k=0,1,\ldots,N$, semuanya di $[0,1)$. Bagi $[0,1)$ menjadi $N$ kotak $I_j=[\tfrac jN,\tfrac{j+1}N)$, untuk $j=0,\ldots,N-1$. Setiap $t\in[0,1)$ termasuk tepat satu kotak, yaitu $j=\lfloor Nt\rfloor$, karena $0\leq Nt<N$. Jadi pemasukan ke kotak adalah fungsi dari $N+1$ indeks ke $N$ kotak. Teorema 20.2.1 memberi $k_1<k_2$ di $\{0,\ldots,N\}$ dengan $\{k_1x\}$ dan $\{k_2x\}$ dalam kotak yang sama, sehingga $\bigl|\{k_2x\}-\{k_1x\}\bigr|<\tfrac1N$, karena keduanya di selang setengah buka berpanjang $\tfrac1N$. Tetapkan $q=k_2-k_1\in[1,N]$ dan $p=\lfloor k_2x\rfloor-\lfloor k_1x\rfloor\in\mathbb{Z}$. Maka $qx-p=\{k_2x\}-\{k_1x\}$, dan kesimpulannya terbukti. $\square$

Akibat 20.2.6

Untuk setiap $x\in\mathbb{R}$ dan $N\in\mathbb{N}_{+}$ ada pecahan $\tfrac pq$ dengan $1\leq q\leq N$ dan $\bigl|x-\tfrac pq\bigr|<\tfrac1{qN}\leq\tfrac1{q^2}$.

Bukti. Bagi ketaksamaan Teorema 20.2.5 dengan $q>0$, lalu gunakan $q\leq N$. $\square$

Ini mempertajam kerapatan $\mathbb{Q}$ (Teorema 11.3.11). Setiap bilangan real dapat dihampiri oleh pecahan dengan galat yang kecil relatif terhadap penyebutnya, dan keberadaan pecahan itu dijamin oleh sarang merpati.

Model Hipotetis: Tabrakan pada Hashing

Sebuah fungsi hash dimodelkan sebagai fungsi $h:K\to[m]$ dari himpunan kunci $K$ ke $m$ ember (bucket). Tabrakan adalah dua kunci berbeda $k\ne k'$ dengan $h(k)=h(k')$.

Proposisi 20.2.7

(a) Jika $|K|>m$, setiap fungsi $h:K\to[m]$ mengalami tabrakan.

(b) Jika $|K|>cm$ untuk $c\in\mathbb{N}$, ada ember yang menampung paling sedikit $c+1$ kunci.

Bukti. (a) Teorema 20.2.1. (b) Teorema 20.2.2. $\square$

Proposisi ini adalah pernyataan keberadaan tentang setiap fungsi, termasuk fungsi yang dirancang sebaik mungkin. Tabrakan tak terhindarkan begitu kunci lebih banyak daripada ember, sehingga struktur data harus mempunyai cara menangani tabrakan. Proposisi ini tidak mengatakan apa pun tentang seberapa sering tabrakan terjadi pada masukan tertentu, atau tentang kinerja fungsi hash tertentu. Pertanyaan-pertanyaan itu memerlukan analisis lain dan data dari sistem yang dipakai.

Latihan

Latihan 20.2-1. Turunkan Teorema 20.2.1 dari Teorema 20.1.4, dengan menjelaskan peran bijeksi $\alpha$ dan $\beta$.

Latihan 20.2-2. (Model hipotetis.) Dalam sebuah kelompok berisi $13$ orang, tunjukkan bahwa paling sedikit dua orang lahir pada bulan yang sama. Berapa banyak orang yang diperlukan untuk menjamin bahwa paling sedikit tiga orang lahir pada bulan yang sama?

Latihan 20.2-3. Buktikan Teorema 20.2.2, termasuk rumus $|A|=\sum_b|f^{-1}[\{b\}]|$.

Latihan 20.2-4. Buktikan bahwa di antara tujuh bilangan bulat ada dua yang selisihnya habis dibagi $6$. Tunjukkan bahwa enam bilangan bulat tidak cukup.

Latihan 20.2-5. Buktikan bahwa di antara $n+1$ bilangan dari $\{1,2,\ldots,2n\}$ ada dua yang berturutan.

Latihan 20.2-6. Terapkan Teorema 20.2.5 pada $x=\sqrt2$ dan $N=5$. Temukan $p,q$ dengan $1\leq q\leq5$ dan $|q\sqrt2-p|<\tfrac15$, dengan perhitungan eksak.

Latihan 20.2-7. Tunjukkan bahwa batas $\tfrac{\sqrt2}2$ pada Contoh 20.2.4 tidak dapat diperbaiki dengan empat titik: berikan empat titik di $[0,1]^2$ yang jarak berpasangannya semuanya paling sedikit $1$.

Latihan 20.2-8. Dalam model hashing dengan $m=100$ ember dan $|K|=1001$ kunci, buktikan bahwa ada ember dengan paling sedikit $11$ kunci. Berikan fungsi $h$ yang menunjukkan bahwa $12$ tidak dijamin.

Solusi

Solusi 20.2-1. $\alpha$ dan $\beta$ memindahkan masalah ke himpunan standar. Injektivitas $f$ akan memberi injeksi $[m]\to[n]$ lewat $\beta^{-1}\circ f\circ\alpha$, yang dilarang oleh Teorema 20.1.4 karena $m>n$. $\square$

Solusi 20.2-2. Pemetaan orang ke bulan memetakan $13$ ke $12$, sehingga ada tabrakan (Teorema 20.2.1). Untuk tiga orang sebulan: Teorema 20.2.2 dengan $k=2$ memerlukan $|A|>24$, yaitu $25$ orang. Dua puluh empat orang tidak cukup, misalnya tepat dua orang per bulan. $\square$

Solusi 20.2-3. Lihat bukti Teorema 20.2.2. $\square$

Solusi 20.2-4. Contoh 20.2.3 dengan $n=6$. Enam bilangan $0,1,2,3,4,5$ mempunyai sisa berbeda, sehingga tidak ada dua yang selisihnya kelipatan $6$. Selisihnya di antara $1$ dan $5$, bukan nol. $\square$

Solusi 20.2-5. Kotak $\{1,2\},\{3,4\},\ldots,\{2n-1,2n\}$ berjumlah $n$. Ada $n+1$ bilangan, sehingga dua bilangan masuk kotak yang sama, dan keduanya berturutan. $\square$

Solusi 20.2-6. Coba $q=5$: $5\sqrt2=\sqrt{50}$, dan $7^2=49<50<\tfrac{225}4=7{,}5^2$, sehingga $7<5\sqrt2<7{,}5$. Lebih tajam: $7{,}1^2=50{,}41>50$, sehingga $7<5\sqrt2<7{,}1$. Jadi $|5\sqrt2-7|<0{,}1<\tfrac15$, dengan $p=7$ dan $q=5$. Teorema menjamin keberadaannya, dan perhitungan memberi saksinya. $\square$

Solusi 20.2-7. Empat titik sudut $(0,0)$, $(1,0)$, $(0,1)$, $(1,1)$ mempunyai jarak berpasangan $1$ atau $\sqrt2$, semuanya $\geq1>\tfrac{\sqrt2}2$. Jadi lima titik memang diperlukan. $\square$

Solusi 20.2-8. $1001>10\cdot100$, sehingga Teorema 20.2.2 dengan $k=10$ memberi ember dengan $\geq11$ kunci. Fungsi yang menempatkan $11$ kunci di satu ember dan $10$ kunci di setiap ember lain memakai $11+99\cdot10=1001$ kunci, tanpa ember berisi $12$. $\square$

Ringkasan

Prinsip Sarang Merpati, yaitu tidak ada injeksi dari himpunan hingga yang lebih besar ke yang lebih kecil, adalah Teorema 20.1.4 dalam bahasa objek dan kotak. Versi umumnya menjamin kotak berisi paling sedikit $k+1$ objek bila objek lebih dari $k$ kali banyak kotak. Penerapannya meliputi sisa pembagian, titik di persegi, teorema aproksimasi Dirichlet (penajaman kerapatan $\mathbb{Q}$), dan model tabrakan hashing, yang tak terhindarkan tetapi tidak diklaim seberapa sering terjadi. Unit 20.3 membahas karakterisasi ketakhinggaan menurut Dedekind.

20.3 Himpunan Tak Hingga oleh Dedekind

Definisi 20.1.2 menyatakan bahwa suatu himpunan tak hingga bila tidak dapat dipasangkan dengan $\{1,\ldots,n\}$ untuk $n$ mana pun. Definisi ini negatif: ia berkata apa yang tidak ada. Richard Dedekind (1888) mengusulkan definisi positif yang menangkap gejala paling mencolok dari ketakhinggaan: himpunan tak hingga dapat dipasangkan satu-satu dengan sebagian dirinya sendiri. Contohnya, $\mathbb{N}$ dipasangkan dengan bilangan genap lewat $n\mapsto2n$, padahal bilangan genap hanya sebagian dari $\mathbb{N}$.

Unit ini membuktikan bahwa setiap himpunan Dedekind-tak hingga memang tak hingga, dan bahwa sifat Dedekind setara dengan memuat salinan $\mathbb{N}$. Unit ini juga menjelaskan batas yang tepat: arah sebaliknya, "setiap himpunan tak hingga Dedekind-tak hingga", tidak dapat dibuktikan tanpa suatu bentuk aksioma pilihan. Fakta metamatematika itu dicatat dengan sumbernya, dan pembahasan aksioma pilihan dijadwalkan pada Bab 23.3.

Prasyarat: Unit 20.1 (khususnya Akibat 20.1.8 dan Teorema 20.1.11); fungsi dan injeksi (Bab 5); rekursi (Teorema 7.4.1) dan urutan baik (Teorema 7.3.4).

Definisi dan Kesetaraan

Definisi 20.3.1 (Dedekind-Tak Hingga)

Himpunan $A$ disebut Dedekind-tak hingga jika terdapat fungsi $f:A\to A$ yang injektif tetapi tidak surjektif. Himpunan yang tidak demikian disebut Dedekind-hingga.

Setara: $A$ Dedekind-tak hingga jika dan hanya jika ada bijeksi antara $A$ dan suatu subhimpunan sejati $B\subsetneq A$. Bila $f$ seperti pada definisi, $B=f[A]$ sejati dan $f:A\to B$ bijeksi. Sebaliknya, bijeksi $A\to B\subsetneq A$, dipandang sebagai fungsi ke $A$, injektif dan tidak surjektif.

Teorema 20.3.2 (Dedekind-Tak Hingga Mengakibatkan Tak Hingga)

Setiap himpunan Dedekind-tak hingga adalah tak hingga. Ekuivalennya, setiap himpunan hingga adalah Dedekind-hingga.

Bukti. Akibat 20.1.8: injeksi diri himpunan hingga selalu surjektif. $\square$

Teorema 20.3.3 (Karakterisasi lewat $\mathbb{N}$)

Untuk himpunan $A$, pernyataan berikut setara:

(a) $A$ Dedekind-tak hingga;

(b) terdapat injeksi $g:\mathbb{N}\to A$.

Bukti. (b)⇒(a). Misalkan $g:\mathbb{N}\to A$ injektif. Definisikan $f:A\to A$ oleh

Definisi ini sah: bila $a=g(n)$, bilangan $n$ tunggal karena $g$ injektif.

$f$ injektif. Dua anggota dari $g[\mathbb{N}]$ dipetakan ke $g(n+1)$ dan $g(n'+1)$, yang berbeda bila $n\ne n'$. Dua anggota di luar $g[\mathbb{N}]$ dipetakan ke dirinya sendiri. Anggota $a=g(n)$ dan anggota $b\notin g[\mathbb{N}]$ dipetakan ke $g(n+1)\in g[\mathbb{N}]$ dan $b\notin g[\mathbb{N}]$, yang berbeda.

$f$ tidak surjektif. $g(0)$ tidak berada dalam peta. Bila $f(a)=g(0)$, maka $a$ tidak mungkin di luar $g[\mathbb{N}]$, karena $f(a)=a\notin g[\mathbb{N}]$. Jadi $a=g(n)$ dan $g(n+1)=g(0)$, sehingga $n+1=0$, mustahil di $\mathbb{N}$.

(a)⇒(b). Misalkan $f:A\to A$ injektif dan $a_0\in A\setminus f[A]$. Teorema rekursi 7.4.1 memberi barisan $g:\mathbb{N}\to A$ dengan $g(0)=a_0$ dan $g(n+1)=f(g(n))$, yaitu $g(n)=f^n(a_0)$.

Kita buktikan $g$ injektif. Andaikan tidak. Pilih, dengan urutan baik, $m$ terkecil sehingga ada $k>m$ dengan $g(m)=g(k)$.

• Jika $m=0$: $a_0=g(k)=f(g(k-1))\in f[A]$, kontradiksi dengan pilihan $a_0$.
• Jika $m\geq1$: $f(g(m-1))=g(m)=g(k)=f(g(k-1))$, dan injektivitas $f$ memberi $g(m-1)=g(k-1)$ dengan $k-1>m-1$, bertentangan dengan minimalitas $m$.

$\square$

Kedua arah dibuktikan tanpa aksioma pilihan. Arah (a)⇒(b) memakai satu pilihan tunggal $a_0$, yang sah karena $A\setminus f[A]\ne\emptyset$, lalu rekursi yang ditentukan oleh $f$.

Contoh 20.3.4 (Himpunan Dedekind-Tak Hingga)

(a) $\mathbb{N}$: $n\mapsto n+1$ injektif dan melewatkan $0$. Atau $n\mapsto2n$, yang melewatkan bilangan ganjil.

(b) $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$: masing-masing memuat $\mathbb{N}$, dan inklusi adalah injeksi $\mathbb{N}\to A$ (Teorema 20.3.3).

(c) $(0,1)$: $n\mapsto\tfrac1{n+2}$ adalah injeksi $\mathbb{N}\to(0,1)$. Setiap nilai di $(0,\tfrac12]$, dan $n\ne n'$ memberi pecahan berbeda.

(d) Untuk $a<b$, $(a,b)$ dan $[a,b]$: injeksi $n\mapsto a+\tfrac{b-a}{n+2}$.

Gambaran populer "Hotel Hilbert", yaitu hotel dengan kamar bernomor $0,1,2,\ldots$ yang penuh tetapi masih dapat menerima tamu baru dengan memindahkan setiap tamu dari kamar $n$ ke kamar $n+1$, adalah ilustrasi Contoh 20.3.4(a). Kamar $0$ menjadi kosong. Ini hanya ilustrasi; bukti formalnya adalah fungsi $n\mapsto n+1$.

Subhimpunan Tak Hingga dari $\mathbb{N}$

Teorema 20.3.5

Setiap subhimpunan tak hingga $S\subseteq\mathbb{N}$ adalah Dedekind-tak hingga. Lebih tepatnya, ada bijeksi naik tegas $e:\mathbb{N}\to S$.

Bukti. Untuk setiap $t\in\mathbb{N}$, himpunan $S_{>t}=\{s\in S:s>t\}$ tidak kosong. Kalau kosong, $S\subseteq\{0,1,\ldots,t\}$, yang hingga karena dalam bijeksi dengan $[t+1]$ lewat $k\mapsto k-1$. Maka $S$ hingga menurut Teorema 20.1.7, kontradiksi. Juga $S\ne\emptyset$.

Definisikan dengan rekursi (Teorema 7.4.1) dan urutan baik (Teorema 7.3.4): $e(0)=\min S$ dan $e(n+1)=\min S_{>e(n)}$. Langkah rekursinya adalah fungsi tertentu $t\mapsto\min S_{>t}$, sehingga tidak ada pilihan sebarang.

• $e$ naik tegas, karena $e(n+1)>e(n)$. Jadi $e$ injektif.
• $e$ surjektif. Andaikan $s\in S$ tidak termasuk peta $e$. Induksi memberi $e(n)\geq n$ untuk semua $n$, sehingga ada $n$ dengan $e(n)>s$; misalnya $e(s+1)\geq s+1>s$. Ambil $n$ terkecil dengan $e(n)>s$. Bila $n=0$, $\min S>s$, mustahil karena $s\in S$. Bila $n\geq1$, $e(n-1)<s<e(n)$, karena $e(n-1)\leq s$ dan $s\ne e(n-1)$. Maka $s\in S_{>e(n-1)}$ dan $s<\min S_{>e(n-1)}=e(n)$, kontradiksi.

$\square$

Bukti ini memakai urutan baik $\mathbb{N}$ untuk memilih secara tertentu, yaitu anggota terkecil, sehingga tidak memerlukan aksioma pilihan. Hal yang sama berlaku untuk setiap himpunan yang mempunyai urutan baik yang diberikan.

Batas yang Tidak Dapat Dilewati Tanpa Pilihan

Untuk himpunan sebarang $A$, implikasi "tak hingga ⇒ Dedekind-tak hingga" mengikuti dari aksioma pilihan terhitung. Secara intuitif, pilihan terhitung memungkinkan kita memilih $a_0$, lalu $a_1\ne a_0$, lalu $a_2\notin\{a_0,a_1\}$, dan seterusnya, sehingga terbentuk injeksi $\mathbb{N}\to A$. Langkah-langkah itu tidak ditentukan oleh rumus apa pun bila $A$ tidak mempunyai struktur yang dapat dipakai.

Fakta metamatematika berikut dicatat tanpa bukti, karena buktinya memerlukan teknik pembuatan model teori himpunan yang berada di luar buku ini. Dalam teori himpunan Zermelo–Fraenkel tanpa aksioma pilihan (ZF), implikasi itu tidak dapat dibuktikan: ada model ZF yang memuat himpunan tak hingga yang Dedekind-hingga (contoh klasiknya model pertama Cohen). Pernyataan "setiap himpunan tak hingga Dedekind-tak hingga" juga tegas lebih lemah daripada aksioma pilihan terhitung. Sumber ikhtisar: entri "Dedekind-infinite set", Wikipedia, diakses 2 Oktober 2026 (https://en.wikipedia.org/wiki/Dedekind-infinite_set), yang merujuk pada literatur standar teori himpunan. Klaim di paragraf ini dibatasi pada isi sumber tersebut.

Rencana penutupan: Bab 23.3 membahas aksioma pilihan dan Lemma Zorn. Di sana implikasi "tak hingga ⇒ Dedekind-tak hingga" dibuktikan dengan asumsi pilihan yang disebut eksplisit. Sampai saat itu, buku ini hanya memakai Teorema 20.3.2–20.3.5, yang semuanya dibuktikan tanpa pilihan. Untuk semua himpunan konkret di analisis ($\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, interval), sifat Dedekind ditunjukkan langsung dengan injeksi eksplisit, seperti pada Contoh 20.3.4.

Latihan

Latihan 20.3-1. Buktikan bahwa $n\mapsto2n$ adalah bijeksi dari $\mathbb{N}$ ke himpunan bilangan genap, dan simpulkan bahwa $\mathbb{N}$ Dedekind-tak hingga.

Latihan 20.3-2. Buktikan Teorema 20.3.2 secara langsung untuk $A=[3]$: tunjukkan bahwa setiap injeksi $[3]\to[3]$ surjektif.

Latihan 20.3-3. Pada bukti Teorema 20.3.3 (b)⇒(a), periksa fungsi $f$ untuk $A=\mathbb{Z}$ dan $g(n)=n$. Tuliskan $f(-3)$, $f(0)$, $f(5)$, dan tentukan anggota yang tidak berada dalam peta $f$.

Latihan 20.3-4. Buktikan bahwa $(0,1)$ dan $[0,1]$ Dedekind-tak hingga dengan injeksi eksplisit dari $\mathbb{N}$.

Latihan 20.3-5. Untuk $S=\{n\in\mathbb{N}:n\text{ kelipatan }3\}$, tuliskan $e(0),e(1),e(2)$ dari Teorema 20.3.5, lalu rumus umum $e(n)$ beserta bukti.

Latihan 20.3-6. Buktikan bahwa jika $A$ Dedekind-tak hingga dan $A\subseteq B$, maka $B$ Dedekind-tak hingga.

Latihan 20.3-7. Buktikan bahwa jika $A$ Dedekind-tak hingga, maka $A\cup\{x\}$ berbijeksi dengan $A$ untuk setiap $x\notin A$.

Latihan 20.3-8. Jelaskan dengan kata-kata sendiri mengapa bukti Teorema 20.3.5 tidak memerlukan aksioma pilihan, sedangkan argumen "pilih $a_0$, lalu $a_1\ne a_0$, dan seterusnya" untuk himpunan tak hingga sebarang memerlukannya.

Solusi

Solusi 20.3-1. Injektif: $2n=2n'$ memberi $n=n'$. Surjektif ke bilangan genap: setiap genap berbentuk $2n$. Fungsi $n\mapsto2n$, dipandang sebagai fungsi $\mathbb{N}\to\mathbb{N}$, injektif dan tidak memuat $1$ dalam petanya. $\square$

Solusi 20.3-2. Injeksi $f:[3]\to[3]$ mempunyai tiga nilai berbeda di $[3]$, sehingga petanya subhimpunan $[3]$ berkardinalitas $3$. Teorema 20.1.7 memaksa peta itu sama dengan $[3]$. $\square$