Bab 23: Bilangan Kardinal dan Aksioma Pilihan

23.1 Kesetaraan Kardinalitas (Equinumerosity)

Bab 20–22 membandingkan ukuran himpunan dengan fungsi: bijeksi untuk "sama besar", injeksi untuk "tidak lebih besar". Bab 23 menata perbandingan itu menjadi teori. Unit ini mendefinisikan kesetaraan kardinalitas dan urutan kardinalitas, membuktikan sifat-sifat dasarnya, dan menunjukkan bahwa keduanya menghormati operasi himpunan (hasil kali, gabungan saling lepas, himpunan kuasa, himpunan fungsi). Unit 23.2 membuktikan antisimetri urutan itu (Schröder–Bernstein), dan Unit 23.3 membahas aksioma pilihan, yang diperlukan untuk membandingkan sebarang dua himpunan.

Prasyarat: fungsi, komposisi, invers (Bab 5); relasi ekuivalensi dan urutan (Bab 4); Bab 20–22.

Definisi

Definisi 23.1.1 (Setara, Tidak Lebih Besar, Lebih Kecil)

Untuk himpunan $A$ dan $B$:

(a) $A$ setara dengan $B$, ditulis $A\approx B$ atau $|A|=|B|$, jika terdapat bijeksi $A\to B$;

(b) $A$ tidak lebih besar daripada $B$, ditulis $A\preceq B$ atau $|A|\leq|B|$, jika terdapat injeksi $A\to B$;

(c) $A$ lebih kecil daripada $B$, ditulis $A\prec B$ atau $|A|<|B|$, jika $A\preceq B$ dan tidak $A\approx B$.

Catatan tentang notasi. Tulisan $|A|=|B|$ di sini hanyalah singkatan untuk $A\approx B$. Kita tidak mendefinisikan "bilangan kardinal" $|A|$ sebagai objek tersendiri untuk himpunan tak hingga. Definisi semacam itu memerlukan perangkat teori himpunan yang lebih jauh, seperti ordinal dan, untuk kardinal sebarang, aksioma pilihan, dan tidak diperlukan di buku ini. Untuk himpunan hingga, $|A|$ tetap bilangan asli dari Definisi 20.1.6. Notasi baku untuk dua kelas penting: $\aleph_0$ ("alef nol") untuk kelas himpunan yang setara dengan $\mathbb{N}$, dan $\mathfrak{c}$ ("kontinum") untuk kelas yang setara dengan $\mathbb{R}$.

Proposisi 23.1.2 (Sifat Dasar)

Untuk himpunan $A,B,C$:

(a) $A\approx A$; jika $A\approx B$ maka $B\approx A$; jika $A\approx B$ dan $B\approx C$ maka $A\approx C$;

(b) $A\preceq A$; jika $A\preceq B$ dan $B\preceq C$ maka $A\preceq C$;

(c) jika $A\approx B$ maka $A\preceq B$ dan $B\preceq A$;

(d) jika $A\subseteq B$ maka $A\preceq B$;

(e) jika $A\approx A'$ dan $B\approx B'$, maka $A\preceq B\iff A'\preceq B'$.

Bukti. (a) Identitas, invers bijeksi, dan komposisi bijeksi (Bab 5). (b) Identitas dan komposisi injeksi. (c) Bijeksi dan inversnya adalah injeksi. (d) Inklusi adalah injeksi. (e) Untuk bijeksi $\alpha:A\to A'$ dan $\beta:B\to B'$ serta injeksi $f:A\to B$, komposisi $\beta\circ f\circ\alpha^{-1}$ adalah injeksi $A'\to B'$. Arah sebaliknya simetris. $\square$

Bagian (a) menyerupai sifat relasi ekuivalensi (Bab 4), dan bagian (b) menyerupai praurutan. Namun "semua himpunan" bukan himpunan (Unit 22.3), sehingga $\approx$ bukan relasi pada suatu himpunan dalam arti Bab 4. Sifat-sifat itu tetap berlaku untuk setiap keluarga himpunan yang sedang ditinjau. Bagian (e) menyatakan bahwa $\preceq$ hanya bergantung pada kelas kesetaraan, sehingga notasi $|A|\leq|B|$ konsisten.

Antisimetri, "$A\preceq B$ dan $B\preceq A$ mengakibatkan $A\approx B$", tidak jelas dari definisi. Antisimetri adalah Teorema Schröder–Bernstein (Unit 23.2).

Contoh

Contoh 23.1.3 (Kelas $\aleph_0$ dan $\mathfrak{c}$)

(a) $\mathbb{N}\approx\mathbb{Z}\approx\mathbb{Q}\approx\mathbb{N}\times\mathbb{N}$ (Teorema 21.2.1, 21.2.4, 21.2.6). Semuanya berkardinalitas $\aleph_0$.

(b) $\mathbb{R}\approx(-1,1)\approx(0,1)\approx(a,b)$ untuk $a<b$ (Proposisi 22.2.4). Semuanya berkardinalitas $\mathfrak{c}$.

(c) $\aleph_0<\mathfrak{c}$: $\mathbb{N}\subseteq\mathbb{R}$ memberi $\mathbb{N}\preceq\mathbb{R}$, dan tidak ada bijeksi karena $\mathbb{R}$ tak terhitung (Akibat 22.2.3).

(d) Untuk himpunan hingga: $A\approx B$ jika dan hanya jika $|A|=|B|$ sebagai bilangan asli (Akibat 20.1.5), dan $A\preceq B$ jika dan hanya jika $|A|\leq|B|$ (Teorema 20.1.4 dan arah sebaliknya dengan injeksi $[m]\subseteq[n]$).

Operasi Menghormati Kesetaraan

Teorema 23.1.4

Misalkan $A\approx A'$ lewat $\alpha$ dan $B\approx B'$ lewat $\beta$. Maka:

(a) $A\times B\approx A'\times B'$;

(b) jika $A\cap B=\emptyset$ dan $A'\cap B'=\emptyset$, maka $A\cup B\approx A'\cup B'$;

(c) $\mathcal{P}(A)\approx\mathcal{P}(A')$;

(d) $B^A\approx B'^{A'}$, dengan $B^A$ himpunan semua fungsi $A\to B$.

Bukti. (a) $(a,b)\mapsto(\alpha(a),\beta(b))$, dengan invers $(a',b')\mapsto(\alpha^{-1}(a'),\beta^{-1}(b'))$.

(b) $\alpha\cup\beta$, yaitu fungsi yang sama dengan $\alpha$ pada $A$ dan $\beta$ pada $B$, sah karena domainnya saling lepas, dan bijektif karena kodomainnya saling lepas.

(c) $S\mapsto\alpha[S]$, dengan invers $T\mapsto\alpha^{-1}[T]$. Peta maju dan peta balik bijeksi saling invers (Bab 5).

(d) $h\mapsto\beta\circ h\circ\alpha^{-1}$, dengan invers $k\mapsto\beta^{-1}\circ k\circ\alpha$. $\square$

Contoh 23.1.5 (Perhitungan Kardinal)

(a) $\{0,1\}^{A}\approx\mathcal{P}(A)$ untuk setiap $A$, lewat fungsi indikator. Bukti Proposisi 22.3.5(a) tidak memakai sifat khusus $\mathbb{N}$, sehingga berlaku kata demi kata untuk $A$ umum.

(b) $\mathbb{N}\times\mathbb{N}\approx\mathbb{N}$, sehingga dalam notasi kardinal $\aleph_0\cdot\aleph_0=\aleph_0$.

(c) $\{0,1\}^{\mathbb{N}}\times\{0,1\}^{\mathbb{N}}\approx\{0,1\}^{\mathbb{N}}$, lewat penyelang-nyelingan $(s,t)\mapsto u$ dengan $u_{2k}=s_k$ dan $u_{2k+1}=t_k$. Inversnya memisahkan indeks genap dan ganjil. Bersama Unit 23.2, yang memberi $\mathbb{R}\approx\{0,1\}^{\mathbb{N}}$, ini menghasilkan $\mathbb{R}\times\mathbb{R}\approx\mathbb{R}$: bidang tidak lebih "banyak" daripada garis.

Latihan

Latihan 23.1-1. Buktikan Proposisi 23.1.2(a) dan (b) secara rinci.

Latihan 23.1-2. Buktikan bahwa $\mathbb{N}\approx\{n\in\mathbb{N}:n\geq7\}$ dan $\mathbb{Z}\approx\{2n:n\in\mathbb{Z}\}$.

Latihan 23.1-3. Buktikan bahwa $A\preceq B$ dan $B\prec C$ mengakibatkan $A\prec C$. (Petunjuk: Anda mungkin memerlukan Unit 23.2; tunjukkan bagian yang tidak memerlukannya.)

Latihan 23.1-4. Buktikan Teorema 23.1.4(c) dan (d).

Latihan 23.1-5. Buktikan bahwa $\{0,1\}^{\mathbb{N}}\times\{0,1\}^{\mathbb{N}}\approx\{0,1\}^{\mathbb{N}}$ dengan penyelang-nyelingan, dan periksa bijektivitasnya.

Latihan 23.1-6. Buktikan bahwa untuk himpunan $A,B,C$ dengan $B\cap C=\emptyset$: $A^{B\cup C}\approx A^B\times A^C$.

Latihan 23.1-7. Buktikan bahwa $(A^B)^C\approx A^{B\times C}$.

Latihan 23.1-8. Buktikan bahwa $\mathbb{N}^{\mathbb{N}}\preceq\{0,1\}^{\mathbb{N}\times\mathbb{N}}\approx\{0,1\}^{\mathbb{N}}$.

Solusi

Solusi 23.1-1. (a) Identitas $\mathrm{id}_A$ bijeksi. Bila $f:A\to B$ bijeksi, $f^{-1}:B\to A$ bijeksi (Bab 5). Bila $f:A\to B$ dan $g:B\to C$ bijeksi, $g\circ f$ bijeksi, dengan invers $f^{-1}\circ g^{-1}$. (b) Sama untuk injeksi: komposisi injeksi injektif. $\square$

Solusi 23.1-2. $n\mapsto n+7$, dengan invers $m\mapsto m-7$. $n\mapsto2n$ dari $\mathbb{Z}$ ke bilangan genap, dengan invers $m\mapsto\tfrac m2$. $\square$

Solusi 23.1-3. $A\preceq C$: komposisi injeksi $A\to B\to C$. Untuk menunjukkan tidak $A\approx C$: andaikan $A\approx C$. Maka $C\preceq A\preceq B$, sehingga $C\preceq B$. Bersama $B\preceq C$, Teorema Schröder–Bernstein (Unit 23.2) memberi $B\approx C$, bertentangan dengan $B\prec C$. Bagian $A\preceq C$ tidak memerlukan Unit 23.2; bagian "tidak setara" memerlukannya. $\square$

Solusi 23.1-4. Lihat bukti Teorema 23.1.4. Untuk (c): $\alpha^{-1}[\alpha[S]]=S$ karena $\alpha$ injektif, dan $\alpha[\alpha^{-1}[T]]=T$ karena $\alpha$ surjektif. Untuk (d): $\beta^{-1}\circ(\beta\circ h\circ\alpha^{-1})\circ\alpha=h$, dan sebaliknya. $\square$

Solusi 23.1-5. Bijektif: inversnya $u\mapsto(s,t)$ dengan $s_k=u_{2k}$ dan $t_k=u_{2k+1}$. Setiap indeks $j\in\mathbb{N}$ genap atau ganjil secara tunggal (pembagian Euclid), sehingga kedua komposisi identitas. $\square$

Solusi 23.1-6. $h\mapsto(h|_B,h|_C)$, dengan invers $(f,g)\mapsto f\cup g$, yang sah karena $B\cap C=\emptyset$. $\square$

Solusi 23.1-7. $H\mapsto\tilde H$ dengan $\tilde H(b,c)=H(c)(b)$. Inversnya $K\mapsto(c\mapsto(b\mapsto K(b,c)))$. Ini pengkurian (currying). $\square$

Solusi 23.1-8. Kirim $s\in\mathbb{N}^{\mathbb{N}}$ ke indikator grafiknya, $\{(n,s(n)):n\in\mathbb{N}\}\subseteq\mathbb{N}\times\mathbb{N}$, dipandang sebagai fungsi $\mathbb{N}\times\mathbb{N}\to\{0,1\}$. Fungsi berbeda mempunyai grafik berbeda, sehingga pemetaan ini injeksi. Lalu $\{0,1\}^{\mathbb{N}\times\mathbb{N}}\approx\{0,1\}^{\mathbb{N}}$ menurut Teorema 23.1.4(d) dengan $\mathbb{N}\times\mathbb{N}\approx\mathbb{N}$. $\square$

Ringkasan

Kesetaraan kardinalitas ($\approx$, bijeksi) bersifat refleksif, simetris, dan transitif. Urutan kardinalitas ($\preceq$, injeksi) refleksif, transitif, dan hanya bergantung pada kelas kesetaraan. Keduanya dihormati oleh hasil kali, gabungan saling lepas, himpunan kuasa, dan himpunan fungsi. Notasi $|A|$ untuk himpunan tak hingga dipakai sebagai singkatan, bukan objek. Contoh pokoknya adalah kelas $\aleph_0$ dan $\mathfrak{c}$ dengan $\aleph_0<\mathfrak{c}$. Unit 23.2 membuktikan antisimetri: dua injeksi berlawanan arah menghasilkan bijeksi.

23.2 Teorema Schröder-Bernstein

Unit 23.1 mendefinisikan $A\preceq B$, yaitu adanya injeksi $A\to B$. Pertanyaan alaminya: jika $A\preceq B$ dan $B\preceq A$, apakah $A\approx B$? Untuk himpunan hingga, jawabannya mudah: $|A|\leq|B|\leq|A|$ sebagai bilangan asli (Teorema 20.1.4). Untuk himpunan tak hingga, kedua injeksi biasanya tidak surjektif. Misalnya, inklusi $(0,1)\to[0,1]$ melewatkan $0$ dan $1$, sedangkan $x\mapsto\tfrac{x+1}3$ dari $[0,1]$ ke $(0,1)$ melewatkan banyak titik. Tidak ada satu pun dari kedua injeksi itu yang bijeksi. Teorema Schröder–Bernstein menyatakan bahwa bijeksi tetap ada dan dapat dirakit dari potongan-potongan kedua injeksi.

Teorema ini adalah alat kerja utama teori kardinalitas. Untuk membuktikan $A\approx B$, cukup membuat dua injeksi, yang biasanya jauh lebih mudah daripada membuat bijeksi eksplisit. Buktinya tidak memakai aksioma pilihan.

Prasyarat: Unit 23.1; peta maju dan peta balik (Bab 5); himpunan kuasa dan separasi (Bab 3); Bab 22.

Lemma Titik Tetap

Lemma 23.2.1 (Titik Tetap Fungsi Monoton pada Himpunan Kuasa)

Misalkan $A$ himpunan dan $\varphi:\mathcal{P}(A)\to\mathcal{P}(A)$ monoton, yaitu $X\subseteq Y$ mengakibatkan $\varphi(X)\subseteq\varphi(Y)$. Tetapkan

Maka $\varphi(C)=C$.

Bukti. $\mathcal{S}$ adalah himpunan menurut separasi, dan $\emptyset\in\mathcal{S}$. $C\subseteq A$ karena setiap anggota $\mathcal{S}$ subhimpunan $A$.

$C\subseteq\varphi(C)$: ambil $a\in C$. Maka $a\in X$ untuk suatu $X\in\mathcal{S}$. Karena $X\subseteq C$, kemonotonan memberi $X\subseteq\varphi(X)\subseteq\varphi(C)$, sehingga $a\in\varphi(C)$.

$\varphi(C)\subseteq C$: dari $C\subseteq\varphi(C)$ dan kemonotonan, $\varphi(C)\subseteq\varphi(\varphi(C))$. Jadi $\varphi(C)\in\mathcal{S}$, sehingga $\varphi(C)\subseteq\bigcup\mathcal{S}=C$. $\square$

Lemma ini adalah kasus khusus teorema titik tetap Knaster–Tarski. $C$ adalah titik tetap terbesar: setiap titik tetap $X$ memenuhi $X\subseteq\varphi(X)$, sehingga $X\in\mathcal{S}$ dan $X\subseteq C$.

Teorema Utama

Teorema 23.2.2 (Schröder–Bernstein)

Jika $f:A\to B$ dan $g:B\to A$ injektif, maka terdapat bijeksi $h:A\to B$. Dengan kata lain, $A\preceq B$ dan $B\preceq A$ mengakibatkan $A\approx B$.

Bukti. Untuk $X\subseteq A$ tetapkan

Langkah 1: $\varphi$ monoton. Jika $X\subseteq Y$, maka $f[X]\subseteq f[Y]$, sehingga $B\setminus f[X]\supseteq B\setminus f[Y]$. Akibatnya $g[B\setminus f[X]]\supseteq g[B\setminus f[Y]]$, sehingga $\varphi(X)\subseteq\varphi(Y)$.

Langkah 2: titik tetap. Lemma 23.2.1 memberi $C\subseteq A$ dengan $\varphi(C)=C$, yaitu

Langkah 3: definisi $h$. Untuk $a\in A\setminus C$, persamaan di atas memberi $b\in B\setminus f[C]$ dengan $g(b)=a$. Karena $g$ injektif, $b$ tunggal. Tulis $b=g^{-1}(a)$. Tetapkan

Ini definisi tanpa pilihan, karena nilai pada kasus kedua tunggal.

Langkah 4: $h$ bijektif. Tulis $B_1=f[C]$ dan $B_2=B\setminus f[C]$. Keduanya saling lepas dan gabungannya $B$.

• $h|_C=f|_C$ adalah bijeksi $C\to B_1$: injektif karena $f$ injektif, dan surjektif ke $B_1$ menurut definisi peta.
• $h|_{A\setminus C}$ adalah bijeksi $A\setminus C\to B_2$. Pemetaan $g|_{B_2}:B_2\to A\setminus C$ injektif dan surjektif menurut Langkah 2, dan $h|_{A\setminus C}$ adalah inversnya.

Gabungan dua bijeksi dengan domain saling lepas ($C$ dan $A\setminus C$) dan kodomain saling lepas ($B_1$ dan $B_2$) adalah bijeksi $A\to B_1\cup B_2=B$, seperti dalam bukti Teorema 23.1.4(b). $\square$

Gambaran intuitifnya: $C$ adalah bagian $A$ yang "aman" dipetakan dengan $f$. Titik $a\in A\setminus C$ selalu merupakan peta $g$ dari titik $B$ yang tidak dicapai $f[C]$, sehingga titik itu dapat dikembalikan dengan $g^{-1}$. Persamaan titik tetap menjamin bahwa kedua bagian pas tanpa tumpang tindih dan tanpa celah.

Akibat 23.2.3 (Antisimetri dan Apitan)

(a) $A\preceq B$ dan $B\preceq A$ jika dan hanya jika $A\approx B$.

(b) Jika $A\subseteq B\subseteq C$ dan $A\approx C$, maka $B\approx C$, dan juga $A\approx B$.

(c) $A\prec B$ jika dan hanya jika $A\preceq B$ dan tidak $B\preceq A$.

Bukti. (a) Teorema 23.2.2 dan Proposisi 23.1.2(c).

(b) $B\preceq C$ lewat inklusi. Bijeksi $C\to A$ dirangkai dengan inklusi $A\subseteq B$ memberi $C\preceq B$. Gunakan (a). Lalu $A\approx C\approx B$.

(c) Jika $A\prec B$ dan $B\preceq A$, maka (a) memberi $A\approx B$, kontradiksi. Sebaliknya, jika $A\preceq B$ dan tidak $B\preceq A$, maka tidak $A\approx B$, karena $A\approx B$ akan memberi $B\preceq A$. $\square$

Akibat 23.2.3(a) melengkapi Proposisi 23.1.2. Relasi $\preceq$ kini refleksif, transitif, dan antisimetris "sampai kesetaraan". Satu-satunya sifat urutan linear yang belum ada adalah keterbandingan: untuk sebarang $A,B$, apakah selalu $A\preceq B$ atau $B\preceq A$? Unit 23.3 menunjukkan bahwa keterbandingan memerlukan aksioma pilihan.

Sejarah singkat: pernyataan ini dikemukakan oleh Cantor, dan bukti-bukti awal tanpa pilihan diberikan oleh Dedekind dan Bernstein pada akhir abad ke-19. Nama Schröder melekat karena ia menerbitkan bukti pada masa yang sama. Bukti melalui titik tetap di atas adalah versi modern yang ringkas.

Penerapan

Contoh 23.2.4 ($[0,1]\approx(0,1)$)

Dengan Schröder–Bernstein: inklusi $(0,1)\to[0,1]$ injektif, dan $x\mapsto\tfrac{x+1}3$ adalah injeksi $[0,1]\to[\tfrac13,\tfrac23]\subseteq(0,1)$. Jadi $[0,1]\approx(0,1)$.

Bijeksi eksplisit, untuk perbandingan, memakai gagasan "hotel Hilbert". Barisan $0,1,\tfrac12,\tfrac13,\tfrac14,\ldots$ di $[0,1]$ digeser dua langkah: $0\mapsto\tfrac12$, $1\mapsto\tfrac13$, dan $\tfrac1n\mapsto\tfrac1{n+2}$ untuk $n\geq2$. Titik lain tetap. Peta himpunan $\{0,1\}\cup\{\tfrac1n:n\geq2\}$ adalah $\{\tfrac1n:n\geq2\}$, secara bijektif, dan titik lain dipetakan ke dirinya sendiri, sehingga diperoleh bijeksi $[0,1]\to(0,1)$. Schröder–Bernstein menghindarkan kita dari menemukan konstruksi seperti ini.

Teorema 23.2.5 ($\mathfrak{c}=2^{\aleph_0}$)

$\mathbb{R}\approx\mathcal{P}(\mathbb{N})\approx\{0,1\}^{\mathbb{N}}$.

Bukti. $\mathcal{P}(\mathbb{N})\approx\{0,1\}^{\mathbb{N}}$ menurut Proposisi 22.3.5(a).

$\mathcal{P}(\mathbb{N})\preceq\mathbb{R}$: pemetaan $S\mapsto0{,}c_1c_2c_3\ldots$ dengan $c_k=4+\chi_S(k-1)$ adalah injeksi ke $(0,1)$ (Solusi 22.2-7). Digitnya hanya $4$ dan $5$, sehingga stringnya kanonik, dan string kanonik berbeda memberi bilangan berbeda (Korolari 12.4.10).

$\mathbb{R}\preceq\mathcal{P}(\mathbb{N})$: $x\mapsto\{q\in\mathbb{Q}:q<x\}$ adalah injeksi $\mathbb{R}\to\mathcal{P}(\mathbb{Q})$ (Latihan 22.3-7). Lalu $\mathcal{P}(\mathbb{Q})\approx\mathcal{P}(\mathbb{N})$ menurut Teorema 23.1.4(c) dengan $\mathbb{Q}\approx\mathbb{N}$ (Teorema 21.2.6).

Teorema 23.2.2 menyelesaikan bukti. $\square$

Notasi $\mathfrak{c}=2^{\aleph_0}$ membaca $\{0,1\}^{\mathbb{N}}$ sebagai "$2$ pangkat $\aleph_0$". Teorema Cantor (Teorema 22.3.3) memberi kembali $\aleph_0<2^{\aleph_0}$.

Akibat 23.2.6

(a) Setiap interval tak degenerat, baik terbuka, tertutup, setengah terbuka, maupun sinar, setara dengan $\mathbb{R}$.

(b) $\mathbb{R}\times\mathbb{R}\approx\mathbb{R}$.

(c) $\mathbb{R}^{\mathbb{N}}\approx\mathbb{R}$, yaitu himpunan semua barisan real setara dengan $\mathbb{R}$.

Bukti. (a) Interval $I$ dengan $a<b$ memuat $(a,b)$ dan termuat di $\mathbb{R}$. Karena $(a,b)\approx\mathbb{R}$ (Proposisi 22.2.4), Akibat 23.2.3(b) memberi $I\approx\mathbb{R}$. Untuk sinar seperti $(a,\infty)$, ia memuat $(a,a+1)$.

(b) Menurut Teorema 23.1.4(a) dan Teorema 23.2.5, $\mathbb{R}\times\mathbb{R}\approx\{0,1\}^{\mathbb{N}}\times\{0,1\}^{\mathbb{N}}$, dan ini setara dengan $\{0,1\}^{\mathbb{N}}\approx\mathbb{R}$ menurut Contoh 23.1.5(c).

(c) Menurut Teorema 23.1.4(d) dan Latihan 23.1-7, $\mathbb{R}^{\mathbb{N}}\approx(\{0,1\}^{\mathbb{N}})^{\mathbb{N}}\approx\{0,1\}^{\mathbb{N}\times\mathbb{N}}$. Ini setara dengan $\{0,1\}^{\mathbb{N}}$ menurut Teorema 23.1.4(d) dengan $\mathbb{N}\times\mathbb{N}\approx\mathbb{N}$. $\square$

Akibat 23.2.6(b) mengejutkan Cantor sendiri: bidang tidak mempunyai lebih banyak titik daripada garis. Bijeksi ini tidak kontinu. Dimensi adalah sifat struktur (kekontinuan, topologi), bukan sifat kardinalitas.

Apakah ada himpunan $S\subseteq\mathbb{R}$ dengan $\mathbb{N}\prec S\prec\mathbb{R}$? Pertanyaan ini adalah hipotesis kontinum. Unit 23.3 mencatat bahwa jawabannya tidak dapat ditentukan dari aksioma baku teori himpunan.

Latihan

Latihan 23.2-1. Untuk $A=B=\mathbb{N}$ dan $f(n)=g(n)=n+1$, tentukan himpunan $C$ pada bukti Teorema 23.2.2 dan bijeksi $h$ yang dihasilkan.

Latihan 23.2-2. Buktikan $[0,1)\approx(0,1)$ dengan Schröder–Bernstein, lalu berikan bijeksi eksplisit.

Latihan 23.2-3. Buktikan bahwa himpunan bilangan irasional $\mathbb{R}\setminus\mathbb{Q}$ setara dengan $\mathbb{R}$ dengan bijeksi eksplisit. (Petunjuk: $E=\{\sqrt2+q:q\in\mathbb{Q}\}$.)

Latihan 23.2-4. Buktikan bahwa $\mathbb{R}^3\approx\mathbb{R}$, dan bahwa $\mathbb{R}^k\approx\mathbb{R}$ untuk setiap $k\geq1$.

Latihan 23.2-5. Buktikan bahwa himpunan semua interval terbuka $(a,b)$ dengan $a<b$ real setara dengan $\mathbb{R}$.

Latihan 23.2-6. Buktikan bahwa $\mathbb{Q}^{\mathbb{N}}\approx\mathbb{R}$ dan $\mathbb{N}^{\mathbb{N}}\approx\mathbb{R}$.

Latihan 23.2-7. Pada bukti Teorema 23.2.2, buktikan bahwa $A\setminus g[B]\subseteq C$, dan bahwa bila $f$ surjektif maka $C=A$ dan $h=f$.

Latihan 23.2-8. Misalkan $A\preceq B$ dan $\mathcal{P}(B)\preceq A$. Buktikan bahwa ini mustahil.

Solusi

Solusi 23.2-1. Persamaan titik tetap: $A\setminus C=g[\mathbb{N}\setminus f[C]]$, yaitu $a\notin C$ jika dan hanya jika $a\geq1$ dan $a-1\notin f[C]$. Selain itu, untuk $b\geq1$, $b\in f[C]$ jika dan hanya jika $b-1\in C$, sedangkan $0\notin f[C]$.

• $a=0$: $0\notin g[\cdot]$, sehingga $0\in C$.
• $a=1$: $a-1=0\notin f[C]$, sehingga $1\notin C$.
• $a\geq2$: $a\notin C\iff a-1\notin f[C]\iff a-2\notin C$.

Induksi kuat memberi $C=\{\text{bilangan genap}\}$, dan ini satu-satunya titik tetap. Maka $h(2k)=f(2k)=2k+1$ dan $h(2k+1)=g^{-1}(2k+1)=2k$. Jadi $h$ menukar $2k\leftrightarrow2k+1$, dan memang bijeksi. $\square$

Solusi 23.2-2. Inklusi $(0,1)\to[0,1)$, dan $x\mapsto\tfrac{x+1}3$ dari $[0,1)$ ke $(0,1)$. Keduanya injeksi, sehingga Teorema 23.2.2 berlaku. Bijeksi eksplisit: $0\mapsto\tfrac12$, $\tfrac1n\mapsto\tfrac1{n+1}$ untuk $n\geq2$, dan titik lain tetap. Peta $\{0\}\cup\{\tfrac1n:n\geq2\}$ adalah $\{\tfrac1n:n\geq2\}$, secara bijektif. $\square$

Solusi 23.2-3. Ambil pencacahan $q_0,q_1,\ldots$ dari $\mathbb{Q}$ tanpa pengulangan (Teorema 21.2.6). Tulis $e_n=\sqrt2+q_n$. Setiap $e_n$ irasional, karena jika $e_n$ rasional maka $\sqrt2=e_n-q_n$ rasional, padahal $\sqrt2$ irasional (Bab 11). Nilai-nilai $e_n$ berbeda satu sama lain, dan $E=\{e_n\}$ saling lepas dengan $\mathbb{Q}$. Tetapkan

$h$ memetakan $\mathbb{Q}\cup E$ secara bijektif ke $E$, karena indeks genap dan ganjil membagi $\mathbb{N}$, dan memetakan $\mathbb{R}\setminus(\mathbb{Q}\cup E)=(\mathbb{R}\setminus\mathbb{Q})\setminus E$ ke dirinya sendiri. Petanya $E\cup\bigl((\mathbb{R}\setminus\mathbb{Q})\setminus E\bigr)=\mathbb{R}\setminus\mathbb{Q}$. Jadi $h$ bijeksi $\mathbb{R}\to\mathbb{R}\setminus\mathbb{Q}$. $\square$

Solusi 23.2-4. $\mathbb{R}^3=\mathbb{R}^2\times\mathbb{R}\approx\mathbb{R}\times\mathbb{R}\approx\mathbb{R}$, dengan Teorema 23.1.4(a) dan Akibat 23.2.6(b). Untuk umum, induksi pada $k$: $\mathbb{R}^{k+1}=\mathbb{R}^k\times\mathbb{R}\approx\mathbb{R}\times\mathbb{R}\approx\mathbb{R}$. $\square$

Solusi 23.2-5. $(a,b)\mapsto(a,b)\in\mathbb{R}^2$, yaitu interval ke pasangan ujungnya, injektif karena interval tak kosong menentukan ujungnya sebagai infimum dan supremum. Jadi himpunan interval $\preceq\mathbb{R}^2\approx\mathbb{R}$. Sebaliknya, $x\mapsto(x,x+1)$ injektif. Teorema 23.2.2. $\square$

Solusi 23.2-6. $\{0,1\}^{\mathbb{N}}\subseteq\mathbb{N}^{\mathbb{N}}$, dan $\mathbb{N}^{\mathbb{N}}\approx\mathbb{Q}^{\mathbb{N}}$ menurut Teorema 23.1.4(d). Selanjutnya $\mathbb{N}^{\mathbb{N}}\preceq\{0,1\}^{\mathbb{N}}$ (Latihan 23.1-8). Teorema 23.2.2 memberi $\mathbb{N}^{\mathbb{N}}\approx\{0,1\}^{\mathbb{N}}\approx\mathbb{R}$. $\square$

Solusi 23.2-7. $C=\varphi(C)=A\setminus g[B\setminus f[C]]\supseteq A\setminus g[B]$, karena $g[B\setminus f[C]]\subseteq g[B]$. Bila $f$ surjektif, $B\setminus f[A]=\emptyset$, sehingga $\varphi(A)=A$. Jadi $A$ titik tetap, dan karena $C$ titik tetap terbesar, $C=A$. Maka $h=f$ di seluruh $A$. $\square$

Solusi 23.2-8. Inklusi $B\to\mathcal{P}(B)$, $b\mapsto\{b\}$, memberi $B\preceq\mathcal{P}(B)\preceq A\preceq B$. Jadi $\mathcal{P}(B)\preceq B$ dan $B\preceq\mathcal{P}(B)$, sehingga Teorema 23.2.2 memberi $B\approx\mathcal{P}(B)$, bertentangan dengan Akibat 22.3.4.

Bukti langsung tanpa Schröder–Bernstein juga ada: misalkan $i:\mathcal{P}(B)\to B$ injektif, dan tetapkan $D=\{b\in B:\text{ada }S\subseteq B\text{ dengan }b=i(S)\text{ dan }b\notin S\}$. Jika $i(D)\in D$, maka $i(D)=i(S)$ untuk suatu $S$ dengan $i(D)\notin S$. Injektivitas memberi $S=D$, sehingga $i(D)\notin D$, kontradiksi. Jika $i(D)\notin D$, maka $S=D$ menjadi saksi bahwa $i(D)\in D$, kontradiksi. $\square$

Ringkasan

Schröder–Bernstein: dua injeksi berlawanan arah menghasilkan bijeksi. Buktinya memakai titik tetap terbesar fungsi monoton pada $\mathcal{P}(A)$, tanpa aksioma pilihan. Akibatnya, $\preceq$ antisimetris sampai kesetaraan. Penerapannya: $[0,1]\approx(0,1)$; $\mathbb{R}\approx\mathcal{P}(\mathbb{N})\approx\{0,1\}^{\mathbb{N}}$, yaitu $\mathfrak{c}=2^{\aleph_0}$; setiap interval tak degenerat, $\mathbb{R}^k$, $\mathbb{R}^{\mathbb{N}}$, $\mathbb{N}^{\mathbb{N}}$, dan himpunan irasional semuanya setara dengan $\mathbb{R}$.

23.3 Aksioma Pilihan dan Lemma Zorn

Beberapa kali sejak Bab 20, buku ini berhenti di depan pernyataan yang tampak jelas tetapi tidak dapat dibuktikan dengan aksioma yang sudah dipakai. Dua contohnya: "setiap himpunan tak hingga memuat salinan $\mathbb{N}$" (Unit 20.3) dan "gabungan terhitung himpunan terhitung adalah terhitung" (Teorema 21.3.5). Hambatannya sama. Bukti alami harus membuat tak hingga banyak pilihan sebarang, tanpa aturan yang menentukan pilihan mana yang diambil. Unit ini merumuskan prinsip yang mengizinkan pilihan semacam itu, yaitu aksioma pilihan. Unit ini juga merumuskan bentuk lemahnya, pilihan terhitung, dan bentuk yang paling sering dipakai dalam aljabar dan analisis, yaitu Lemma Zorn. Setelah itu, Unit ini menutup pinjaman dari Bab 20–21 dan membuktikan dua akibat penting: keterbandingan kardinalitas dan keberadaan basis ruang vektor.

Penjelasan implementasi master: aksioma ini menjadi landasan teoretis untuk membuktikan keberadaan basis dalam ruang vektor berdimensi tak hingga, yang dipakai dalam fisika kuantum dan teknik tingkat lanjut. Bagian akhir unit ini menjelaskan dengan tepat apa yang dijamin dan apa yang tidak.

Prasyarat: Unit 23.1–23.2; urutan parsial (Bab 4); fungsi sebagai grafik (Bab 5); himpunan hingga (Unit 20.1); Unit 20.3 dan 21.3.

Fungsi Pilihan

Definisi 23.3.1 (Fungsi Pilihan)

Misalkan $\mathcal{A}$ himpunan yang anggotanya himpunan-himpunan tak kosong. Fungsi pilihan untuk $\mathcal{A}$ adalah fungsi $c:\mathcal{A}\to\bigcup\mathcal{A}$ dengan $c(X)\in X$ untuk setiap $X\in\mathcal{A}$.

Fungsi pilihan memilih satu wakil dari setiap anggota keluarga, sekaligus, sebagai satu objek. Dalam banyak situasi fungsi semacam itu dapat ditulis langsung:

• Keluarga hingga: untuk $\mathcal{A}=\{X_1,\ldots,X_n\}$, fungsi pilihan ada menurut induksi pada $n$. Setiap langkah hanya memakai satu pilihan tunggal, yang sah dalam logika biasa: dari "$X_{n+1}\ne\emptyset$" kita boleh mengambil satu $x\in X_{n+1}$. Aksioma tambahan tidak diperlukan.
• Subhimpunan tak kosong $\mathbb{N}$: $c(X)=\min X$, menurut urutan baik (Teorema 7.3.4).
• Interval tutup tak degenerat $[a,b]$: $c([a,b])=a$, atau titik tengahnya.
• Subhimpunan tak kosong $\mathbb{Q}$: tidak ada minimum, tetapi pencacahan $q_0,q_1,\ldots$ (Teorema 21.2.6) memberi $c(X)=q_k$ dengan $k$ terkecil sehingga $q_k\in X$.

Untuk keluarga semua subhimpunan tak kosong $\mathbb{R}$, buku ini tidak memberikan aturan semacam itu. "Anggota terkecil" gagal, misalnya pada $(0,1)$. Fakta 23.3.18 di akhir unit mencatat bahwa AC secara umum tidak dapat dibuktikan dari aksioma ZF.

Ilustrasi Russell yang terkenal: dari tak hingga banyak pasang sepatu, kita dapat memilih satu sepatu dari setiap pasang dengan aturan "ambil yang kiri". Dari tak hingga banyak pasang kaus kaki yang identik, tidak ada aturan yang membedakan kedua kaus kaki dalam satu pasang. Aksioma pilihan diperlukan tepat pada kasus kedua.

Aksioma 23.3.2 (Aksioma Pilihan, AC)

Setiap himpunan $\mathcal{A}$ yang anggotanya himpunan-himpunan tak kosong mempunyai fungsi pilihan.

Aksioma 23.3.3 (Aksioma Pilihan Terhitung, AC$_\omega$)

Untuk setiap barisan $(A_n)_{n\in\mathbb{N}}$ himpunan tak kosong, terdapat barisan $(a_n)_{n\in\mathbb{N}}$ dengan $a_n\in A_n$ untuk setiap $n$.

AC mengakibatkan AC$_\omega$: terapkan AC pada $\mathcal{A}=\{A_n:n\in\mathbb{N}\}$, lalu tetapkan $a_n=c(A_n)$. AC$_\omega$ tegas lebih lemah daripada AC, tetapi fakta ini tidak dibuktikan di buku ini.

Kebijakan buku: teori himpunan dasar buku ini (Bab 3) adalah ZF, yaitu aksioma Zermelo–Fraenkel tanpa pilihan. Setiap teorema yang memerlukan AC atau AC$_\omega$ menyebut asumsinya secara eksplisit. Dalam bab-bab analisis berikutnya, AC$_\omega$ muncul dalam bentuk yang khas, misalnya: "untuk setiap $n$ pilih $x_n$ dengan $|x_n-a|<\tfrac1n$ dan sifat tertentu". Penggunaan semacam itu juga akan ditandai.

Surjeksi dan Invers Kanan

Teorema 23.3.4

Pernyataan berikut setara dalam ZF:

(a) AC;

(b) setiap surjeksi $p:A\to B$ mempunyai invers kanan, yaitu $s:B\to A$ dengan $p\circ s=\mathrm{id}_B$.

Akibatnya, dengan AC, jika ada surjeksi $A\to B$ maka $B\preceq A$.

Bukti. (a)⇒(b). Untuk $b\in B$, serat $p^{-1}[\{b\}]$ tidak kosong karena $p$ surjektif. Misalkan $c$ fungsi pilihan untuk $\mathcal{A}=\{p^{-1}[\{b\}]:b\in B\}$, dan tetapkan $s(b)=c(p^{-1}[\{b\}])$. Maka $s(b)\in p^{-1}[\{b\}]$, yaitu $p(s(b))=b$.

(b)⇒(a). Misalkan $\mathcal{A}$ keluarga himpunan tak kosong. Tetapkan $A=\{(X,x):X\in\mathcal{A},\ x\in X\}\subseteq\mathcal{A}\times\bigcup\mathcal{A}$ dan $p(X,x)=X$. Fungsi $p:A\to\mathcal{A}$ surjektif karena setiap $X$ tak kosong. Invers kanan $s$ memberi $s(X)=(X,x_X)$ dengan $x_X\in X$. Fungsi $c(X)=x_X$, yaitu komponen kedua $s(X)$, adalah fungsi pilihan.

Akibat: invers kanan $s$ injektif, karena $s(b)=s(b')$ memberi $b=p(s(b))=p(s(b'))=b'$. $\square$

Bandingkan dengan Teorema 21.1.3(c)⇒(b). Untuk surjeksi dari $\mathbb{N}$, invers kanan dibuat tanpa pilihan dengan "anggota terkecil". Teorema 23.3.4 menyatakan bahwa untuk surjeksi sebarang, keberadaan invers kanan justru setara dengan seluruh kekuatan AC.

Menutup Pinjaman Bab 20 dan 21

Teorema 23.3.5 (Dengan AC$_\omega$: Tak Hingga Mengakibatkan Dedekind-Tak Hingga)

Dengan Aksioma 23.3.3: setiap himpunan tak hingga $A$ memuat subhimpunan terhitung tak hingga. Akibatnya, terdapat injeksi $\mathbb{N}\to A$, dan $A$ Dedekind-tak hingga.

Bukti. Langkah 1, tanpa pilihan: untuk setiap $n\in\mathbb{N}$, himpunan $I_n$ semua injeksi $[n]\to A$ tidak kosong. Himpunan ini sah sebagai subhimpunan $\mathcal{P}([n]\times A)$ menurut separasi. Buktinya induksi pada $n$. Untuk $n=0$, fungsi kosong termasuk $I_0$. Untuk langkah, misalkan $f\in I_n$. Peta $f[[n]]$ hingga, karena berbijeksi dengan $[n]$. Karena $A$ tak hingga, $A\ne f[[n]]$, sehingga ada $a\in A\setminus f[[n]]$. Fungsi $f\cup\{(n+1,a)\}$ adalah injeksi $[n+1]\to A$. Langkah ini membuktikan pernyataan keberadaan dengan satu pilihan tunggal untuk setiap $n$, dan tidak membangun barisan pilihan.

Langkah 2, dengan AC$_\omega$: Aksioma 23.3.3, diterapkan pada $(I_n)_{n\in\mathbb{N}}$, memberi barisan $(f_n)$ dengan $f_n\in I_n$.

Langkah 3, tanpa pilihan: tetapkan $R=\bigcup_{n\in\mathbb{N}}f_n[[n]]\subseteq A$, dan $P=\{(n,k)\in\mathbb{N}\times\mathbb{N}:1\leq k\leq n\}$. Himpunan $P$ tak kosong dan terhitung, sebagai subhimpunan $\mathbb{N}\times\mathbb{N}$ (Teorema 21.2.4, Akibat 21.1.4(a)). Pemetaan $(n,k)\mapsto f_n(k)$ adalah surjeksi $P\to R$, sehingga $R$ terhitung (Akibat 21.1.4(b)).

$R$ tak hingga. Andaikan $R$ hingga dengan $|R|=m$ dan bijeksi $\beta:R\to[m]$. Maka $\beta\circ f_{m+1}$ adalah injeksi $[m+1]\to[m]$, bertentangan dengan Teorema 20.1.4.

Jadi $R$ terhitung dan tak hingga, sehingga terhitung tak hingga (Definisi 21.1.1). Pencacahan $\mathbb{N}\to R$ adalah injeksi $\mathbb{N}\to A$, dan Teorema 20.3.3 memberi bahwa $A$ Dedekind-tak hingga. $\square$

Pinjaman Unit 20.3 dan catatan setelah Akibat 21.1.5 ditutup oleh teorema ini, dengan asumsi AC$_\omega$ yang disebut eksplisit. Dengan asumsi itu, $\aleph_0$ adalah kardinalitas tak hingga terkecil: $\mathbb{N}\preceq A$ untuk setiap himpunan tak hingga $A$.

Perhatikan strategi buktinya. Argumen naif "pilih $a_0$, lalu $a_1\ne a_0$, lalu $a_2\notin\{a_0,a_1\}$, dan seterusnya" membuat pilihan yang bergantung pada pilihan sebelumnya. Prinsip yang membenarkan argumen itu disebut pilihan bergantung (dependent choice). Bukti di atas menghindari ketergantungan itu. Semua daftar $f_n$ dipilih sekaligus dan saling bebas, lalu digabungkan dengan aturan yang tertentu. Karena itu cukup AC$_\omega$.

Teorema 23.3.6 (Teorema 21.3.5 dalam Rumusan Aksioma)

Dengan Aksioma 23.3.3: gabungan terhitung himpunan terhitung adalah terhitung.

Bukti. Bukti Teorema 21.3.5 memilih surjeksi $h_n\in S_n$ hanya untuk indeks $n$ dengan $A_n\ne\emptyset$. Untuk memakai Aksioma 23.3.3, yang meminta barisan himpunan tak kosong untuk semua $n$, tetapkan $T_n=S_n$ bila $A_n\ne\emptyset$ dan $T_n=\{\emptyset\}$ bila $A_n=\emptyset$. Penentuan ini bersifat tertentu: tidak ada pilihan. Aksioma 23.3.3 memberi $(t_n)$ dengan $t_n\in T_n$. Untuk $A_n\ne\emptyset$, $t_n$ adalah surjeksi $\mathbb{N}\to A_n$. Lanjutkan seperti pada bukti Teorema 21.3.5. $\square$

Lemma Zorn

Definisi 23.3.7 (Rantai, Batas Atas, Unsur Maksimal)

Misalkan $(P,\leq)$ himpunan terurut parsial (Bab 4).

(a) $K\subseteq P$ disebut rantai jika setiap dua anggota $K$ dapat dibandingkan: untuk $x,y\in K$, $x\leq y$ atau $y\leq x$.

(b) $u\in P$ adalah batas atas $K\subseteq P$ jika $k\leq u$ untuk setiap $k\in K$. Batas atas tidak harus anggota $K$.

(c) $m\in P$ disebut unsur maksimal jika tidak ada $p\in P$ dengan $m<p$, yaitu $m\leq p$ mengakibatkan $p=m$.

Unsur maksimal berbeda dengan unsur terbesar. Pada $P=\{X\subseteq\{1,2,3\}:X\ne\{1,2,3\}\}$ dengan urutan $\subseteq$, ketiga himpunan dua-anggota adalah unsur maksimal, tetapi tidak ada unsur terbesar.

Pernyataan 23.3.8 (Lemma Zorn)

Jika $(P,\leq)$ himpunan terurut parsial tak kosong dan setiap rantai tak kosong di $P$ mempunyai batas atas di $P$, maka $P$ mempunyai unsur maksimal.

Fakta 23.3.9 (Kesetaraan Klasik, Dicatat Tanpa Bukti Penuh)

Dalam ZF, pernyataan berikut setara:

(a) Aksioma Pilihan;

(b) Lemma Zorn;

(c) Teorema Urutan Baik: setiap himpunan mempunyai urutan baik, yaitu urutan linear yang setiap subhimpunan tak kosongnya mempunyai anggota terkecil.

Arah (b)⇒(a) dibuktikan di bawah (Teorema 23.3.10). Arah (a)⇒(b) dan kesetaraan dengan (c) memerlukan rekursi transfinit atas ordinal, yang berada di luar cakupan buku ini. Ide arah (a)⇒(b): andaikan $P$ tidak mempunyai unsur maksimal. Fungsi pilihan memilih batas atas tegas untuk setiap rantai, lalu rekursi transfinit membangun rantai yang "terlalu panjang" untuk termuat di dalam himpunan $P$.

Sumber: Stanford Encyclopedia of Philosophy, entri "The Axiom of Choice" (https://plato.stanford.edu/entries/axiom-choice/); entri "Axiom of choice", Wikipedia (https://en.wikipedia.org/wiki/Axiom_of_choice); keduanya diakses 2 Oktober 2026 dan merujuk pada literatur standar teori himpunan. Klaim paragraf ini dibatasi pada isi sumber tersebut.

Kebijakan buku: teorema yang dibuktikan dengan Lemma Zorn diberi label "dengan Lemma Zorn". Menurut Fakta 23.3.9, asumsi itu setara dengan AC.

Teorema 23.3.10 (Lemma Zorn Mengakibatkan AC)

Misalkan $\mathcal{A}$ keluarga himpunan tak kosong. Dengan Lemma Zorn, $\mathcal{A}$ mempunyai fungsi pilihan.

Bukti. Misalkan $P$ himpunan semua fungsi pilihan parsial, yaitu fungsi $c$ dengan $\mathrm{dom}(c)\subseteq\mathcal{A}$ dan $c(X)\in X$ untuk setiap $X\in\mathrm{dom}(c)$. Fungsi dipandang sebagai grafik, sehingga $P\subseteq\mathcal{P}(\mathcal{A}\times\bigcup\mathcal{A})$ adalah himpunan menurut separasi. Urutkan $P$ dengan $\subseteq$. Fungsi kosong termasuk $P$, sehingga $P\ne\emptyset$.

Rantai: misalkan $K\subseteq P$ rantai tak kosong dan $u=\bigcup K$. $u$ adalah fungsi. Jika $(X,x),(X,x')\in u$, maka $(X,x)\in c_1$ dan $(X,x')\in c_2$ untuk suatu $c_1,c_2\in K$. Karena $K$ rantai, keduanya termuat di anggota yang lebih besar, yang merupakan fungsi, sehingga $x=x'$. Setiap $(X,x)\in u$ berasal dari suatu $c\in K$, sehingga $x\in X$. Jadi $u\in P$, dan $u$ batas atas $K$.

Lemma Zorn memberi unsur maksimal $m$. Andaikan $X\in\mathcal{A}\setminus\mathrm{dom}(m)$. Karena $X\ne\emptyset$, ambil $x\in X$. Maka $m\cup\{(X,x)\}\in P$ tegas memuat $m$, bertentangan dengan kemaksimalan. Jadi $\mathrm{dom}(m)=\mathcal{A}$, dan $m$ fungsi pilihan. $\square$

Lemma 23.3.11 (Himpunan Hingga di Gabungan Rantai)

Misalkan $K$ rantai tak kosong himpunan-himpunan, dengan urutan $\subseteq$, dan $F\subseteq\bigcup K$ hingga. Maka $F\subseteq X$ untuk suatu $X\in K$.