# 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
$$\mathcal{S}=\{X\in\mathcal{P}(A):X\subseteq\varphi(X)\},\qquad C=\bigcup\mathcal{S}.$$
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
$$\varphi(X)=A\setminus g\bigl[B\setminus f[X]\bigr].$$

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
$$A\setminus C=g\bigl[B\setminus f[C]\bigr].$$

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
$$h(a)=\begin{cases}f(a),&a\in C,\\g^{-1}(a),&a\in A\setminus C.\end{cases}$$
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(q_n)=e_{2n},\qquad h(e_n)=e_{2n+1},\qquad h(x)=x\ \text{untuk}\ x\notin\mathbb{Q}\cup E.$$
$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$.

Bukti. Induksi pada $|F|$. Bila $F=\emptyset$, ambil sebarang $X\in K$. Bila $F=F'\cup\{x\}$ dengan $|F'|=|F|-1$, hipotesis induksi memberi $F'\subseteq X_1\in K$. Juga $x\in X_2$ untuk suatu $X_2\in K$. Karena $K$ rantai, $X_1\subseteq X_2$ atau $X_2\subseteq X_1$, dan yang lebih besar memuat $F$. $\square$

#### Teorema 23.3.12 (Keterbandingan Kardinalitas, dengan Lemma Zorn)

Untuk sebarang himpunan $A$ dan $B$: $A\preceq B$ atau $B\preceq A$.

Bukti. Misalkan $P$ himpunan semua injeksi parsial dari $A$ ke $B$, yaitu $f\subseteq A\times B$ yang merupakan fungsi injektif dari $\mathrm{dom}(f)\subseteq A$ ke $B$. Urutkan $P$ dengan $\subseteq$, dan perhatikan bahwa $\emptyset\in P$.

Rantai tak kosong $K$: $u=\bigcup K$ adalah fungsi, dengan argumen seperti pada Teorema 23.3.10. $u$ juga injektif: jika $(a,b),(a',b)\in u$, keduanya terletak di satu anggota $K$ menurut Lemma 23.3.11 dengan $F$ dua unsur, dan anggota itu injektif, sehingga $a=a'$. Jadi $u\in P$ adalah batas atas.

Lemma Zorn memberi unsur maksimal $m$. Andaikan ada $a\in A\setminus\mathrm{dom}(m)$ dan $b\in B\setminus m[\mathrm{dom}(m)]$. Maka $m\cup\{(a,b)\}$ injeksi parsial yang tegas lebih besar, kontradiksi. Jadi $\mathrm{dom}(m)=A$, sehingga $m$ adalah injeksi $A\to B$, atau $m[\mathrm{dom}(m)]=B$, sehingga $m^{-1}$ adalah injeksi $B\to A$. $\square$

Bersama Schröder–Bernstein, dengan Lemma Zorn, untuk sebarang $A,B$ tepat satu dari $A\prec B$, $A\approx B$, $B\prec A$ berlaku. Hartogs (1915) menunjukkan bahwa keterbandingan ini sebaliknya mengakibatkan teorema urutan baik, sehingga juga AC, dalam ZF. Fakta ini dicatat tanpa bukti. Sumber: entri "Hartogs number", Wikipedia (https://en.wikipedia.org/wiki/Hartogs_number); C. Feldman dan M. Orhon, "Generalizing Hartogs' Trichotomy Theorem", arXiv:0804.0673 (https://arxiv.org/abs/0804.0673); keduanya diakses 2 Oktober 2026. Jadi pertanyaan di akhir Unit 23.2 terjawab: keterbandingan setara dengan AC.

### Basis Ruang Vektor

Bagian ini memerlukan definisi minimal ruang vektor. Buku ini tidak membahas aljabar linear secara umum, sehingga hanya bagian yang diperlukan untuk teorema keberadaan basis yang dinyatakan.

#### Definisi 23.3.13 (Ruang Vektor)

Misalkan $K=\mathbb{Q}$ atau $K=\mathbb{R}$. Ruang vektor atas $K$ adalah himpunan $V$ dengan penjumlahan $V\times V\to V$ dan perkalian skalar $K\times V\to V$ sehingga:

- $(V,+)$ adalah grup komutatif dengan unsur nol $0_V$;
- $a(u+v)=au+av$, $(a+b)v=av+bv$, $(ab)v=a(bv)$, dan $1v=v$, untuk semua $a,b\in K$ dan $u,v\in V$.

Contoh: $\mathbb{R}^n$ atas $\mathbb{R}$; $\mathbb{R}$ atas $\mathbb{Q}$, dengan perkalian skalar perkalian biasa; himpunan $\mathbb{R}^{\mathbb{N}}$ semua barisan real atas $\mathbb{R}$, dengan operasi per suku.

#### Definisi 23.3.14 (Bebas Linear, Rentang, Basis)

Misalkan $V$ ruang vektor atas $K$ dan $S\subseteq V$.

(a) $S$ bebas linear jika untuk setiap $k\in\mathbb{N}$, setiap $v_1,\ldots,v_k\in S$ yang berbeda, dan setiap $c_1,\ldots,c_k\in K$, persamaan $c_1v_1+\cdots+c_kv_k=0_V$ mengakibatkan $c_1=\cdots=c_k=0$.

(b) Rentang $S$, ditulis $\mathrm{span}\,S$, adalah himpunan semua kombinasi linear hingga $c_1v_1+\cdots+c_kv_k$ dengan $v_i\in S$ dan $c_i\in K$. Kombinasi kosong ($k=0$) bernilai $0_V$.

(c) $S$ basis (basis Hamel) jika $S$ bebas linear dan $\mathrm{span}\,S=V$.

Semua jumlah dalam definisi ini hingga. Tidak ada limit atau deret. Ini perbedaan pokok dengan "basis" dalam analisis fungsional, yang dibahas pada catatan setelah Contoh 23.3.17.

Bila $B$ basis, setiap $v\in V$ mempunyai representasi tunggal $v=\sum_{b\in B}c_b(v)\,b$, dengan hanya berhingga banyak $c_b(v)\ne0$. Keberadaan representasi berasal dari rentang. Ketunggalannya berasal dari kebebasan linear, karena selisih dua representasi adalah kombinasi bernilai nol. Akibat ketunggalan, $c_b(u+v)=c_b(u)+c_b(v)$ dan $c_b(av)=a\,c_b(v)$.

#### Teorema 23.3.15 (Keberadaan Basis, dengan Lemma Zorn)

Misalkan $V$ ruang vektor atas $K$ dan $S\subseteq V$ bebas linear. Dengan Lemma Zorn, terdapat basis $B$ dengan $S\subseteq B$. Khususnya, untuk $S=\emptyset$, setiap ruang vektor mempunyai basis.

Bukti. Misalkan $P=\{T\subseteq V:S\subseteq T,\ T\text{ bebas linear}\}$, diurutkan dengan $\subseteq$. $S\in P$, sehingga $P\ne\emptyset$.

Rantai tak kosong $\mathcal{K}\subseteq P$: $U=\bigcup\mathcal{K}$ memuat $S$. $U$ bebas linear, karena vektor berbeda $v_1,\ldots,v_k\in U$ termuat dalam satu $T\in\mathcal{K}$ (Lemma 23.3.11), dan $T$ bebas linear. Jadi $U\in P$ adalah batas atas.

Lemma Zorn memberi unsur maksimal $B$. $B$ bebas linear. Andaikan $\mathrm{span}\,B\ne V$, dan ambil $v\in V\setminus\mathrm{span}\,B$. Maka $v\notin B$. Kita tunjukkan bahwa $B\cup\{v\}$ bebas linear. Misalkan ada kombinasi bernilai nol dari vektor-vektor berbeda di $B\cup\{v\}$. Bila $v$ tidak muncul, semua koefisien nol karena $B$ bebas linear. Bila $v$ muncul dengan koefisien $c$, persamaannya berbentuk $cv+c_1b_1+\cdots+c_kb_k=0_V$ dengan $b_i\in B$ berbeda. Jika $c\ne0$, maka $v=-c^{-1}(c_1b_1+\cdots+c_kb_k)\in\mathrm{span}\,B$, kontradiksi. Jadi $c=0$, lalu $c_1=\cdots=c_k=0$. Maka $B\cup\{v\}\in P$ tegas lebih besar daripada $B$, bertentangan dengan kemaksimalan. Jadi $\mathrm{span}\,B=V$. $\square$

Kebalikannya juga benar: dalam ZF, pernyataan "setiap ruang vektor mempunyai basis" mengakibatkan AC. Hasil ini dari A. Blass dan dicatat tanpa bukti; sumbernya entri "Axiom of choice" di atas.

#### Contoh 23.3.16 (Barisan Real)

Di $V=\mathbb{R}^{\mathbb{N}}$ atas $\mathbb{R}$, misalkan $e_k$ barisan dengan suku $1$ di posisi $k$ dan $0$ di posisi lain. Himpunan $E=\{e_k:k\in\mathbb{N}\}$ bebas linear. Kombinasi $\sum_{i\leq k}c_ie_i$ mempunyai suku ke-$i$ sama dengan $c_i$, sehingga kombinasi itu nol hanya jika semua $c_i=0$.

Akan tetapi $\mathrm{span}\,E$ hanya berisi barisan yang akhirnya nol. Barisan $(1,1,1,\ldots)$ tidak termasuk di dalamnya. Jadi $E$ bukan basis Hamel. Teorema 23.3.15 menjamin adanya basis $B\supseteq E$, tetapi buktinya tidak memberikan cara untuk menuliskan $B$, dan buku ini tidak akan menuliskannya.

#### Contoh 23.3.17 ($\mathbb{R}$ atas $\mathbb{Q}$ dan Fungsi Aditif yang Tidak Linear)

Dengan Lemma Zorn, $\mathbb{R}$ sebagai ruang vektor atas $\mathbb{Q}$ mempunyai basis $H$.

(a) $H$ tak terhitung. Bila $H$ terhitung, $H$ dapat dicacah, dan rentangnya adalah gabungan atas $k\in\mathbb{N}$ dari peta $\mathbb{Q}^{k}$ di bawah pemetaan koefisien ke kombinasi linear $k$ unsur pertama $H$. Gabungan ini terhitung menurut Teorema 21.3.3, karena semua pencacahannya tertentu. Padahal $\mathrm{span}\,H=\mathbb{R}$ tak terhitung (Akibat 22.2.3).

(b) Ada fungsi $f:\mathbb{R}\to\mathbb{R}$ dengan $f(x+y)=f(x)+f(y)$ untuk semua $x,y$, tetapi tidak berbentuk $f(x)=cx$. Karena $H$ tak terhitung, ambil $b_0\ne b_1$ di $H$, dan tetapkan $f(x)=c_{b_0}(x)$, yaitu koordinat $x$ pada $b_0$. Menurut sifat koordinat, $f$ aditif. Andaikan $f(x)=cx$ untuk semua $x$. Maka $0=f(b_1)=cb_1$. Karena $b_1\ne0$ (unsur himpunan bebas linear tidak nol), $c=0$. Tetapi $f(b_0)=1\ne0$, kontradiksi.

Fungsi $f$ ini hanya bernilai rasional, tetapi tidak konstan. Grafiknya sangat tidak beraturan. Latihan 23.3-8 menunjukkan bahwa setiap fungsi aditif bersifat linear pada $\mathbb{Q}$. Rencana penutupan: setelah kekontinuan didefinisikan (Bagian VII, Bab 36), akan dibuktikan bahwa fungsi aditif yang kontinu pasti berbentuk $cx$. Jadi fungsi seperti $f$ tidak mungkin kontinu. Keberadaan $f$ memerlukan pilihan, dan buku ini tidak memakainya di luar contoh ini.

#### Catatan tentang Implementasi: Fisika Kuantum dan Teknik

Pernyataan master perlu dibaca dengan tepat.

(a) Dalam mekanika kuantum dan pengolahan sinyal, ruang keadaan dimodelkan sebagai ruang Hilbert, yaitu ruang vektor dengan hasil kali dalam yang lengkap. "Basis" yang dipakai di sana adalah basis ortonormal, yang memakai deret tak hingga yang konvergen, bukan basis Hamel yang hanya memakai jumlah hingga. Pembahasan konvergensi deret baru tersedia pada Bagian VI.

(b) Pernyataan "setiap ruang Hilbert mempunyai basis ortonormal" dibuktikan secara umum dengan Lemma Zorn, dengan argumen yang sejajar dengan Teorema 23.3.15. Sumber entri "Axiom of choice" di atas mencatat teorema ini sebagai hasil yang memerlukan AC dalam bentuk umumnya.

(c) Ruang yang dipakai dalam perhitungan nyata biasanya separabel, yaitu memuat barisan padat yang terhitung. Untuk ruang separabel, basis ortonormal dapat dibangun dari barisan padat yang diberikan dengan proses Gram–Schmidt, tanpa AC penuh. Basis yang dipakai dalam praktik, seperti basis Fourier, juga diberikan secara eksplisit.

Jadi peran AC dan Lemma Zorn di sini adalah landasan teoretis: keduanya menjamin keberadaan basis dalam keumuman penuh. Perhitungan teknik tidak bergantung pada basis yang tidak dapat dituliskan. Klaim pada catatan ini dibatasi pada tingkat umum yang dinyatakan, dan buku ini tidak membuat klaim tentang perangkat atau standar teknik tertentu.

### Status Logis Aksioma Pilihan

#### Fakta 23.3.18 (Independensi, Dicatat Tanpa Bukti)

(a) Gödel (1938) menunjukkan bahwa negasi AC bukan teorema ZF, bila ZF konsisten. Cohen (1963), dengan metode forcing, menunjukkan bahwa AC sendiri juga bukan teorema ZF, bila ZF konsisten. Jadi AC independen dari ZF.

(b) Hipotesis kontinum (CH) menyatakan bahwa setiap himpunan tak hingga $S\subseteq\mathbb{R}$ dapat diinjeksikan ke $\mathbb{N}$, atau $\mathbb{R}$ dapat diinjeksikan ke $S$. Dengan kata lain, tidak ada $S$ dengan $\mathbb{N}\prec S\prec\mathbb{R}$. Gödel (1940) menunjukkan bahwa negasi CH tidak dapat dibuktikan dalam teori himpunan baku. Cohen (1963) menunjukkan bahwa CH juga tidak dapat dibuktikan. Ini menjawab pertanyaan di akhir Unit 23.2: jawabannya tidak ditentukan oleh ZFC.

Sumber: entri "Axiom of choice" dan "Continuum hypothesis", Wikipedia (https://en.wikipedia.org/wiki/Axiom_of_choice, https://en.wikipedia.org/wiki/Continuum_hypothesis), diakses 2 Oktober 2026. Pernyataan di atas mengikuti rumusan kedua sumber itu.

Bagi analisis, ringkasannya sebagai berikut. Hampir semua teorema analisis real di buku ini dapat dibuktikan dalam ZF dengan tambahan AC$_\omega$, dan penggunaan AC$_\omega$ akan ditandai. AC penuh hanya muncul pada contoh keberadaan seperti Contoh 23.3.17.

### Latihan

Latihan 23.3-1. Tuliskan fungsi pilihan eksplisit, tanpa AC, untuk: (a) keluarga semua subhimpunan tak kosong $\mathbb{Z}$; (b) keluarga semua subhimpunan hingga tak kosong $\mathbb{R}$; (c) keluarga semua interval terbuka $(a,b)$ dengan $a<b$.

Latihan 23.3-2. Buktikan tanpa AC bahwa setiap keluarga hingga himpunan tak kosong mempunyai fungsi pilihan.

Latihan 23.3-3. Pada $\mathbb{R}$ tetapkan $x\sim y$ jika $x-y\in\mathbb{Q}$. Buktikan bahwa $\sim$ relasi ekuivalensi, dan bahwa dengan AC, himpunan kelas ekuivalensinya $\mathbb{R}/{\sim}$ memenuhi $\mathbb{R}/{\sim}\preceq\mathbb{R}$.

Latihan 23.3-4. Dengan AC$_\omega$, buktikan bahwa untuk setiap himpunan tak hingga $A$ dan $p\notin A$: $A\cup\{p\}\approx A$.

Latihan 23.3-5. Buktikan tanpa Lemma Zorn bahwa setiap himpunan terurut parsial hingga yang tak kosong mempunyai unsur maksimal.

Latihan 23.3-6. Buktikan arah (a)⇒(b) Teorema 23.3.4 langsung dengan Lemma Zorn, memakai invers kanan parsial.

Latihan 23.3-7. Di $\mathbb{R}$ atas $\mathbb{Q}$, buktikan bahwa $\{1,\sqrt2\}$ bebas linear dan $\{1,\sqrt2,\sqrt8\}$ tidak bebas linear.

Latihan 23.3-8. Misalkan $f:\mathbb{R}\to\mathbb{R}$ aditif, yaitu $f(x+y)=f(x)+f(y)$ untuk semua $x,y$. Buktikan tanpa AC bahwa $f(qx)=q\,f(x)$ untuk semua $q\in\mathbb{Q}$ dan $x\in\mathbb{R}$. Simpulkan bahwa $f(q)=q\,f(1)$ untuk $q\in\mathbb{Q}$.

### Solusi

Solusi 23.3-1. (a) Untuk $X\ne\emptyset$, himpunan $\{|z|:z\in X\}\subseteq\mathbb{N}$ mempunyai minimum $m$ (urutan baik). Ambil $c(X)=m$ bila $m\in X$, dan $c(X)=-m$ bila tidak. (b) $c(X)=\min X$. Himpunan hingga tak kosong bilangan real mempunyai minimum, menurut induksi pada banyak anggota. (c) $c((a,b))=\tfrac{a+b}2$. Fungsi ini terdefinisi karena $a=\inf(a,b)$ dan $b=\sup(a,b)$ ditentukan oleh himpunannya. $\square$

Solusi 23.3-2. Induksi pada $n=|\mathcal{A}|$. Untuk $n=0$, fungsi kosong. Untuk langkah, tulis $\mathcal{A}=\mathcal{A}'\cup\{X\}$ dengan $X\notin\mathcal{A}'$. Hipotesis induksi memberi fungsi pilihan $c'$ untuk $\mathcal{A}'$. Karena $X\ne\emptyset$, ambil $x\in X$. Fungsi $c'\cup\{(X,x)\}$ adalah fungsi pilihan untuk $\mathcal{A}$. Setiap langkah membuktikan pernyataan keberadaan dengan satu pilihan tunggal, sehingga AC tidak dipakai. $\square$

Solusi 23.3-3. Refleksif: $x-x=0\in\mathbb{Q}$. Simetris: $y-x=-(x-y)$. Transitif: $x-z=(x-y)+(y-z)$. $\mathbb{Q}$ tertutup terhadap negasi dan penjumlahan. Pemetaan $p(x)=[x]$ adalah surjeksi $\mathbb{R}\to\mathbb{R}/{\sim}$. Teorema 23.3.4 memberi invers kanan injektif $s:\mathbb{R}/{\sim}\to\mathbb{R}$, sehingga $\mathbb{R}/{\sim}\preceq\mathbb{R}$. Peta $s$ memuat tepat satu wakil dari setiap kelas. Himpunan semacam itu disebut himpunan Vitali, dan keberadaannya bergantung pada AC. $\square$

Solusi 23.3-4. Teorema 23.3.5 memberi injeksi $g:\mathbb{N}\to A$. Tetapkan $h:A\cup\{p\}\to A$ dengan $h(p)=g(0)$, $h(g(n))=g(n+1)$, dan $h(a)=a$ untuk $a\in A\setminus g[\mathbb{N}]$. Fungsi $h$ memetakan $\{p\}\cup g[\mathbb{N}]$ secara bijektif ke $g[\mathbb{N}]$: $p\mapsto g(0)$, dan $g(n)\mapsto g(n+1)$. Di bagian lain, $h$ adalah identitas. Jadi $h$ bijeksi. $\square$

Solusi 23.3-5. Untuk $p\in P$ tulis $d(p)=|\{q\in P:q\leq p\}|$. Himpunan nilai $d$ adalah himpunan hingga tak kosong di $\mathbb{N}$, sehingga mempunyai maksimum. Ambil $p$ dengan $d(p)$ maksimum. Bila ada $q$ dengan $p<q$, maka $\{r:r\leq p\}\cup\{q\}\subseteq\{r:r\leq q\}$ menurut transitivitas. Karena $q\not\leq p$, sebab $q\leq p$ bersama $p\leq q$ memberi $p=q$, gabungan itu memuat $d(p)+1$ anggota. Jadi $d(q)>d(p)$, kontradiksi. Maka $p$ maksimal. $\square$

Solusi 23.3-6. Misalkan $p:A\to B$ surjektif, dan $P$ himpunan fungsi $s$ dengan $\mathrm{dom}(s)\subseteq B$ dan $p(s(b))=b$ untuk $b\in\mathrm{dom}(s)$, diurutkan dengan $\subseteq$. $\emptyset\in P$. Gabungan rantai tak kosong adalah fungsi, seperti pada Teorema 23.3.10, dan tetap memenuhi $p(s(b))=b$, sehingga menjadi batas atas. Unsur maksimal $s$ mempunyai $\mathrm{dom}(s)=B$. Bila $b\notin\mathrm{dom}(s)$, ambil $a$ dengan $p(a)=b$; maka $s\cup\{(b,a)\}\in P$ lebih besar. $\square$

Solusi 23.3-7. Misalkan $a+b\sqrt2=0$ dengan $a,b\in\mathbb{Q}$. Bila $b\ne0$, maka $\sqrt2=-\tfrac ab\in\mathbb{Q}$, bertentangan dengan irasionalitas $\sqrt2$ (Bab 11). Jadi $b=0$, lalu $a=0$. Karena $\sqrt8=2\sqrt2$, berlaku $0\cdot1+2\cdot\sqrt2+(-1)\cdot\sqrt8=0$ dengan koefisien tidak semuanya nol. Jadi $\{1,\sqrt2,\sqrt8\}$ tidak bebas linear. $\square$

Solusi 23.3-8. $f(0)=f(0+0)=2f(0)$, sehingga $f(0)=0$. Induksi memberi $f(nx)=nf(x)$ untuk $n\in\mathbb{N}$. Dari $0=f(x+(-x))=f(x)+f(-x)$ diperoleh $f(-x)=-f(x)$, sehingga $f(nx)=nf(x)$ untuk $n\in\mathbb{Z}$. Untuk $n\geq1$, $f(x)=f(n\cdot\tfrac xn)=nf(\tfrac xn)$, sehingga $f(\tfrac xn)=\tfrac1nf(x)$. Untuk $q=\tfrac mn$, $f(qx)=mf(\tfrac xn)=\tfrac mnf(x)$. Dengan $x=1$: $f(q)=qf(1)$. $\square$

### Ringkasan

Aksioma pilihan menjamin fungsi pilihan untuk sebarang keluarga himpunan tak kosong. Pilihan terhitung adalah bentuk lemahnya untuk barisan. Keluarga hingga, dan keluarga yang mempunyai aturan pilih seperti "anggota terkecil", tidak memerlukan aksioma itu. Dengan AC$_\omega$, pinjaman dari Bab 20–21 ditutup: setiap himpunan tak hingga memuat salinan $\mathbb{N}$, dan gabungan terhitung himpunan terhitung terhitung. Dalam ZF, AC setara dengan Lemma Zorn, dengan teorema urutan baik, dan dengan keberadaan invers kanan surjeksi. Arah Zorn ⇒ AC dan kesetaraan dengan invers kanan dibuktikan di unit ini; arah lainnya dicatat dengan sumber. Lemma Zorn memberi keterbandingan kardinalitas dan basis untuk setiap ruang vektor, termasuk basis Hamel $\mathbb{R}$ atas $\mathbb{Q}$ dan fungsi aditif yang tidak linear. Dalam fisika dan teknik, peran AC adalah menjamin keberadaan basis secara umum; basis yang dipakai dalam perhitungan diberikan secara eksplisit. AC dan CH independen dari aksioma baku.