Himpunan hingga, kardinalitas কী?

Contoh 2.6 (Kehinggaan itu penting)

Pada himpunan yang hingga, Proposisi 2.5 adalah jalan pintas yang ampuh: setiap pemetaan injektif dari $E$ ke dirinya sendiri otomatis menjadi permutasi $E$ — separuh dari kebijektifan datang cuma-cuma. Kedua implikasi itu runtuh pada himpunan tak hingga: $n \mapsto n + 1$ injektif dari $\N$ ke $\N$ tetapi melewatkan $0$, dan pemetaan $\N \to \N$ yang mengirim $0 \mapsto 0$ dan $n \mapsto n - 1$ untuk $n \geq 1$ surjektif tetapi tidak injektif. Setiap kali proposisi ini dipanggil, hipotesis kehinggaannya sedang bekerja sungguhan — tema yang ditelusuri soal akhir pekan Bab 1 dari sisi yang berlawanan, tempat himpunan tak hingga persis adalah himpunan yang punya pemetaan-diri semacam itu.

Contoh 2.7 (Separuh pekerjaan, cuma-cuma)

Tinjau pemetaan $f$ pada $\{0, 1, \dots, 6\}$ yang mengirim $k$ ke sisa pembagian $3k$ oleh $7$; tabel nilainya adalah

Apakah $f$ sebuah bijeksi? Keinjektifan saja sudah cukup (Proposisi 2.5): jika $3k$ dan $3k'$ bersisa sama, maka $7$ membagi $3(k - k')$, dan karena $7$ prima serta tidak membagi $3$, ia membagi $k - k'$ (lema Euclid, yang di sini dipakai pada taraf sekolah menengah dan dibuktikan pada Bab 6); dengan $\abs{k - k'} \leq 6$ hal ini memaksa $k = k'$. Kesurjektifan datang cuma-cuma — tak perlu menyelesaikan $3k \equiv c$ untuk setiap $c$, meskipun tabelnya membenarkan bahwa setiap nilai muncul tepat sekali. Jalan pintas itu adalah kuda beban: ia membuktikan keterbalikan perkalian modular (Bab 6), menggerakkan pemasangan pada teorema Wilson, dan kembali dalam aljabar linear sebagai “endomorfisma ruang berdimensi hingga bersifat injektif jika dan hanya jika surjektif” (Bab 19).

Contoh 2.17

Dua pengkhususan klasik: $a = b = 1$ memulihkan $\sum_k \binom nk = 2^n$; $a = -1$, $b = 1$ memberikan $\sum_{k} (-1)^k \binom nk = 0$ untuk $n \geq 1$: di antara himpunan bagian sebuah himpunan tak kosong, tepat separuhnya berkardinalitas genap.