Bab 21: Keteranhimpunan (Countability)

21.1 Definisi Himpunan Berhingga Terhitung (Denumerable)

Bab 20 memisahkan himpunan hingga dari himpunan tak hingga. Bab 21 mulai membedakan di antara himpunan tak hingga. Himpunan tak hingga yang "paling kecil" adalah himpunan yang anggotanya dapat dicacah satu per satu, $a_0,a_1,a_2,\ldots$, tanpa ada yang terlewat. Himpunan semacam itu disebut terhitung tak hingga (denumerable). Bab 22 akan menunjukkan bahwa tidak semua himpunan tak hingga demikian: $\mathbb{R}$ terlalu besar untuk dicacah.

Catatan istilah. Judul master unit ini memakai frasa "himpunan berhingga terhitung (denumerable)". Istilah Inggris denumerable lazim berarti terhitung dan tak hingga, yaitu dalam bijeksi dengan $\mathbb{N}$. Untuk menghindari kerancuan dengan "berhingga" pada Bab 20, teks unit ini memakai:

• terhitung tak hingga (denumerable) untuk himpunan yang berbijeksi dengan $\mathbb{N}$;
• terhitung (countable) untuk himpunan yang hingga atau terhitung tak hingga.

Judul unit dibiarkan persis seperti master. Pilihan istilah dalam badan teks dicatat untuk keputusan penulis.

Prasyarat: Bab 20 (himpunan hingga, Teorema 20.1.7, 20.1.10, 20.1.11, 20.3.3, 20.3.5); fungsi (Bab 5); urutan baik (Teorema 7.3.4).

Definisi

Definisi 21.1.1 (Terhitung Tak Hingga dan Terhitung)

(a) Himpunan $A$ disebut terhitung tak hingga (denumerable) jika terdapat bijeksi $f:\mathbb{N}\to A$. Bijeksi semacam itu disebut pencacahan $A$, dan $a_n=f(n)$ ditulis sebagai barisan $a_0,a_1,a_2,\ldots$ tanpa pengulangan dan tanpa anggota yang terlewat.

(b) Himpunan $A$ disebut terhitung (countable) jika $A$ hingga atau terhitung tak hingga. Himpunan yang tidak terhitung disebut tak terhitung (uncountable).

Himpunan terhitung tak hingga memang tak hingga: bila $A$ berbijeksi dengan $\mathbb{N}$ dan $A$ hingga, maka $\mathbb{N}$ hingga, bertentangan dengan Teorema 20.1.11. Dengan bijeksi sebagai alat pembanding, istilah "sama besar" untuk himpunan tak hingga dibahas pada Bab 23.1. Untuk sekarang, cukup: semua himpunan terhitung tak hingga berbijeksi satu sama lain lewat $\mathbb{N}$.

Contoh 21.1.2

(a) $\mathbb{N}$: pencacahan identitas.

(b) $\mathbb{N}_{+}$: $n\mapsto n+1$.

(c) Bilangan genap $\{0,2,4,\ldots\}$: $n\mapsto2n$.

(d) $\{n^2:n\in\mathbb{N}\}$: $n\mapsto n^2$. Fungsi ini injektif karena naik tegas pada $[0,\infty)$ (Teorema 10.2.6).

(e) Himpunan hingga, termasuk $\emptyset$, terhitung tetapi tidak terhitung tak hingga.

Contoh (b)–(d) memperlihatkan gejala Dedekind (Unit 20.3): himpunan terhitung tak hingga dapat berbijeksi dengan bagian sejatinya.

Karakterisasi

Teorema 21.1.3 (Karakterisasi Himpunan Terhitung)

Untuk himpunan $A$, pernyataan berikut setara:

(a) $A$ terhitung;

(b) terdapat injeksi $A\to\mathbb{N}$;

(c) $A=\emptyset$, atau terdapat surjeksi $\mathbb{N}\to A$.

Bukti. (a)⇒(b). Bila $A$ hingga dengan bijeksi $f:[n]\to A$, maka $f^{-1}$ adalah injeksi $A\to[n]\subseteq\mathbb{N}$. Bila $A$ terhitung tak hingga, invers pencacahan adalah injeksi.

(b)⇒(a). Misalkan $g:A\to\mathbb{N}$ injektif, dan $S=g[A]\subseteq\mathbb{N}$. Fungsi $g:A\to S$ adalah bijeksi.

• Bila $S$ hingga, $A$ hingga.
• Bila $S$ tak hingga, Teorema 20.3.5 memberi bijeksi $e:\mathbb{N}\to S$, dan $g^{-1}\circ e:\mathbb{N}\to A$ adalah bijeksi.

(a)⇒(c). Bila $A$ hingga tak kosong dengan bijeksi $f:[n]\to A$, $n\geq1$, definisikan $h(k)=f(k)$ untuk $1\leq k\leq n$ dan $h(k)=f(1)$ untuk $k=0$ atau $k>n$. Fungsi ini surjektif. Bila $A$ terhitung tak hingga, pencacahan itu sendiri surjektif.

(c)⇒(b). Bila $A=\emptyset$, fungsi kosong adalah injeksi. Bila $h:\mathbb{N}\to A$ surjektif, untuk setiap $a\in A$ himpunan $h^{-1}[\{a\}]\subseteq\mathbb{N}$ tidak kosong. Definisikan $g(a)=\min h^{-1}[\{a\}]$, dengan minimum yang ada menurut urutan baik. Fungsi $g$ injektif, karena $h(g(a))=a$, sehingga $g(a)=g(a')$ memberi $a=a'$. $\square$

Arah (c)⇒(b) tidak memerlukan aksioma pilihan, karena setiap pilihan ditentukan oleh "anggota terkecil". Inilah keuntungan $\mathbb{N}$ yang terurut baik.

Bentuk (c) adalah alat paling praktis. Untuk membuktikan suatu himpunan terhitung, cukup tunjukkan suatu daftar $a_0,a_1,a_2,\ldots$ yang memuat setiap anggotanya. Pengulangan diperbolehkan, dan daftar itu tidak perlu tanpa pengulangan.

Akibat 21.1.4

(a) Subhimpunan himpunan terhitung adalah terhitung.

(b) Peta himpunan terhitung oleh suatu fungsi adalah terhitung.

(c) Subhimpunan tak hingga dari himpunan terhitung tak hingga adalah terhitung tak hingga.

Bukti. (a) Pembatasan injeksi $A\to\mathbb{N}$ ke subhimpunan tetap injeksi.

(b) Bila $A$ terhitung tak kosong dengan surjeksi $h:\mathbb{N}\to A$ dan $f:A\to B$, maka $f\circ h:\mathbb{N}\to f[A]$ surjektif. Bila $A=\emptyset$, petanya kosong.

(c) Menurut (a), subhimpunan itu terhitung. Karena tak hingga, ia terhitung tak hingga. $\square$

Akibat 21.1.5 (Terhitung Tak Hingga sebagai Tak Hingga Terkecil)

Setiap himpunan Dedekind-tak hingga memuat subhimpunan terhitung tak hingga. Sebaliknya, himpunan terhitung tak hingga tidak memuat subhimpunan tak hingga yang tak terhitung.

Bukti. Teorema 20.3.3 memberi injeksi $g:\mathbb{N}\to A$, dan $g[\mathbb{N}]$ terhitung tak hingga. Bagian kedua adalah Akibat 21.1.4(a). $\square$

Dengan penyelesaian pertanyaan pilihan pada Bab 23.3, "setiap himpunan tak hingga memuat himpunan terhitung tak hingga" akan menjadi pernyataan untuk semua himpunan tak hingga. Untuk sekarang pernyataan itu berlaku untuk himpunan Dedekind-tak hingga, yang mencakup semua himpunan konkret di analisis.

Latihan

Latihan 21.1-1. Tuliskan pencacahan eksplisit untuk himpunan bilangan ganjil positif dan untuk $\{10,11,12,\ldots\}$, lalu buktikan bijektivitasnya.

Latihan 21.1-2. Buktikan bahwa setiap himpunan terhitung tak hingga adalah tak hingga dan Dedekind-tak hingga.

Latihan 21.1-3. Buktikan Teorema 21.1.3 (b)⇒(a) untuk $A=\{n\in\mathbb{N}:n\text{ prima}\}$ dengan $g$ inklusi. Anda boleh memakai fakta bahwa ada tak hingga banyak bilangan prima, tetapi sebutkan statusnya sebagai pinjaman.

Latihan 21.1-4. Buktikan bahwa jika $A$ terhitung dan $B$ hingga, maka $A\cup B$ terhitung, tanpa memakai Unit 21.3.

Latihan 21.1-5. Tunjukkan bahwa daftar $0,0,1,0,1,2,0,1,2,3,\ldots$ memuat setiap bilangan asli. Apa yang dikatakan Teorema 21.1.3 tentang daftar dengan pengulangan semacam ini?

Latihan 21.1-6. Buktikan Akibat 21.1.4(b) dan berikan contoh fungsi yang memetakan himpunan terhitung tak hingga ke himpunan hingga.

Latihan 21.1-7. Buktikan bahwa $\{\tfrac1n:n\in\mathbb{N}_{+}\}$ dan $\mathbb{N}\times\{0,1\}$ terhitung tak hingga.

Latihan 21.1-8. Buktikan bahwa jika $f:A\to B$ injektif dan $B$ terhitung, maka $A$ terhitung. Apakah kebalikannya berlaku?

Solusi

Solusi 21.1-1. Ganjil positif: $n\mapsto2n+1$. Injektif jelas. Surjektif karena setiap ganjil positif berbentuk $2n+1$ dengan $n\in\mathbb{N}$ (pembagian Euclid dengan sisa $1$). $\{10,11,\ldots\}$: $n\mapsto n+10$, dengan invers $m\mapsto m-10$. $\square$

Solusi 21.1-2. Tak hingga: lihat paragraf setelah Definisi 21.1.1. Dedekind-tak hingga: pencacahan adalah injeksi $\mathbb{N}\to A$, lalu gunakan Teorema 20.3.3. $\square$

Solusi 21.1-3. $g$ inklusi, sehingga $S=g[A]=A$. Bila himpunan bilangan prima tak hingga, Teorema 20.3.5 memberi pencacahan naik $e$, dengan $e(0)=2$, $e(1)=3$, $e(2)=5$, dan seterusnya. Ketakhinggaan bilangan prima adalah fakta teori bilangan (bukti Euklides) yang tidak dibuktikan di buku ini, sehingga dipakai sebagai pinjaman di luar lingkup. Tanpa fakta itu, Teorema 21.1.3 tetap memberi "terhitung" tanpa menentukan hingga atau tak hingga. $\square$

Solusi 21.1-4. Bila $A=\emptyset$, $A\cup B=B$ hingga. Bila tidak, ambil surjeksi $h:\mathbb{N}\to A$ dan bijeksi $b:[m]\to B$. Definisikan $h'(k)=b(k+1)$ untuk $k<m$ dan $h'(k)=h(k-m)$ untuk $k\geq m$. Fungsi $h'$ surjektif ke $A\cup B$. $\square$

Solusi 21.1-5. Bilangan $m$ muncul pada blok ke-$m$ dan sesudahnya, misalnya sebagai unsur terakhir blok $0,1,\ldots,m$. Teorema 21.1.3(c): daftar dengan pengulangan yang memuat semua anggota sudah cukup untuk menyimpulkan keterhitungan. $\square$

Solusi 21.1-6. Bukti: lihat Akibat 21.1.4. Contoh: $f:\mathbb{N}\to\{0,1\}$ yang memetakan $n$ ke sisa pembagian $n$ oleh $2$. $\square$

Solusi 21.1-7. $n\mapsto\tfrac1{n+1}$ adalah bijeksi $\mathbb{N}\to\{\tfrac1n:n\geq1\}$, injektif karena $\tfrac1a=\tfrac1b\Rightarrow a=b$. $\mathbb{N}\times\{0,1\}$: $(n,i)\mapsto2n+i$ adalah bijeksi ke $\mathbb{N}$ (pembagian Euclid oleh $2$), dan inversnya adalah pencacahan. $\square$

Solusi 21.1-8. Injeksi $A\to B$ yang dikomposisikan dengan injeksi $B\to\mathbb{N}$ adalah injeksi $A\to\mathbb{N}$. Lalu gunakan Teorema 21.1.3. Kebalikannya tidak berlaku: inklusi $\mathbb{N}\to\mathbb{R}$ injektif dan $\mathbb{N}$ terhitung, tetapi $\mathbb{R}$ tak terhitung (Bab 22). $\square$

Ringkasan

Himpunan terhitung tak hingga adalah himpunan yang berbijeksi dengan $\mathbb{N}$, dan himpunan terhitung adalah yang hingga atau terhitung tak hingga. Keterhitungan setara dengan adanya injeksi ke $\mathbb{N}$, dan dengan adanya daftar (boleh berulang) yang memuat semua anggota. Kedua kesetaraan itu dibuktikan tanpa aksioma pilihan berkat urutan baik $\mathbb{N}$. Subhimpunan dan peta himpunan terhitung tetap terhitung, dan himpunan terhitung tak hingga adalah tak hingga yang terkecil dalam arti Akibat 21.1.5. Unit 21.2 membuktikan bahwa $\mathbb{Z}$, $\mathbb{N}\times\mathbb{N}$, dan $\mathbb{Q}$ terhitung tak hingga, yang terakhir lewat pencacahan diagonal Cantor.

21.2 Keterhitungan Bilangan Bulat $\mathbb{Z}$ dan Rasional $\mathbb{Q}$

Penjelasan master: bilangan rasional, yang tampak padat, ternyata mempunyai kardinalitas yang sama dengan bilangan bulat, dan ini dibuktikan melalui pemetaan matriks diagonal Cantor. Hasil ini berlawanan dengan intuisi. Di antara dua rasional selalu ada rasional lain (Teorema 11.3.11), sehingga tampaknya rasional jauh "lebih banyak" daripada bilangan bulat yang terpisah-pisah. Namun $\mathbb{Q}$ dapat didaftar sebagai barisan $q_0,q_1,q_2,\ldots$ yang memuat setiap rasional tepat sekali. Kerapatan adalah sifat urutan, sedangkan keterhitungan adalah sifat ukuran. Keduanya tidak saling menentukan.

Unit ini membuktikan keterhitungan $\mathbb{Z}$ dengan bijeksi eksplisit, keterhitungan $\mathbb{N}\times\mathbb{N}$ dengan fungsi pasangan Cantor (pencacahan antidiagonal pada tabel tak hingga, yaitu "matriks diagonal" dalam penjelasan master), lalu keterhitungan $\mathbb{Q}$.

Prasyarat: Unit 21.1; pembagian Euclid (Teorema 7.3.8); urutan baik (Teorema 7.3.4); Lema 8.4.6 (penyebut positif terkecil); Bab 20.

Bilangan Bulat

Teorema 21.2.1

Fungsi $z:\mathbb{N}\to\mathbb{Z}$ dengan

$$z(n)=\begin{cases}\tfrac n2,&n\text{ genap},\\-\tfrac{n+1}2,&n\text{ ganjil},\end{cases}$$

adalah bijeksi. Jadi $\mathbb{Z}$ terhitung tak hingga.

Bukti. Nilai $z$ adalah bilangan bulat. Untuk $n=2k$, $z(n)=k\geq0$. Untuk $n=2k+1$, $z(n)=-(k+1)\leq-1$.

• Injektif: dua bilangan genap berbeda memberi $k$ berbeda; dua bilangan ganjil berbeda memberi $-(k+1)$ berbeda; bilangan genap memberi nilai $\geq0$ dan bilangan ganjil memberi nilai $\leq-1$.
• Surjektif: $m\geq0$ adalah $z(2m)$, dan $m\leq-1$ adalah $z(-2m-1)$, dengan $-2m-1\geq1$ ganjil.

$\square$

Pencacahannya: $0,-1,1,-2,2,-3,3,\ldots$, yaitu bergantian menyamping dari nol.

Pasangan Bilangan Asli: Diagonal Cantor

Susun semua pasangan $(m,n)\in\mathbb{N}\times\mathbb{N}$ dalam tabel tak hingga, dengan baris $m$ dan kolom $n$. Tabel ini tidak dapat didaftar baris demi baris, karena baris pertama saja tidak pernah selesai. Cantor mendaftarnya menurut antidiagonal $m+n=k$ untuk $k=0,1,2,\ldots$. Setiap antidiagonal berhingga, memuat $k+1$ pasangan, sehingga setiap pasangan tercapai setelah berhingga langkah.

Definisi 21.2.2 (Bilangan Segitiga dan Fungsi Pasangan)

Untuk $k\in\mathbb{N}$, $T(k)=\tfrac{k(k+1)}2$. Untuk $(m,n)\in\mathbb{N}^2$, tetapkan

$$\pi(m,n)=T(m+n)+n.$$

$T(k)$ adalah bilangan asli: salah satu dari $k$ dan $k+1$ genap. $T(k)$ adalah banyaknya pasangan pada antidiagonal $0,\ldots,k-1$, karena $1+2+\cdots+k=T(k)$ (induksi). Jadi $\pi(m,n)$ adalah nomor urut pasangan $(m,n)$: lewati semua antidiagonal sebelumnya, lalu hitung posisi $n$ di dalam antidiagonal $k=m+n$.

Lemma 21.2.3

(a) $T(k+1)=T(k)+k+1$, sehingga $T$ naik tegas dan $T(k)\geq k$.

(b) Untuk setiap $N\in\mathbb{N}$ terdapat tepat satu $k\in\mathbb{N}$ dengan $T(k)\leq N<T(k+1)$.

Bukti. (a) $\tfrac{(k+1)(k+2)}2-\tfrac{k(k+1)}2=\tfrac{(k+1)\cdot2}2=k+1$. Induksi memberi $T(k)\geq k$.

(b) Keberadaan: himpunan $\{j\in\mathbb{N}:T(j+1)>N\}$ tidak kosong, karena $T(N+1)\geq N+1>N$. Ambil unsur terkecilnya $k$ (urutan baik). Maka $T(k+1)>N$. Bila $k=0$, $T(0)=0\leq N$. Bila $k\geq1$, minimalitas memberi $T(k)\leq N$.

Ketunggalan: jika $k<k'$ keduanya memenuhi, maka $T(k+1)\leq T(k')\leq N<T(k+1)$, menurut kemonotonan, kontradiksi. $\square$

Teorema 21.2.4 (Fungsi Pasangan Cantor)

$\pi:\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ adalah bijeksi. Jadi $\mathbb{N}\times\mathbb{N}$ terhitung tak hingga.

Bukti. Untuk $(m,n)$ dengan $k=m+n$: $T(k)\leq\pi(m,n)=T(k)+n\leq T(k)+k<T(k+1)$. Jadi $k$ adalah bilangan tunggal pada Lemma 21.2.3(b) untuk $N=\pi(m,n)$.

Injektif: jika $\pi(m,n)=\pi(m',n')=N$, maka $m+n=m'+n'=k$ (ketunggalan $k$), lalu $n=N-T(k)=n'$ dan $m=k-n=m'$.

Surjektif: untuk $N\in\mathbb{N}$, ambil $k$ dari Lemma 21.2.3(b), $n=N-T(k)$, dan $m=k-n$. Maka $0\leq n<T(k+1)-T(k)=k+1$, sehingga $0\leq n\leq k$ dan $m\geq0$. Jadi $(m,n)\in\mathbb{N}^2$ dan $\pi(m,n)=T(k)+n=N$. $\square$

Sepuluh nomor pertama:

Akibat 21.2.5

Jika $A$ dan $B$ terhitung, maka $A\times B$ terhitung. Jika keduanya terhitung tak hingga, $A\times B$ terhitung tak hingga.

Bukti. Injeksi $\alpha:A\to\mathbb{N}$ dan $\beta:B\to\mathbb{N}$ memberi injeksi $(a,b)\mapsto\pi(\alpha(a),\beta(b))$ dari $A\times B$ ke $\mathbb{N}$. Lalu gunakan Teorema 21.1.3. Bila keduanya tak hingga, $A\times B$ memuat $A\times\{b_0\}$, yang tak hingga, sehingga $A\times B$ tak hingga. $\square$

Bilangan Rasional

Teorema 21.2.6

$\mathbb{Q}$ terhitung tak hingga.

Bukti. Setiap $r\in\mathbb{Q}$ mempunyai wakil tunggal $r=\tfrac pq$ dengan $p\in\mathbb{Z}$ dan $q\in\mathbb{N}_{+}$ terkecil (Lema 8.4.6). Ketunggalan: penyebut positif terkecil tunggal, dan pembilang ditentukan oleh $p=rq$. Fungsi $r\mapsto(p,q)$ injektif dari $\mathbb{Q}$ ke $\mathbb{Z}\times\mathbb{N}_{+}$, yang terhitung menurut Teorema 21.2.1 dan Akibat 21.2.5. Teorema 21.1.3 memberi bahwa $\mathbb{Q}$ terhitung. $\mathbb{Q}\supseteq\mathbb{N}$ tak hingga (Solusi 20.1-7). $\square$

Bukti di atas memakai injeksi ke tabel. Versi Cantor yang klasik memakai surjeksi: daftarkan pecahan positif $\tfrac pq$ dengan $p,q\geq1$ menurut antidiagonal $p+q=2,3,4,\ldots$:

$$\tfrac11;\ \tfrac12,\tfrac21;\ \tfrac13,\tfrac22,\tfrac31;\ \tfrac14,\tfrac23,\tfrac32,\tfrac41;\ \ldots$$

Daftar ini memuat setiap rasional positif, dengan pengulangan, misalnya $\tfrac22=\tfrac11$. Teorema 21.1.3(c) menyatakan bahwa daftar dengan pengulangan sudah cukup. Membuang pengulangan memberi pencacahan tanpa pengulangan, tetapi langkah itu tidak diperlukan untuk menyimpulkan keterhitungan.

Contoh 21.2.7 (Lima Rasional Positif Pertama)

Dengan membuang pengulangan dari daftar antidiagonal: $q_0=1$, $q_1=\tfrac12$, $q_2=2$, $q_3=\tfrac13$, $q_4=3$. Pecahan $\tfrac22$ dilewati. Lalu $\tfrac14,\tfrac23,\tfrac32,4,\ldots$.

Kerapatan dan Keterhitungan

$\mathbb{Q}$ rapat di $\mathbb{R}$ dan terhitung. Akibatnya, dua sifat "besar" ini independen: kerapatan tidak mengakibatkan ketakterhitungan. Sebaliknya, Bab 22 akan menunjukkan bahwa setiap interval tak degenerat tak terhitung. Jadi $\mathbb{Q}\cap(0,1)$, walaupun rapat di $(0,1)$, hanya mengisi bagian yang "dapat diabaikan" dari interval itu dalam arti kardinalitas. Bilangan irasional di $(0,1)$ tidak terhitung, karena gabungan dua himpunan terhitung terhitung (Unit 21.3).

Latihan

Latihan 21.2-1. Hitung $z(0),\ldots,z(6)$ pada Teorema 21.2.1 dan tentukan $z^{-1}(-4)$ serta $z^{-1}(4)$.

Latihan 21.2-2. Buktikan bahwa $T(k)=1+2+\cdots+k$ untuk $k\geq1$, dan bahwa $T(k)$ bilangan asli.

Latihan 21.2-3. Hitung $\pi(3,2)$ dan $\pi(0,5)$. Tentukan $(m,n)$ dengan $\pi(m,n)=12$ menurut langkah bukti surjektivitas.

Latihan 21.2-4. Buktikan bahwa $\mathbb{N}\times\mathbb{N}\times\mathbb{N}$ terhitung tak hingga dengan menyusun dua fungsi pasangan.

Latihan 21.2-5. Buktikan bahwa $\mathbb{Z}\times\mathbb{Z}$ terhitung tak hingga.

Latihan 21.2-6. Tuliskan sepuluh rasional positif pertama dalam daftar antidiagonal tanpa pengulangan.

Latihan 21.2-7. Buktikan bahwa himpunan semua interval $(a,b)$ dengan $a,b\in\mathbb{Q}$ dan $a<b$ terhitung.

Latihan 21.2-8. Buktikan bahwa setiap himpunan $\mathcal{S}$ yang terdiri atas interval-interval buka tak kosong dan saling lepas di $\mathbb{R}$ adalah terhitung. Petunjuk: pilih rasional dalam setiap interval secara tertentu, tanpa aksioma pilihan.

Solusi

Solusi 21.2-1. $z(0..6)=0,-1,1,-2,2,-3,3$. $z^{-1}(-4)=7$ dan $z^{-1}(4)=8$. $\square$

Solusi 21.2-2. Induksi: $T(1)=1$, dan $T(k+1)=T(k)+k+1$ (Lemma 21.2.3(a)). Bilangan asli: $k(k+1)$ genap karena salah satu dari $k$, $k+1$ genap (pembagian Euclid oleh $2$), sehingga $\tfrac{k(k+1)}2\in\mathbb{N}$. $\square$

Solusi 21.2-3. $\pi(3,2)=T(5)+2=15+2=17$. $\pi(0,5)=T(5)+5=20$. Untuk $N=12$: $T(4)=10\leq12<15=T(5)$, sehingga $k=4$, $n=2$, $m=2$. Periksa: $\pi(2,2)=10+2=12$. $\square$

Solusi 21.2-4. $(a,b,c)\mapsto\pi(\pi(a,b),c)$ adalah komposisi bijeksi $\mathbb{N}^3\to\mathbb{N}^2\to\mathbb{N}$, dengan langkah pertama $(a,b,c)\mapsto(\pi(a,b),c)$. $\square$

Solusi 21.2-5. Akibat 21.2.5 dengan $A=B=\mathbb{Z}$ (Teorema 21.2.1). $\square$

Solusi 21.2-6. $1,\tfrac12,2,\tfrac13,3,\tfrac14,\tfrac23,\tfrac32,4,\tfrac15$. Antidiagonal $p+q=6$ memberi $\tfrac15,\tfrac24,\tfrac33,\tfrac42,\tfrac51$; yang pertama baru, sedangkan $\tfrac24=\tfrac12$ dan $\tfrac33=1$ adalah pengulangan. $\square$

Solusi 21.2-7. $(a,b)\mapsto$ pasangan $(a,b)\in\mathbb{Q}^2$ injektif, dari himpunan interval ke $\mathbb{Q}\times\mathbb{Q}$, yang terhitung (Akibat 21.2.5). Interval ditentukan oleh ujungnya, karena $a=\inf$ dan $b=\sup$ (Bab 12). $\square$

Solusi 21.2-8. Pencacahan $(q_k)$ dari $\mathbb{Q}$ (Teorema 21.2.6) tetap. Untuk setiap $I\in\mathcal{S}$, $I\cap\mathbb{Q}\ne\emptyset$ (kerapatan). Definisikan $\phi(I)=\min\{k:q_k\in I\}$, dengan minimum yang ada menurut urutan baik. Jika $\phi(I)=\phi(J)$, maka $q_{\phi(I)}\in I\cap J$, sehingga $I=J$ karena interval-intervalnya saling lepas. Jadi $\phi:\mathcal{S}\to\mathbb{N}$ injektif. Tidak ada pilihan sebarang: pencacahan tertentu dan minimum menentukan $\phi$. $\square$

Ringkasan

$\mathbb{Z}$ terhitung tak hingga lewat pencacahan zig-zag. $\mathbb{N}\times\mathbb{N}$ terhitung tak hingga lewat fungsi pasangan Cantor, yang mendaftar tabel menurut antidiagonal, dengan bukti bijektif lengkap memakai bilangan segitiga. Hasil kali himpunan terhitung terhitung. $\mathbb{Q}$ terhitung tak hingga, lewat wakil tereduksi atau lewat daftar diagonal Cantor dengan pengulangan. Kerapatan tidak mengakibatkan ketakterhitungan. Unit 21.3 membahas gabungan terhitung dari himpunan terhitung, termasuk peran aksioma pilihan di sana.

21.3 Gabungan Terhitung dari Himpunan Terhitung

Gabungan berhingga himpunan hingga adalah hingga (Teorema 20.1.9). Unit ini membahas pernyataan sejajar untuk himpunan terhitung: gabungan dua himpunan terhitung terhitung, gabungan berhingga terhitung, dan gabungan terhitung dari himpunan-himpunan terhitung juga terhitung. Bentuk terakhir adalah alat yang sangat sering dipakai dalam analisis.

Pernyataan terakhir itu mempunyai kehalusan yang sering terlewat. Buktinya menjajarkan himpunan-himpunan itu dalam tabel $\mathbb{N}\times\mathbb{N}$ dan menyusurinya dengan diagonal Cantor (Unit 21.2). Langkah itu mudah bila setiap himpunan sudah dilengkapi pencacahan tertentu. Bila yang diketahui hanya bahwa setiap himpunan dapat dicacah, kita harus memilih satu pencacahan untuk setiap himpunan sekaligus, dan langkah itu memerlukan aksioma pilihan terhitung. Unit ini memisahkan kedua situasi itu dengan tegas.

Prasyarat: Unit 21.1–21.2 (Teorema 21.1.3, 21.2.4, 21.2.6); Bab 20; fungsi dan keluarga berindeks (Bab 3, 5).

Gabungan Dua dan Berhingga Banyak

Teorema 21.3.1 (Gabungan Dua Himpunan Terhitung)

Jika $A$ dan $B$ terhitung, maka $A\cup B$ terhitung.

Bukti. Bila salah satunya kosong, selesai. Bila keduanya tak kosong, ambil surjeksi $h_A,h_B:\mathbb{N}\to A,B$ (Teorema 21.1.3(c)). Definisikan $h(2n)=h_A(n)$ dan $h(2n+1)=h_B(n)$. Setiap bilangan asli adalah genap atau ganjil secara tunggal (pembagian Euclid), sehingga $h$ terdefinisi. $h:\mathbb{N}\to A\cup B$ surjektif. $\square$

Bukti ini memilih dua surjeksi. Dua pilihan, atau berhingga banyak pilihan, tidak memerlukan aksioma pilihan: masing-masing adalah eliminasi eksistensial biasa.

Akibat 21.3.2

Untuk $k\in\mathbb{N}_{+}$, gabungan $A_1\cup\cdots\cup A_k$ dari himpunan-himpunan terhitung adalah terhitung.

Bukti. Induksi pada $k$ dengan Teorema 21.3.1. $\square$

Contohnya, $\mathbb{R}\setminus\mathbb{Q}$ tidak terhitung asalkan $\mathbb{R}$ tidak terhitung. Seandainya terhitung, $\mathbb{R}=\mathbb{Q}\cup(\mathbb{R}\setminus\mathbb{Q})$ akan terhitung. Bab 22 membuktikan bahwa $\mathbb{R}$ tidak terhitung.

Gabungan Terhitung dengan Pencacahan yang Diberikan

Teorema 21.3.3 (Gabungan Terhitung yang Tercacah)

Misalkan $(A_n)_{n\in\mathbb{N}}$ keluarga himpunan, dan $I=\{n\in\mathbb{N}:A_n\ne\emptyset\}$. Misalkan diberikan satu fungsi $H:I\times\mathbb{N}\to\bigcup_{n\in\mathbb{N}}A_n$ sehingga untuk setiap $n\in I$, fungsi $k\mapsto H(n,k)$ adalah surjeksi $\mathbb{N}\to A_n$. Maka $\bigcup_{n\in\mathbb{N}}A_n$ terhitung. Khususnya, bila $A_n\ne\emptyset$ untuk semua $n$, maka $I=\mathbb{N}$ dan $H$ terdefinisi pada $\mathbb{N}\times\mathbb{N}$.

Bukti. Bila $I=\emptyset$, setiap $A_n$ kosong, sehingga $\bigcup_nA_n=\emptyset$, yang hingga dan karena itu terhitung. Misalkan $I\ne\emptyset$. Domain $I\times\mathbb{N}$ adalah subhimpunan $\mathbb{N}\times\mathbb{N}$, yang terhitung (Teorema 21.2.4), sehingga $I\times\mathbb{N}$ terhitung (Akibat 21.1.4(a)).

$H$ surjektif ke $\bigcup_nA_n$. Bila $x\in\bigcup_nA_n$, maka $x\in A_n$ untuk suatu $n$. Himpunan $A_n$ itu tak kosong, sehingga $n\in I$. Karena $H(n,\cdot)$ surjeksi ke $A_n$, ada $k$ dengan $H(n,k)=x$. Jadi $\bigcup_nA_n=H[I\times\mathbb{N}]$ adalah peta himpunan terhitung, sehingga terhitung (Akibat 21.1.4(b)).

Surjeksinya juga dapat ditulis eksplisit. Dengan $\pi$ fungsi pasangan Cantor (Teorema 21.2.4) dan $n_0=\min I$ (urutan baik), tetapkan $e(j)=\pi^{-1}(j)$ bila $\pi^{-1}(j)\in I\times\mathbb{N}$, dan $e(j)=(n_0,0)$ bila tidak. Maka $e:\mathbb{N}\to I\times\mathbb{N}$ surjektif, karena $(n,k)=e(\pi(n,k))$, dan $H\circ e:\mathbb{N}\to\bigcup_nA_n$ surjektif. Tidak ada fungsi yang perlu didefinisikan pada indeks kosong, dan tidak diperlukan surjeksi ke $\emptyset$. $\square$

Data "$H$ diberikan" adalah satu objek, yaitu satu fungsi, bukan tak hingga banyak pilihan yang dibuat satu per satu. Karena itu teorema ini tidak memerlukan aksioma pilihan.

Himpunan kosong ditangani oleh domain $I\times\mathbb{N}$. Untuk $n\notin I$, tidak ada surjeksi $\mathbb{N}\to A_n=\emptyset$, dan teorema memang tidak memintanya: $H$ hanya didefinisikan pada indeks $n$ dengan $A_n$ tak kosong. Indeks kosong tidak menyumbang anggota apa pun pada gabungan.

Contoh 21.3.4 (Penerapan Tanpa Pilihan)

(a) $\mathbb{Q}=\bigcup_{q\in\mathbb{N}}A_q$, dengan $A_0=\emptyset$ dan $A_q=\{\tfrac pq:p\in\mathbb{Z}\}$ untuk $q\geq1$. Di sini $I=\mathbb{N}_{+}$, dan $H(q,k)=\tfrac{z(k)}q$ untuk $(q,k)\in I\times\mathbb{N}$, dengan $z$ dari Teorema 21.2.1. Ini bukti kedua untuk Teorema 21.2.6.

(b) Himpunan semua polinomial berkoefisien bulat (Definisi 16.1.1 dengan koefisien di $\mathbb{Z}$) terhitung, dengan pencacahan yang dibangun secara eksplisit sebagai berikut.

Langkah 1: daftar bilangan asli. Tetapkan $\beta_1(k)=(k)$. Untuk $\ell\geq1$, bila $(a,b)=\pi^{-1}(k)$, tetapkan $\beta_{\ell+1}(k)=(\beta_\ell(a),b)$, yaitu daftar $\beta_\ell(a)$ yang ditambah koordinat terakhir $b$. Rekursi pada $\ell$ (Teorema 7.4.1) menentukan seluruh keluarga $(\beta_\ell)_{\ell\geq1}$ sekaligus, tanpa memilih pencacahan baru untuk setiap panjang. Rekursi yang sama dipakai pada Solusi 21.3-5. Setiap $\beta_\ell:\mathbb{N}\to\mathbb{N}^\ell$ bijektif, menurut induksi pada $\ell$. Untuk $\ell=1$ jelas. Bila $\beta_\ell$ bijektif, maka $\beta_{\ell+1}$ mempunyai invers

$$(u_1,\ldots,u_{\ell+1})\mapsto\pi\bigl(\beta_\ell^{-1}(u_1,\ldots,u_\ell),\,u_{\ell+1}\bigr):$$

invers $\beta_\ell$ diterapkan pada $\ell$ koordinat pertama, lalu $\pi$ (Teorema 21.2.4) memasangkan hasilnya dengan koordinat terakhir. Kedua komposisi adalah identitas, karena $\pi$ dan $\pi^{-1}$ saling invers, dan demikian pula $\beta_\ell$ dan $\beta_\ell^{-1}$.

Langkah 2: daftar koefisien. Untuk $d,k\in\mathbb{N}$, tulis $(u_0,\ldots,u_d)=\beta_{d+1}(k)$ dan tetapkan

$$C(d,k)=\bigl(z(u_0),\ldots,z(u_d)\bigr)\in\mathbb{Z}^{d+1},\qquad P_{d,k}(X)=\sum_{i=0}^dz(u_i)X^i,$$

dengan $z:\mathbb{N}\to\mathbb{Z}$ bijeksi Teorema 21.2.1. Untuk $m\in\mathbb{N}$ dengan $(d,k)=\pi^{-1}(m)$, tetapkan $P_m=P_{d,k}$.

Langkah 3: setiap polinomial muncul. Misalkan $p(X)=\sum_{i=0}^da_iX^i$ dengan $d\in\mathbb{N}$ dan $a_i\in\mathbb{Z}$. Tetapkan $u_i=z^{-1}(a_i)$, $k=\beta_{d+1}^{-1}(u_0,\ldots,u_d)$, dan $m=\pi(d,k)$. Maka $C(d,k)=(a_0,\ldots,a_d)$ dan $P_m=p$. Jadi $m\mapsto P_m$ adalah surjeksi dari $\mathbb{N}$ ke himpunan polinomial berkoefisien bulat, dan Teorema 21.1.3(c) memberi keterhitungan. Tidak ada pilihan: setiap langkah adalah fungsi yang ditentukan rumus atau rekursi.

Pencacahan ini tidak injektif, dan itu tidak menjadi masalah. Polinomial $X^2-2$ muncul dari daftar koefisien $(-2,0,1)$ dan juga dari daftar $(-2,0,1,0)$, yang memuat koefisien nol tambahan, pada indeks $m$ yang berbeda. Kedua daftar mendefinisikan fungsi yang sama. Polinomial nol juga muncul, misalnya dari daftar $(0)$, dan harus dikeluarkan pada (c).

(c) Bilangan aljabar real, yaitu bilangan real yang merupakan pembuat nol suatu polinomial berkoefisien bulat yang bukan polinomial nol, membentuk himpunan terhitung $\mathcal{A}$. Konstruksinya memakai pencacahan $(P_m)$ dari (b).

Langkah 1: himpunan akar. Untuk $m$ dengan $P_m$ bukan polinomial nol, yaitu bukan fungsi nol (menurut Akibat 16.1.4, setara dengan: ada koefisien tak nol), tetapkan $R_m=\{x\in\mathbb{R}:P_m(x)=0\}$. Himpunan ini hingga. Bila $P_m$ berderajat $n\geq0$, Akibat 16.1.3 memberi paling banyak $n$ anggota; khususnya, konstanta tak nol memberi $R_m=\emptyset$. Tulis $r_m=|R_m|$. Bila $r_m>0$, susun $R_m$ secara naik: $\alpha_{m,0}<\alpha_{m,1}<\cdots<\alpha_{m,r_m-1}$. Susunan naik ini tunggal: $\alpha_{m,0}=\min R_m$ (Teorema 11.1.14), $\alpha_{m,1}$ adalah minimum dari sisanya, dan seterusnya, dengan rekursi sepanjang $r_m$ langkah. Ini daftar akar real yang berbeda, bukan akar yang dihitung menurut kelipatannya. Penyusunan itu adalah definisi matematis yang tunggal, bukan klaim tentang algoritma numerik atau rumus akar. Untuk polinomial nol, $R_m=\mathbb{R}$ tidak hingga, sehingga $r_m$ tidak didefinisikan; polinomial nol dikeluarkan pada langkah berikut.

Langkah 2: domain dan fungsi. Tetapkan

$$D=\{(m,j)\in\mathbb{N}^2:\ P_m\text{ bukan polinomial nol dan }0\leq j<r_m\},\qquad F:D\to\mathbb{R},\quad F(m,j)=\alpha_{m,j}.$$

Syarat pada $D$ hanya menyentuh $r_m$ bila $P_m$ bukan polinomial nol, sehingga tidak ada simbol yang tak terdefinisi. $D\subseteq\mathbb{N}^2$ terhitung (Teorema 21.2.4, Akibat 21.1.4(a)). Polinomial tanpa akar real menyumbang nol pasangan.

Langkah 3: $F[D]=\mathcal{A}$. ($\subseteq$) $F(m,j)=\alpha_{m,j}\in R_m$ adalah pembuat nol polinomial bulat $P_m$ yang bukan polinomial nol. ($\supseteq$) Bila $x\in\mathcal{A}$, ada polinomial bulat $p$ yang bukan polinomial nol dengan $p(x)=0$. Menurut (b), $p=P_m$ untuk suatu $m$. Maka $x\in R_m$, sehingga $r_m>0$ dan $x=\alpha_{m,j}$ untuk tepat satu $j<r_m$. Jadi $(m,j)\in D$ dan $F(m,j)=x$. Akibatnya $\mathcal{A}$ adalah peta himpunan terhitung, sehingga terhitung (Akibat 21.1.4(b)). Tidak ada pemilihan akar yang sebarang; urutan bilangan real menentukan semuanya.

Contoh yang dikerjakan:

• $X^2-2$: $x^2=2$ tepat untuk $x=\pm\sqrt2$ (Teorema 11.3.8 dan $(-x)^2=x^2$), sehingga $r_m=2$, dengan $\alpha_{m,0}=-\sqrt2$ dan $\alpha_{m,1}=\sqrt2$.
• $X^2+1$: $x^2+1\geq1>0$ untuk semua $x$, sehingga $r_m=0$, dan polinomial ini tidak menyumbang pasangan.
• $(X-1)^2=X^2-2X+1$: hanya $x=1$ yang memenuhi, karena $(x-1)^2=0$ memaksa $x-1=0$ (tanpa pembagi nol). Jadi $r_m=1$, walaupun $1$ adalah akar berkelipatan dua.
• $2X^2-4$ adalah polinomial yang berbeda dari $X^2-2$ dan muncul pada indeks lain, tetapi himpunan akarnya sama. Begitu pula $X^2-2$ yang ditulis dengan koefisien nol tambahan. Bilangan $\pm\sqrt2$ muncul sebagai nilai $F$ lebih dari sekali. $F$ tidak injektif, tetapi tetap surjektif ke $\mathcal{A}$, dan itu cukup.
• Polinomial nol dikeluarkan, karena himpunan akarnya adalah seluruh $\mathbb{R}$.

Akibatnya, bersyarat pada ketakterhitungan $\mathbb{R}$ yang dibuktikan di Bab 22, ada bilangan real yang bukan aljabar (bilangan transenden). Ketergantungan pada Bab 22 itu tidak diaudit ulang di sini. Ini argumen keberadaan Cantor, yang tidak menunjukkan satu pun bilangan transenden secara eksplisit.

Peran Aksioma Pilihan

Teorema 21.3.5 (Bentuk Umum, dengan Pilihan Terhitung)

Dengan aksioma pilihan terhitung (dirumuskan pada Bab 23.3): jika setiap $A_n$, $n\in\mathbb{N}$, terhitung, maka $\bigcup_nA_n$ terhitung.

Bukti, dengan asumsi aksioma yang disebut. Tetapkan $I=\{n\in\mathbb{N}:A_n\ne\emptyset\}$. Bila $I=\emptyset$, gabungannya kosong, dan tidak ada yang perlu dipilih. Misalkan $I\ne\emptyset$. Untuk $n\in I$, himpunan $S_n$ yang berisi semua surjeksi $\mathbb{N}\to A_n$ (subhimpunan himpunan semua fungsi $\mathbb{N}\to A_n$, menurut separasi) tidak kosong, karena $A_n$ terhitung dan tak kosong (Teorema 21.1.3(c)).

Aksioma pilihan terhitung (Aksioma 23.3.3) dirumuskan untuk barisan himpunan berindeks $\mathbb{N}$. Agar aksioma itu dapat dipakai, tetapkan $T_n=S_n$ bila $n\in I$, dan $T_n=\{\emptyset\}$ bila $n\notin I$. Di sini $\emptyset$ hanyalah fungsi kosong yang dipakai sebagai penanda. Semua $T_n$ tak kosong, dan penetapan ini tertentu, tanpa pilihan. Aksioma pilihan terhitung memberi barisan $(t_n)$ dengan $t_n\in T_n$. Batasi barisan itu pada $I$: untuk $n\in I$, $h_n=t_n$ adalah surjeksi $\mathbb{N}\to A_n$. Tetapkan $H:I\times\mathbb{N}\to\bigcup_nA_n$, $H(n,k)=h_n(k)$. Teorema 21.3.3 memberi keterhitungan.

Pilihan terhitung hanya dipakai untuk memperoleh keluarga $(h_n)_{n\in I}$ sekaligus. Teorema 21.3.3 sendiri, yang memberi kesimpulan, tidak memakai pilihan. $\square$

Fakta metamatematika berikut dicatat tanpa bukti, karena buktinya memakai konstruksi model teori himpunan di luar cakupan buku. Tanpa aksioma pilihan terhitung, Teorema 21.3.5 tidak dapat dibuktikan di ZF. Feferman dan Lévy (1963) menunjukkan bahwa, bila ZF konsisten, ZF tetap konsisten dengan pernyataan bahwa himpunan bilangan real adalah gabungan terhitung himpunan-himpunan terhitung. Dalam model itu $\mathbb{R}$ tetap tak terhitung, karena argumen diagonal Cantor (Bab 22) tidak memerlukan pilihan. Jadi yang gagal adalah Teorema 21.3.5, bukan Bab 22.

Sumber:

• Open Logic Project, Countable Choice: https://builds.openlogicproject.org/content/set-theory/choice/countablechoice.pdf
• A. Miller, A Dedekind Finite Borel Set: https://people.math.wisc.edu/~awmille1/res/ded.pdf. Paper ini menyebut hasil Feferman–Lévy dan merujuk pada T. Jech, Set Theory.

Keduanya diakses 2 Oktober 2026. Klaim di atas dibatasi pada isi yang dinyatakan sumber tersebut.

Kebijakan buku: setiap pemakaian gabungan terhitung pada bab-bab selanjutnya akan menyebut apakah pencacahannya diberikan (Teorema 21.3.3, tanpa pilihan) atau dipilih (Teorema 21.3.5, dengan pilihan terhitung). Pada analisis bilangan real, pencacahan hampir selalu dapat dibuat eksplisit, seperti Contoh 21.3.4.

Latihan

Latihan 21.3-1. Buktikan Teorema 21.3.1, lalu tuliskan $h(0),\ldots,h(5)$ untuk $A=\mathbb{N}$, $B=\{-1,-2,-3,\ldots\}$, dengan $h_A=\mathrm{id}$ dan $h_B(n)=-(n+1)$.

Latihan 21.3-2. Buktikan bahwa $\mathbb{Z}=\mathbb{N}\cup\{-n:n\in\mathbb{N}_{+}\}$ terhitung memakai Teorema 21.3.1, dan bandingkan dengan Teorema 21.2.1.

Latihan 21.3-3. Buktikan bahwa jika $\mathbb{R}$ tak terhitung, maka $\mathbb{R}\setminus\mathbb{Q}$ tak terhitung.

Latihan 21.3-4. Buktikan bahwa $\bigcup_{n\in\mathbb{N}}\{n\}\times\mathbb{N}=\mathbb{N}\times\mathbb{N}$ terhitung dengan Teorema 21.3.3, dan tuliskan fungsi $H$-nya.

Latihan 21.3-5. Buktikan bahwa himpunan semua barisan hingga (daftar panjang berhingga) bilangan asli adalah terhitung, dengan pencacahan yang diberikan tanpa pilihan.

Latihan 21.3-6. Buktikan bahwa himpunan semua subhimpunan hingga dari $\mathbb{N}$ adalah terhitung.

Latihan 21.3-7. Jelaskan dengan tepat langkah mana pada bukti Teorema 21.3.5 yang memerlukan aksioma pilihan terhitung, dan mengapa langkah sejajar pada Teorema 21.3.1 tidak memerlukannya.

Latihan 21.3-8. Buktikan bahwa himpunan semua bilangan real $x$ yang memenuhi persamaan $x^2=q$ untuk suatu $q\in\mathbb{Q}$ adalah terhitung, dengan pencacahan eksplisit.

Solusi

Solusi 21.3-1. Lihat bukti Teorema 21.3.1. $h(0)=0$, $h(1)=-1$, $h(2)=1$, $h(3)=-2$, $h(4)=2$, $h(5)=-3$. $\square$

Solusi 21.3-2. $\mathbb{N}$ terhitung, dan $\{-n:n\geq1\}$ terhitung lewat $n\mapsto-(n+1)$. Teorema 21.3.1 memberi $\mathbb{Z}$ terhitung. Surjeksinya sama dengan pencacahan Teorema 21.2.1 dengan urutan berbeda. $\square$

Solusi 21.3-3. Bila $\mathbb{R}\setminus\mathbb{Q}$ terhitung, maka $\mathbb{R}=\mathbb{Q}\cup(\mathbb{R}\setminus\mathbb{Q})$ terhitung menurut Teorema 21.3.1 dan 21.2.6. $\square$

Solusi 21.3-4. $A_n=\{n\}\times\mathbb{N}$ dengan $H(n,k)=(n,k)$. Gabungannya $\mathbb{N}\times\mathbb{N}$. $H\circ\pi^{-1}$ di sini adalah $\pi^{-1}$ sendiri. $\square$

Solusi 21.3-5. Barisan panjang $\ell$ adalah anggota $\mathbb{N}^\ell$. Untuk $\ell\geq1$, ada bijeksi eksplisit $\beta_\ell:\mathbb{N}\to\mathbb{N}^\ell$, dibangun secara rekursif dari $\pi^{-1}$: $\beta_1(k)=(k)$ dan $\beta_{\ell+1}(k)=(\beta_\ell(a),b)$ dengan $(a,b)=\pi^{-1}(k)$. Untuk $\ell=0$, hanya barisan kosong. Tetapkan $H(\ell,k)=\beta_\ell(k)$ untuk $\ell\geq1$ dan $H(0,k)=()$. Teorema 21.3.3 memberi keterhitungan. Rekursi pada $\ell$ menentukan semua $\beta_\ell$ sekaligus (Teorema 7.4.1), tanpa pilihan. $\square$

Solusi 21.3-6. Subhimpunan hingga $F\subseteq\mathbb{N}$ dengan $|F|=\ell$ ditentukan oleh daftar naiknya $(f_1<\cdots<f_\ell)$, yaitu barisan hingga bilangan asli. Pemetaan $F\mapsto$ daftar naik adalah injeksi ke himpunan pada Latihan 21.3-5, yang terhitung. Daftar naik tertentu karena $F$ terurut baik. $\square$

Solusi 21.3-7. Pada Teorema 21.3.5, untuk setiap $n\in I=\{n:A_n\ne\emptyset\}$, yang dapat memuat tak hingga banyak indeks, harus dipilih satu surjeksi $h_n$ dari himpunan $S_n$ yang tak kosong, tanpa aturan yang memilihnya. Untuk $A_n$ kosong tidak ada surjeksi dan tidak ada yang dipilih; penanda $T_n=\{\emptyset\}$ hanya membuat barisan himpunan berindeks $\mathbb{N}$. Membuat tak hingga banyak pilihan sekaligus adalah isi aksioma pilihan terhitung. Pada Teorema 21.3.1, hanya dua pilihan dibuat, masing-masing dengan eliminasi eksistensial biasa, sehingga tidak diperlukan aksioma. $\square$

Solusi 21.3-8. Untuk $q\geq0$, solusinya $\pm\sqrt q$; untuk $q<0$, tidak ada. Dengan pencacahan $(q_k)$ dari $\mathbb{Q}$ (Teorema 21.2.6), tetapkan $H(k,0)=\sqrt{\max(q_k,0)}$ dan $H(k,1)=-\sqrt{\max(q_k,0)}$, lalu $H(k,j)=H(k,0)$ untuk $j\geq2$. Fungsi $(k,j)\mapsto H(k,j)$ dengan $j\in\{0,1\}$ surjektif ke himpunan solusi ditambah $\{0\}$, karena $q_k<0$ menghasilkan $0$. Himpunan solusi memuat $0$ (dari $q=0$). Jadi $H\circ\pi^{-1}$ adalah surjeksi $\mathbb{N}\to$ himpunan solusi, tanpa pilihan. $\square$

Ringkasan Unit 21.3 dan Penutup Bab 21

Gabungan berhingga himpunan terhitung adalah terhitung tanpa aksioma pilihan. Gabungan terhitung himpunan terhitung adalah terhitung bila pencacahannya diberikan sebagai satu fungsi, yaitu kasus yang hampir selalu terjadi di analisis (contoh: $\mathbb{Q}$, polinomial bulat, bilangan aljabar). Dalam bentuk umum, pernyataan itu memerlukan pilihan terhitung; tanpa pilihan, pernyataan itu tidak dapat dibuktikan di ZF (Feferman–Lévy). Keterhitungan bilangan aljabar, bersama ketakterhitungan $\mathbb{R}$ pada Bab 22, menjamin adanya bilangan transenden.

Bab 21 secara keseluruhan:

• 21.1: terhitung dan terhitung tak hingga;
• 21.2: $\mathbb{Z}$, $\mathbb{N}^2$, dan $\mathbb{Q}$ lewat diagonal Cantor;
• 21.3: gabungan.

Bab 22 menunjukkan bahwa tidak semua himpunan tak hingga terhitung.