Apa itu Ekuipotensi, keterbilangan?

Contoh 1.7 (Fungsi pemasangan, dihitung)

Bijeksi $(p, q) \mapsto 2^p(2q + 1) - 1$ dalam bukti di atas pantas dilihat sedang bekerja. Nilai-nilai pertamanya:

Baris $p$ menghimpun bilangan $n$ yang $n + 1$-nya habis dibagi tepat oleh $2^p$: setiap bilangan cacah muncul tepat sekali. Pembacaan baliknya segamblang penyandiannya: untuk $n = 43$, faktorkan $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$, sehingga $(p, q) = (2, 5)$. Pelajaran penutupnya: bukti keterbilangan sering kali berupa algoritme yang menyamar — di sini, “keluarkan semua faktor dua”.

Contoh 1.8 (Bilangan aljabar adalah terbilang)

Suatu bilangan kompleks disebut aljabar apabila ia menolkan suatu polinomial tak nol berkoefisien rasional. Himpunan $\overline\Q$ semua bilangan aljabar adalah terbilang: polinomial berderajat $\leq d$ atas $\Q$ terinjeksi ke $\Q^{d+1}$, yaitu hasil kali hingga atas himpunan terbilang (Proposisi 1.6 (2)); gabungan atas $d$ menyusun semua polinomial rasional tak nol sebagai $P_0, P_1, P_2, \dots$; setiap $P_k$ punya berhingga banyak akar; dan

adalah gabungan terbilang atas himpunan hingga (Proposisi 1.6 (3)), tak hingga karena memuat $\Q$. Digabungkan dengan ketakterbilangan $\R$ (Teorema 1.9 di bawah), ini membuktikan — tanpa menunjukkan satu pun contohnya — bahwa bilangan transenden memang ada dan justru merupakan mayoritas yang tak terbilang: itulah hujah pencacahan Cantor tahun 1874, keberadaan semata-mata lewat kardinalitas.

Contoh 1.11

$\intoo{0}{1}$ dan $\intcc{0}{1}$ ekuipoten: identitas menginjeksikan satu arah, $x \mapsto \frac{x + 1}{3}$ arah sebaliknya; teorema tadi memproduksi bijeksinya (yang mau tak mau tak kontinu). Demikian pula $\R$, $\intoo{0}{1}$ (lewat bijeksi bertipe $\tanh$) dan $\mathcal{P}(\N)$ (uraian biner, Latihan 1.3) semuanya ekuipoten: itulah “kardinalitas kontinum”.