Bab 22: Ketakteranhimpunan dan Argumen Diagonal Cantor

22.1 Argumen Diagonal Cantor

Bab 21 memperlihatkan banyak himpunan tak hingga yang ternyata terhitung: $\mathbb{Z}$, $\mathbb{N}\times\mathbb{N}$, $\mathbb{Q}$, bahkan himpunan bilangan aljabar. Wajar untuk menduga bahwa setiap himpunan tak hingga dapat dicacah, asal caranya cukup cerdik. Georg Cantor membantah dugaan itu dengan argumen diagonal: suatu metode pembuktian dengan kontradiksi yang menunjukkan bahwa daftar terhitung mana pun pasti melewatkan sesuatu. Penjelasan master menyebutnya metode untuk menunjukkan bahwa himpunan bilangan riil tidak dapat didaftar sebagai barisan terhitung.

Unit ini menyajikan argumen itu dalam bentuk paling bersih, pada himpunan semua barisan biner, tanpa kerumitan representasi desimal. Unit 22.2 menerapkannya pada $(0,1)$ dan $\mathbb{R}$, dan Unit 22.3 mengabstraksikannya menjadi Teorema Cantor tentang himpunan kuasa.

Prasyarat: Bab 21 (terhitung, Teorema 21.1.3); fungsi dan barisan (Bab 5, Bab 7); pembuktian dengan kontradiksi (Bab 6).

Himpunan Barisan Biner

Definisi 22.1.1

$\{0,1\}^{\mathbb{N}}$ adalah himpunan semua fungsi $s:\mathbb{N}\to\{0,1\}$, yaitu barisan tak hingga $s=(s_0,s_1,s_2,\ldots)$ dengan setiap $s_k\in\{0,1\}$. Dua barisan sama jika dan hanya jika sama di setiap indeks (kesamaan fungsi, Bab 5).

Teorema dan Argumennya

Teorema 22.1.2 (Diagonal Cantor)

Tidak ada surjeksi $\mathbb{N}\to\{0,1\}^{\mathbb{N}}$. Akibatnya, $\{0,1\}^{\mathbb{N}}$ tak terhitung.

Bukti. Misalkan $F:\mathbb{N}\to\{0,1\}^{\mathbb{N}}$ sebarang fungsi. Tulis $F(n)=(F(n)_0,F(n)_1,\ldots)$, yaitu barisan ke-$n$ dalam daftar. Definisikan barisan $d\in\{0,1\}^{\mathbb{N}}$ oleh

Untuk setiap $n\in\mathbb{N}$, $d_n=1-F(n)_n\ne F(n)_n$, karena $1-b\ne b$ untuk $b\in\{0,1\}$. Jadi $d$ dan $F(n)$ berbeda di indeks $n$, sehingga $d\ne F(n)$. Karena ini berlaku untuk setiap $n$, $d$ tidak berada dalam peta $F$, dan $F$ tidak surjektif.

Akibat: bila $\{0,1\}^{\mathbb{N}}$ terhitung, ia tak kosong (memuat barisan nol), sehingga ada surjeksi $\mathbb{N}\to\{0,1\}^{\mathbb{N}}$ menurut Teorema 21.1.3(c), kontradiksi. $\square$

Nama "diagonal" berasal dari gambarnya. Tuliskan daftar $F(0),F(1),F(2),\ldots$ sebagai baris-baris tabel tak hingga:

Barisan $d$ dibaca sepanjang diagonal tebal, dengan setiap entri dibalik. Ia berbeda dari baris ke-$n$ tepat di kolom ke-$n$.

Tiga ciri logis argumen ini:

1. Konstruktif relatif terhadap daftar. Untuk setiap daftar yang diberikan, barisan yang terlewat ditulis secara eksplisit. Bukti ini tidak memakai aksioma pilihan.
2. Bentuknya "untuk setiap $F$ ada $d\notin F[\mathbb{N}]$", yaitu negasi "ada $F$ yang surjektif". Pertukaran kuantor di sini disengaja: $d$ bergantung pada $F$.
3. Argumen ini tidak bergantung pada urutan daftar atau pada keterhitungan apa pun selain indeks $\mathbb{N}$.

Contoh 22.1.3 (Diagonal untuk Daftar Konkret)

Misalkan $F(n)$ adalah barisan yang bernilai $1$ tepat di indeks kelipatan $n+1$, dan $0$ di indeks lainnya. Contohnya, $F(0)=(1,1,1,\ldots)$ dan $F(1)=(1,0,1,0,\ldots)$. Entri diagonal $F(k)_k$ bernilai $1$ jika dan hanya jika $(k+1)\mid k$. Untuk $k=0$: $1\mid0$, sehingga entrinya $1$. Untuk $k\geq1$: $k+1>k\geq1$, sehingga $k+1\nmid k$, dan entrinya $0$. Jadi $d=(0,1,1,1,\ldots)$, dan $d\ne F(n)$ untuk setiap $n$: misalnya $d_0=0\ne1=F(0)_0$, dan $d_1=1\ne0=F(1)_1$.

Variasi

Akibat 22.1.4

Untuk setiap himpunan $B$ dengan paling sedikit dua anggota, $B^{\mathbb{N}}$ (semua barisan dengan nilai di $B$) tak terhitung.

Bukti. Ambil $b_0\ne b_1$ di $B$. Untuk $F:\mathbb{N}\to B^{\mathbb{N}}$, definisikan $d_k=b_1$ bila $F(k)_k=b_0$, dan $d_k=b_0$ bila $F(k)_k\ne b_0$. Maka $d_k\ne F(k)_k$ untuk setiap $k$. Pada kasus pertama, $b_1\ne b_0=F(k)_k$. Pada kasus kedua, $d_k=b_0\ne F(k)_k$. $\square$

Bila $B$ hanya mempunyai satu anggota, $B^{\mathbb{N}}$ hanya memuat satu barisan konstan, sehingga terhitung. Syarat "paling sedikit dua anggota" adalah syarat yang benar-benar diperlukan.

Proposisi 22.1.5 (Barisan Biner yang Akhirnya Nol)

Himpunan $E\subseteq\{0,1\}^{\mathbb{N}}$ yang berisi barisan biner yang hanya mempunyai berhingga banyak entri $1$ adalah terhitung. Akibatnya, komplemennya $\{0,1\}^{\mathbb{N}}\setminus E$ tak terhitung.

Bukti. Barisan $s\in E$ ditentukan oleh himpunan hingga $\{k:s_k=1\}\subseteq\mathbb{N}$. Pemetaan ini injektif ke himpunan subhimpunan hingga $\mathbb{N}$, yang terhitung (Latihan 21.3-6). Komplemennya tak terhitung karena gabungan dua himpunan terhitung terhitung (Teorema 21.3.1). $\square$

Proposisi ini menunjukkan bahwa argumen diagonal tidak sekadar menemukan satu barisan yang terlewat. Hampir semua barisan, dalam arti kardinalitas, berada di luar setiap himpunan terhitung.

Kesalahan Umum

Menerapkan argumen diagonal pada $\mathbb{Q}$ atau pada $\mathbb{N}$ tidak menghasilkan kontradiksi. Untuk daftar rasional $q_0,q_1,\ldots$ yang ditulis dalam desimal, mengubah digit ke-$n$ dari $q_n$ menghasilkan bilangan real yang berbeda dari setiap $q_n$. Namun bilangan itu tidak harus rasional, sehingga tidak ada kontradiksi dengan keterhitungan $\mathbb{Q}$. Argumen diagonal berhasil tepat ketika objek hasil konstruksi dijamin anggota himpunan yang sedang ditinjau. Pada $\{0,1\}^{\mathbb{N}}$ hal itu jelas. Pada $(0,1)$ diperlukan kehati-hatian dengan ekspansi ganda (Unit 22.2).

Latihan

Latihan 22.1-1. Untuk daftar $F(n)=(0,0,\ldots)$ untuk semua $n$, tentukan barisan diagonal $d$ dan periksa bahwa $d$ tidak berada dalam daftar.

Latihan 22.1-2. Untuk $F(n)$ yang bernilai $1$ tepat di indeks $n$ dan $0$ di lainnya, tentukan $d$.

Latihan 22.1-3. Buktikan Akibat 22.1.4 untuk $B=\{0,1,\ldots,9\}$. Barisan diagonal mana yang Anda gunakan?

Latihan 22.1-4. Buktikan bahwa $\{0,1\}^{\mathbb{N}}$ tak hingga dengan injeksi eksplisit dari $\mathbb{N}$.

Latihan 22.1-5. Buktikan bahwa untuk setiap $F:\mathbb{N}\to\{0,1\}^{\mathbb{N}}$, ada tak hingga banyak barisan yang tidak berada dalam peta $F$.

Latihan 22.1-6. Mengapa argumen diagonal tidak membuktikan bahwa $E$ pada Proposisi 22.1.5 tak terhitung? Tunjukkan langkah yang gagal pada daftar barisan di $E$.

Latihan 22.1-7. Buktikan bahwa $\mathbb{N}^{\mathbb{N}}$, himpunan semua barisan bilangan asli, tak terhitung.

Latihan 22.1-8. Buktikan bahwa jika $A$ tak terhitung dan $A\subseteq B$, maka $B$ tak terhitung. Simpulkan bahwa himpunan semua fungsi $\mathbb{N}\to\mathbb{R}$ tak terhitung.

Solusi

Solusi 22.1-1. $d_k=1-0=1$ untuk semua $k$, sehingga $d=(1,1,\ldots)$. Barisan ini berbeda dari barisan nol di setiap indeks. $\square$

Solusi 22.1-2. $F(k)_k=1$, sehingga $d_k=0$ untuk semua $k$, dan $d$ adalah barisan nol. Untuk setiap $n$, $F(n)_n=1\ne0=d_n$. $\square$

Solusi 22.1-3. Dengan $b_0=0$ dan $b_1=1$: $d_k=1$ bila $F(k)_k=0$, dan $d_k=0$ bila tidak. Pilihan lain yang juga sah: $d_k=5$ bila $F(k)_k\ne5$, dan $d_k=4$ bila $F(k)_k=5$. Pilihan ini dipakai di Unit 22.2. $\square$

Solusi 22.1-4. $n\mapsto e^{(n)}$ dengan $e^{(n)}_k=1$ tepat bila $k=n$. Untuk $n\ne m$, $e^{(n)}_n=1\ne0=e^{(m)}_n$. $\square$

Solusi 22.1-5. Peta $F[\mathbb{N}]$ terhitung (Akibat 21.1.4(b)). Bila komplemennya berhingga, $\{0,1\}^{\mathbb{N}}$ akan terhitung (Teorema 21.3.1), kontradiksi. Jadi komplemennya tak hingga. Bahkan tak terhitung, dengan alasan yang sama. $\square$

Solusi 22.1-6. Bila $F$ mendaftar $E$, barisan diagonal $d$ berbeda dari setiap $F(n)$, tetapi $d$ tidak harus anggota $E$. Barisan $d$ mungkin mempunyai tak hingga banyak entri $1$. Misalnya, untuk daftar yang semua entri diagonalnya $0$, $d=(1,1,\ldots)\notin E$. Jadi tidak ada kontradiksi. $\square$

Solusi 22.1-7. $\{0,1\}^{\mathbb{N}}\subseteq\mathbb{N}^{\mathbb{N}}$, lalu gunakan Latihan 22.1-8. Alternatifnya, Akibat 22.1.4 dengan $B=\mathbb{N}$. $\square$

Solusi 22.1-8. Bila $B$ terhitung, subhimpunannya $A$ terhitung (Akibat 21.1.4(a)), kontradiksi. Fungsi $\mathbb{N}\to\{0,1\}\subseteq\mathbb{R}$ adalah subhimpunan himpunan fungsi $\mathbb{N}\to\mathbb{R}$, setelah barisan biner dipandang sebagai barisan real. $\square$

Ringkasan

Argumen diagonal Cantor: untuk setiap daftar barisan biner, barisan yang membalik entri diagonal berbeda dari setiap baris, sehingga $\{0,1\}^{\mathbb{N}}$ tak terhitung. Argumen ini konstruktif relatif terhadap daftar, tanpa aksioma pilihan, dan berlaku untuk barisan bernilai di himpunan dengan paling sedikit dua anggota. Himpunan terhitung hanyalah bagian kecil dari $\{0,1\}^{\mathbb{N}}$. Argumen ini gagal, sebagaimana mestinya, pada himpunan terhitung, karena objek diagonal tidak harus anggota himpunan itu. Unit 22.2 menerapkannya pada bilangan real.

22.2 Ketakteranhimpunan Interval Terbuka $(0,1)$ dan $\mathbb{R}$

Unit 22.1 membuktikan bahwa himpunan barisan biner tak terhitung. Unit ini membuktikan hasil utama Cantor untuk analisis: interval $(0,1)$, dan karenanya $\mathbb{R}$, tak terhitung. Kita memberi dua bukti. Bukti pertama adalah argumen diagonal pada ekspansi desimal, yang memerlukan kehati-hatian karena satu bilangan dapat mempunyai dua ekspansi ($0{,}5000\ldots=0{,}4999\ldots$); Unit 12.4 menyediakan bentuk kanonik yang tunggal. Bukti kedua memakai interval bersarang (Unit 12.2) tanpa desimal sama sekali, dan memperlihatkan bahwa yang sesungguhnya bekerja adalah kelengkapan $\mathbb{R}$. Setelah itu, setiap interval tak degenerat terbukti berbijeksi dengan $(0,1)$, dan $\mathbb{R}$ berbijeksi dengan $(-1,1)$.

Prasyarat: Unit 22.1; Unit 12.4 (Teorema 12.4.6, Lemma 12.4.7, Teorema 12.4.8, Korolari 12.4.10); Unit 12.2 (Teorema 12.2.4); Bab 21; Teorema 7.4.1.

Bukti Pertama: Diagonal Desimal

Untuk $x\in(0,1)$, ekspansi kanonik $x$ (Korolari 12.4.10) mempunyai bagian bulat $0$, karena $0\leq x<1$ memberi $\lfloor x\rfloor=0$. Tulis ekspansi itu $0{,}d_1d_2d_3\ldots$, dengan sifat tidak berekor sembilan. Ekspansi itu tunggal, sehingga digit-digit $d_k(x)$ adalah fungsi dari $x$.

Teorema 22.2.1 ($(0,1)$ Tak Terhitung)

Tidak ada surjeksi $\mathbb{N}\to(0,1)$. Jadi $(0,1)$ tak terhitung.

Bukti. Misalkan $x:\mathbb{N}\to(0,1)$ sebarang, $n\mapsto x_n$. Definisikan digit-digit

dan $y$ sebagai nilai string $0{,}e_1e_2e_3\ldots$ (Definisi 12.4.3).

(i) $y\in(0,1)$. Pemotongan pertama memberi $y\geq s_1=\tfrac{e_1}{10}\geq\tfrac4{10}>0$. Untuk batas atas, setiap $e_k\leq5$, sehingga setiap pemotongan $y$ tidak melebihi pemotongan yang sama dari string $0{,}555\ldots$, yang bernilai $\tfrac59$ (Latihan 22.2-2). Jadi $\tfrac59$ adalah batas atas semua pemotongan $y$, dan $y\leq\tfrac59<1$.

(ii) String $0{,}e_1e_2\ldots$ kanonik: semua digitnya $4$ atau $5$, sehingga tidak ada ekor sembilan. Menurut ketunggalan bentuk kanonik (Korolari 12.4.10), digit kanonik $y$ adalah tepat $e_k$.

(iii) $y\ne x_n$ untuk setiap $n$. Digit kanonik ke-$(n+1)$ dari $y$ adalah $e_{n+1}$, yang berbeda dari $d_{n+1}(x_n)$ menurut definisi. Dua bilangan dengan digit kanonik berbeda adalah bilangan berbeda, karena ekspansi kanonik adalah fungsi dari bilangan.

Jadi $y\in(0,1)$ tidak berada dalam peta $x$. $\square$

Mengapa digit $4$ dan $5$, bukan aturan sederhana "tambah satu"? Aturan yang dapat menghasilkan digit $9$ atau $0$ berisiko menghasilkan string berekor sembilan, misalnya $0{,}4999\ldots$. String semacam itu bernilai sama dengan string lain, $0{,}5000\ldots$, sehingga "berbeda digit" tidak lagi menjamin "berbeda bilangan". Dengan digit $4$ dan $5$, string diagonal dijamin kanonik, dan ketunggalan menyelesaikan argumen.

Bukti Kedua: Interval Bersarang

Teorema 22.2.2 (Bukti Tanpa Desimal)

Untuk setiap barisan $(x_n)_{n\in\mathbb{N}}$ bilangan real dan setiap interval $[a,b]$ dengan $a<b$, ada $p\in[a,b]$ dengan $p\ne x_n$ untuk semua $n$.

Bukti. Definisikan dengan rekursi (Teorema 7.4.1) interval $J_n=[a_n,b_n]$ dengan $a_n<b_n$. Mulai dengan $J_0'=[a,b]$. Untuk interval $[u,v]$ dengan $u<v$ dan bilangan $t$, tetapkan sepertiga kiri $L=[u,u+\tfrac{v-u}3]$ dan sepertiga kanan $R=[v-\tfrac{v-u}3,v]$. Keduanya saling lepas, karena $u+\tfrac{v-u}3<v-\tfrac{v-u}3$. Langkahnya: pilih $L$ bila $t\notin L$, dan $R$ bila $t\in L$. Pada kasus kedua $t\notin R$ karena $L\cap R=\emptyset$. Aturan ini deterministik, dan interval terpilih tidak memuat $t$.

Tetapkan $J_0$ sebagai hasil langkah pada $J_0'$ dengan $t=x_0$, dan $J_{n+1}$ sebagai hasil langkah pada $J_n$ dengan $t=x_{n+1}$. Maka:

• $J_{n+1}\subseteq J_n$;
• setiap $J_n$ tutup, tak kosong, dan terbatas, dengan panjang $\tfrac{b-a}{3^{n+1}}>0$;
• $x_n\notin J_n$.

Teorema 12.2.4 (setelah pergeseran indeks seperti pada Unit 14.3) memberi $p$ di semua $J_n$. Untuk setiap $n$, $p\in J_n$ dan $x_n\notin J_n$, sehingga $p\ne x_n$. Juga $p\in J_0\subseteq[a,b]$. $\square$

Akibat 22.2.3

Setiap interval $[a,b]$ dengan $a<b$ tak terhitung, dan demikian pula $(a,b)$, $[a,b)$, $(a,b]$, sinar, dan $\mathbb{R}$.

Bukti. Untuk $[a,b]$, Teorema 22.2.2: tidak ada barisan yang memuat semua anggotanya. Interval terbuka $(a,b)$ memuat $[a+\tfrac{b-a}4,b-\tfrac{b-a}4]$, yang tak terhitung, sehingga $(a,b)$ tak terhitung (Latihan 22.1-8). Bentuk lain memuat suatu interval tutup tak degenerat. $\square$

Bukti kedua memperlihatkan peran kelengkapan. Di $\mathbb{Q}$, interval bersarang dapat beririsan kosong (Contoh 12.2.12, Latihan 12.3-8), dan memang $\mathbb{Q}\cap[0,1]$ terhitung. Ketakterhitungan $\mathbb{R}$ adalah gejala kelengkapan, sama seperti keberadaan $\sqrt2$.

Bijeksi Antarinterval dan dengan $\mathbb{R}$

Proposisi 22.2.4

(a) Untuk $a<b$, $t\mapsto a+(b-a)t$ adalah bijeksi $(0,1)\to(a,b)$.

(b) $\phi(x)=\dfrac x{1+|x|}$ adalah bijeksi $\mathbb{R}\to(-1,1)$, dengan invers $\psi(y)=\dfrac y{1-|y|}$.

Bukti. (a) Fungsi naik tegas, karena $b-a>0$, dengan invers $s\mapsto\tfrac{s-a}{b-a}$. Peta $(0,1)$ adalah $(a,b)$ menurut translasi dan penskalaan urutan.

(b) $|\phi(x)|=\tfrac{|x|}{1+|x|}<1$, karena $|x|<1+|x|$ dan penyebutnya positif. Jadi $\phi$ bernilai di $(-1,1)$. Untuk $y\in(-1,1)$, $1-|y|>0$, sehingga $\psi(y)$ terdefinisi.

Periksa $\phi(\psi(y))=y$. Tulis $x=\psi(y)$. Karena $x$ dan $y$ bertanda sama (penyebut positif), $|x|=\tfrac{|y|}{1-|y|}$, dan $1+|x|=\tfrac1{1-|y|}$. Maka $\phi(x)=x(1-|y|)=y$.

Periksa $\psi(\phi(x))=x$. Dengan $y=\phi(x)$, $|y|=\tfrac{|x|}{1+|x|}$ dan $1-|y|=\tfrac1{1+|x|}$, sehingga $\psi(y)=y(1+|x|)=x$.

Kedua komposisi identitas, sehingga $\phi$ bijeksi (Bab 5). $\square$

Jadi $\mathbb{R}$, seluruh garis yang tak terbatas, berbijeksi dengan interval terbatas $(-1,1)$, dan karenanya dengan $(0,1)$ lewat (a). Panjang tidak mempengaruhi kardinalitas. Bab 23 merumuskan "berbijeksi" sebagai kesetaraan kardinalitas, dan Teorema Schröder–Bernstein akan memberi juga $[0,1]\sim(0,1)$ tanpa bijeksi eksplisit.

Akibat-Akibat

Akibat 22.2.5

(a) $\mathbb{R}\setminus\mathbb{Q}$ tak terhitung, dan setiap interval tak degenerat memuat tak terhitung banyak bilangan irasional.

(b) Ada bilangan real transenden.

Bukti. (a) Bila $(a,b)\setminus\mathbb{Q}$ terhitung, maka $(a,b)=\bigl((a,b)\cap\mathbb{Q}\bigr)\cup\bigl((a,b)\setminus\mathbb{Q}\bigr)$ terhitung (Teorema 21.3.1), bertentangan dengan Akibat 22.2.3. Ini memperkuat Teorema 11.4.8, yang hanya memberi tak hingga banyak.

(b) Bilangan aljabar terhitung (Contoh 21.3.4(c)), sedangkan $\mathbb{R}$ tidak. $\square$

Latihan

Latihan 22.2-1. Untuk daftar $x_0=0{,}5$, $x_1=\tfrac13$, $x_2=\tfrac{\sqrt2}2$ (cukup tiga digit pertama), tentukan tiga digit pertama $e_1,e_2,e_3$ dari bilangan diagonal $y$. Ekspansi kanonik: $0{,}5=0{,}5000\ldots$, $\tfrac13=0{,}333\ldots$, $\tfrac{\sqrt2}2=0{,}707\ldots$.

Latihan 22.2-2. Buktikan bahwa string $0{,}555\ldots$ bernilai $\tfrac59$, dengan cara seperti Proposisi 12.4.11, lalu simpulkan bahwa bilangan diagonal $y$ pada Teorema 22.2.1 kurang dari $1$.

Latihan 22.2-3. Jelaskan dengan contoh mengapa aturan "$e_k=d_k+1$ bila $d_k\leq8$, dan $e_k=0$ bila $d_k=9$" dapat gagal menghasilkan bilangan baru.

Latihan 22.2-4. Untuk $x_n=\tfrac1{n+2}$ dan $[a,b]=[0,1]$, jalankan dua langkah pertama konstruksi Teorema 22.2.2 dan tuliskan $J_0$ dan $J_1$.

Latihan 22.2-5. Buktikan bahwa $[0,1]$, $[0,1)$, dan $(0,\infty)$ tak terhitung.

Latihan 22.2-6. Hitung $\phi(3)$, $\phi(-1)$, $\psi(\tfrac12)$, dan $\psi(-\tfrac34)$ untuk Proposisi 22.2.4(b). Tuliskan bijeksi eksplisit $\mathbb{R}\to(0,1)$.

Latihan 22.2-7. Buktikan bahwa himpunan $C$ yang berisi bilangan di $[0,1]$ yang ekspansi desimal kanoniknya (setelah koma) hanya memakai digit $4$ dan $5$ adalah tak terhitung.

Latihan 22.2-8. Buktikan bahwa jika $A\subseteq\mathbb{R}$ terhitung, maka $\mathbb{R}\setminus A$ rapat di $\mathbb{R}$: setiap interval $(u,v)$ dengan $u<v$ memuat titik di luar $A$.

Solusi

Solusi 22.2-1. $d_1(x_0)=5$, sehingga $e_1=4$. $d_2(x_1)=3\ne5$, sehingga $e_2=5$. $d_3(x_2)$: $0{,}707<\tfrac{\sqrt2}2<0{,}708$, karena $0{,}707^2=0{,}499849<\tfrac12<0{,}501264=0{,}708^2$ dan kuadrat naik tegas pada bilangan positif. Dengan Proposisi 12.4.4 dan ketunggalan ekspansi kanonik, tiga digit pertamanya $7,0,7$, sehingga digit ketiganya $7\ne5$ dan $e_3=5$. Jadi $y=0{,}455\ldots$. $y\ne x_0$, karena digit pertama $4$ dan $5$ berbeda dan ekspansinya kanonik. $\square$

Solusi 22.2-2. $s_n=\sum_{k=1}^n5\cdot10^{-k}=\tfrac59(1-10^{-n})$, dengan identitas teleskopik Lemma 12.4.2 dikalikan $\tfrac59$. Supremumnya $\tfrac59$, dengan argumen Proposisi 12.4.11. Untuk bilangan diagonal, $e_k\leq5$, sehingga setiap pemotongannya paling banyak pemotongan $0{,}555\ldots$, dan $y\leq\tfrac59<1$. $\square$

Solusi 22.2-3. Aturan itu dapat menghasilkan digit $9$ terus-menerus. Bila setiap $d_k(x_{k-1})=8$, misalnya $x_n=0{,}888\ldots$ untuk semua $n$, maka $e_k=9$ untuk semua $k$ dan $y=0{,}999\ldots=1\notin(0,1)$. String diagonal itu tidak kanonik, dan bilangannya keluar dari interval. $\square$

Solusi 22.2-4. $J_0'=[0,1]$ dan $x_0=\tfrac12$. $L=[0,\tfrac13]$ tidak memuat $\tfrac12$, sehingga $J_0=[0,\tfrac13]$. Langkah berikutnya dengan $x_1=\tfrac13$: $L=[0,\tfrac19]$ tidak memuat $\tfrac13$, sehingga $J_1=[0,\tfrac19]$. Konstruksi ini terus memilih sepertiga kiri, dan $p=0$, yang memang tidak berada dalam daftar $\{\tfrac1{n+2}\}$. $\square$

Solusi 22.2-5. Akibat 22.2.3. $(0,\infty)\supseteq(0,1)$. $\square$

Solusi 22.2-6. $\phi(3)=\tfrac34$. $\phi(-1)=-\tfrac12$. $\psi(\tfrac12)=\tfrac{1/2}{1/2}=1$. $\psi(-\tfrac34)=\tfrac{-3/4}{1/4}=-3$. Bijeksi $\mathbb{R}\to(0,1)$: $x\mapsto\tfrac12(\phi(x)+1)$, yaitu komposisi $\phi$ dengan bijeksi $s\mapsto\tfrac{s+1}2$ dari $(-1,1)$ ke $(0,1)$, yang naik tegas dengan invers $t\mapsto2t-1$. $\square$

Solusi 22.2-7. Pemetaan dari $\{0,1\}^{\mathbb{N}_{+}}$ ke $C$ yang mengirim barisan $(b_k)$ ke nilai string $0{,}(4+b_1)(4+b_2)\ldots$ adalah injeksi. String-string itu kanonik, sehingga barisan yang berbeda memberi bilangan berbeda (Korolari 12.4.10), dan nilainya di $C$. Karena $\{0,1\}^{\mathbb{N}_{+}}$ tak terhitung (Teorema 22.1.2, dengan indeks digeser), $C$ tak terhitung (Latihan 21.1-8). $\square$

Solusi 22.2-8. $(u,v)$ tak terhitung (Akibat 22.2.3). Bila $(u,v)\subseteq A$, maka $(u,v)$ terhitung (Akibat 21.1.4(a)), kontradiksi. $\square$

Ringkasan

$(0,1)$ tak terhitung, dibuktikan dua kali. Bukti pertama memakai diagonal desimal, dengan digit $4$ dan $5$ agar string diagonal kanonik, dan ketunggalan bentuk kanonik dari Unit 12.4. Bukti kedua memakai interval bersarang sepertiga tanpa desimal, dan memperlihatkan bahwa ketakterhitungan adalah gejala kelengkapan. Setiap interval tak degenerat dan $\mathbb{R}$ tak terhitung. Bijeksi aljabar $x\mapsto\tfrac x{1+|x|}$ memasangkan $\mathbb{R}$ dengan $(-1,1)$. Bilangan irasional dan bilangan transenden tak terhitung banyaknya. Unit 22.3 mengabstraksikan argumen diagonal menjadi Teorema Cantor.

22.3 Teorema Cantor: Kuasa Himpunan Kuasa Selalu Lebih Besar

Argumen diagonal pada Unit 22.1 menunjukkan bahwa barisan biner terlalu banyak untuk dicacah oleh $\mathbb{N}$. Unit ini mengabstraksikan argumen itu: untuk setiap himpunan $A$, himpunan kuasanya $\mathcal{P}(A)$, yaitu himpunan semua subhimpunan $A$, selalu "lebih besar" daripada $A$. Untuk himpunan berhingga dengan $n$ anggota, $\mathcal{P}(A)$ mempunyai $2^n$ anggota. Contoh master: $3$ anggota memberi $2^3=8$ subhimpunan. Teorema Cantor menyatakan bahwa ketaksamaan $|\mathcal{P}(A)|>|A|$ tetap berlaku untuk himpunan tak hingga. Akibatnya tidak ada "ketakhinggaan terbesar": $\mathbb{N}$, $\mathcal{P}(\mathbb{N})$, $\mathcal{P}(\mathcal{P}(\mathbb{N}))$, dan seterusnya, makin lama makin besar.

Untuk menyatakan "lebih besar" secara tepat tanpa mendahului Bab 23, unit ini memakai bahasa fungsi: $|A|\leq|B|$ berarti ada injeksi $A\to B$, dan $|A|<|B|$ berarti ada injeksi tetapi tidak ada bijeksi. Teori kardinal yang lengkap, termasuk sifat antisimetri (Schröder–Bernstein), dibahas pada Bab 23.

Prasyarat: Unit 22.1; Bab 20 (himpunan hingga, Teorema 20.1.9); himpunan kuasa dan separasi (Bab 3); fungsi (Bab 5).

Himpunan Kuasa Himpunan Berhingga

Teorema 22.3.1

Jika $A$ hingga dengan $|A|=n$, maka $\mathcal{P}(A)$ hingga dengan $|\mathcal{P}(A)|=2^n$.

Bukti. Induksi pada $n$.

Basis $n=0$: $\mathcal{P}(\emptyset)=\{\emptyset\}$, dengan kardinalitas $1=2^0$.

Langkah: misalkan $|A|=n+1$, ambil $a\in A$, dan tulis $A'=A\setminus\{a\}$ dengan $|A'|=n$ (Teorema 20.1.9(a)). Subhimpunan $A$ terbagi dua secara saling lepas: yang tidak memuat $a$, yaitu tepat $\mathcal{P}(A')$, dan yang memuat $a$, yaitu $\{S\cup\{a\}:S\in\mathcal{P}(A')\}$. Pemetaan $S\mapsto S\cup\{a\}$ adalah bijeksi $\mathcal{P}(A')\to$ bagian kedua, dengan invers $T\mapsto T\setminus\{a\}$. Hipotesis induksi dan Teorema 20.1.9(a) memberi $|\mathcal{P}(A)|=2^n+2^n=2^{n+1}$. $\square$

Contoh 22.3.2 (Contoh Master)

Untuk $A=\{a,b,c\}$, kedelapan subhimpunannya adalah $\emptyset$, $\{a\}$, $\{b\}$, $\{c\}$, $\{a,b\}$, $\{a,c\}$, $\{b,c\}$, dan $\{a,b,c\}$. Jadi $2^3=8$. Dengan bukti di atas: subhimpunan $\{a,b\}$ ada $4$, dan setiap subhimpunan $\{a,b,c\}$ adalah salah satunya atau salah satunya ditambah $c$.

Untuk setiap $n\in\mathbb{N}$, $n<2^n$ (induksi: $0<1$; jika $n<2^n$, maka $n+1\leq2^n<2^n+2^n=2^{n+1}$). Jadi untuk himpunan berhingga, $|\mathcal{P}(A)|>|A|$ sudah terlihat dari hitungan.

Teorema Cantor

Teorema 22.3.3 (Cantor)

Untuk setiap himpunan $A$, tidak ada surjeksi $A\to\mathcal{P}(A)$.

Bukti. Misalkan $F:A\to\mathcal{P}(A)$ sebarang. Definisikan dengan separasi

Andaikan $D=F(d)$ untuk suatu $d\in A$. Bila $d\in D$, maka menurut definisi $D$, $d\notin F(d)=D$, kontradiksi. Bila $d\notin D=F(d)$, maka $d$ memenuhi syarat keanggotaan $D$, sehingga $d\in D$, kontradiksi. Kedua kemungkinan mustahil, sehingga $D$ tidak berada dalam peta $F$. $\square$

Ini adalah argumen diagonal dalam bentuk abstrak. Bandingkan dengan Teorema 22.1.2. Bila $A=\mathbb{N}$ dan subhimpunan $S\subseteq\mathbb{N}$ dikodekan sebagai barisan biner, dengan $s_k=1$ tepat bila $k\in S$, maka $D$ dikodekan oleh $d_k=1-F(k)_k$, persis barisan diagonal. Himpunan $D$ "berbeda dari $F(a)$ pada unsur $a$" untuk setiap $a$.

Akibat 22.3.4 ($|A|<|\mathcal{P}(A)|$)

Untuk setiap himpunan $A$:

(a) $a\mapsto\{a\}$ adalah injeksi $A\to\mathcal{P}(A)$, sehingga $|A|\leq|\mathcal{P}(A)|$;

(b) tidak ada bijeksi $A\to\mathcal{P}(A)$, sehingga $|A|<|\mathcal{P}(A)|$.

Bukti. (a) $\{a\}=\{a'\}$ memberi $a=a'$ (Bab 3). (b) Bijeksi adalah surjeksi, sehingga Teorema 22.3.3 berlaku. $\square$

Hubungan dengan $\mathbb{N}$ dan $\mathbb{R}$

Proposisi 22.3.5

(a) $\chi:\mathcal{P}(\mathbb{N})\to\{0,1\}^{\mathbb{N}}$, yang mengirim $S$ ke fungsi indikatornya $\chi_S(k)=1$ untuk $k\in S$ dan $\chi_S(k)=0$ untuk $k\notin S$, adalah bijeksi.

(b) $\mathcal{P}(\mathbb{N})$ tak terhitung.

Bukti. (a) Inversnya $s\mapsto\{k:s_k=1\}$, yang terdefinisi dengan separasi. Kedua komposisi adalah identitas: subhimpunan ditentukan oleh anggotanya (ekstensionalitas), dan barisan ditentukan oleh nilainya.

(b) Teorema 22.3.3 dengan $A=\mathbb{N}$, atau (a) bersama Teorema 22.1.2. $\square$

Hubungan $\mathcal{P}(\mathbb{N})$ dengan $\mathbb{R}$: pemetaan $S\mapsto$ nilai string desimal $0{,}c_1c_2\ldots$ dengan $c_k=4+\chi_S(k-1)$ adalah injeksi $\mathcal{P}(\mathbb{N})\to(0,1)$ (Solusi 22.2-7). Arah sebaliknya, injeksi $(0,1)\to\mathcal{P}(\mathbb{Q})$, diberikan oleh $x\mapsto\{q\in\mathbb{Q}:q<x\}$. Fungsi ini injektif karena kerapatan $\mathbb{Q}$: jika $x<y$, ada rasional di antara keduanya, dan rasional itu termasuk himpunan untuk $y$ tetapi tidak untuk $x$. Lalu $\mathcal{P}(\mathbb{Q})$ berbijeksi dengan $\mathcal{P}(\mathbb{N})$ lewat pencacahan $\mathbb{Q}$. Dengan Teorema Schröder–Bernstein (Bab 23.2), kedua injeksi ini akan memberi bijeksi $\mathbb{R}\sim\mathcal{P}(\mathbb{N})$.

Hierarki Tak Hingga

Dengan menerapkan Akibat 22.3.4 berulang kali:

Setiap langkah memberi himpunan yang tidak dapat dipasangkan secara bijektif dengan himpunan sebelumnya, sedangkan injeksi ke arah naik selalu ada. Tidak ada himpunan yang "paling besar". Akibat logis yang penting: tidak ada himpunan $V$ yang memuat semua himpunan. Seandainya ada, $\mathcal{P}(V)\subseteq V$, karena setiap anggota $\mathcal{P}(V)$ adalah himpunan. Fungsi $F:V\to\mathcal{P}(V)$ dengan $F(x)=x$ bila $x\subseteq V$ (selalu benar, karena semua anggota $x$ adalah himpunan) akan surjektif, bertentangan dengan Teorema 22.3.3. Himpunan $D$ dalam bukti Cantor untuk $F$ ini adalah $\{x\in V:x\notin x\}$, yaitu himpunan Russell. Penalaran ini selaras dengan cara teori himpunan aksiomatik (Bab 3) menolak "himpunan semua himpunan".

Latihan

Latihan 22.3-1. Tuliskan semua subhimpunan $\{1,2\}$ dan $\{1,2,3,4\}$ yang memuat $1$. Berapa banyaknya, dan bagaimana hubungannya dengan bukti Teorema 22.3.1?

Latihan 22.3-2. Buktikan $n<2^n$ untuk semua $n\in\mathbb{N}$, dan $2^n\leq n!$ untuk $n\geq4$.

Latihan 22.3-3. Untuk $A=\{1,2,3\}$ dan $F(1)=\{1,2\}$, $F(2)=\emptyset$, $F(3)=\{1,3\}$, tentukan $D$ pada bukti Teorema Cantor dan periksa bahwa $D\ne F(a)$ untuk setiap $a$.

Latihan 22.3-4. Untuk $F:\mathbb{N}\to\mathcal{P}(\mathbb{N})$ dengan $F(n)=\{k\in\mathbb{N}:k\geq n\}$, tentukan $D$.

Latihan 22.3-5. Buktikan Proposisi 22.3.5(a) secara lengkap.

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

Latihan 22.3-7. Buktikan bahwa $x\mapsto\{q\in\mathbb{Q}:q<x\}$ adalah injeksi $\mathbb{R}\to\mathcal{P}(\mathbb{Q})$. Di mana kerapatan $\mathbb{Q}$ dipakai?

Latihan 22.3-8. Buktikan bahwa tidak ada surjeksi $A\to\{0,1\}^A$ untuk setiap himpunan $A$, dengan meniru Teorema 22.1.2, tanpa memakai himpunan kuasa.

Solusi

Solusi 22.3-1. Untuk $\{1,2\}$: $\{1\}$ dan $\{1,2\}$, yaitu $2=2^1$. Untuk $\{1,2,3,4\}$: subhimpunan $\{2,3,4\}$ ditambah $1$, sebanyak $2^3=8$. Ini bagian kedua dalam bukti, yang berbijeksi dengan $\mathcal{P}(A')$. $\square$

Solusi 22.3-2. $n<2^n$: Contoh 22.3.2. $2^n\leq n!$ untuk $n\geq4$: basis $16\leq24$; langkah $2^{n+1}=2\cdot2^n\leq2\cdot n!\leq(n+1)\,n!=(n+1)!$, karena $2\leq n+1$. $\square$

Solusi 22.3-3. $1\in F(1)$, sehingga $1\notin D$. $2\notin F(2)=\emptyset$, sehingga $2\in D$. $3\in F(3)$, sehingga $3\notin D$. Jadi $D=\{2\}$. Periksa: $D\ne\{1,2\}$, $D\ne\emptyset$, dan $D\ne\{1,3\}$. $\square$

Solusi 22.3-4. $n\in F(n)$, karena $n\geq n$. Jadi $D=\emptyset$, dan memang $\emptyset\ne F(n)$ untuk setiap $n$, karena $n\in F(n)$. $\square$

Solusi 22.3-5. Lihat bukti Proposisi 22.3.5(a): $\chi_{\{k:s_k=1\}}=s$ dan $\{k:\chi_S(k)=1\}=S$. $\square$

Solusi 22.3-6. Subhimpunan hingga dari $\mathbb{N}$ terhitung (Latihan 21.3-6). Bila subhimpunan tak hingga juga terhitung, $\mathcal{P}(\mathbb{N})$ akan terhitung (Teorema 21.3.1), bertentangan dengan Proposisi 22.3.5(b). $\square$

Solusi 22.3-7. Jika $x<y$, kerapatan (Teorema 11.3.11) memberi $q$ dengan $x<q<y$. Maka $q$ termasuk himpunan untuk $y$ dan tidak termasuk himpunan untuk $x$, sehingga himpunannya berbeda. Kerapatan dipakai tepat di langkah itu. $\square$

Solusi 22.3-8. Untuk $F:A\to\{0,1\}^A$, definisikan $d(a)=1-F(a)(a)$. Maka $d(a)\ne F(a)(a)$ untuk setiap $a$, sehingga $d\ne F(a)$. Bukti ini setara dengan Teorema 22.3.3 lewat fungsi indikator. $\square$

Ringkasan Unit 22.3 dan Penutup Bab 22

Himpunan berhingga dengan $n$ anggota mempunyai $2^n$ subhimpunan; contoh master $2^3=8$. Teorema Cantor: tidak ada surjeksi dari $A$ ke $\mathcal{P}(A)$, dengan himpunan diagonal $D=\{a:a\notin F(a)\}$ sebagai saksinya. Jadi $|A|<|\mathcal{P}(A)|$ untuk setiap $A$, berhingga atau tidak. $\mathcal{P}(\mathbb{N})$ berbijeksi dengan barisan biner dan tak terhitung. Hierarki ketakhinggaan tidak mempunyai puncak, dan tidak ada himpunan semua himpunan.

Bab 22 secara keseluruhan:

• 22.1: argumen diagonal;
• 22.2: $(0,1)$ dan $\mathbb{R}$ tak terhitung, dengan dua bukti;
• 22.3: Teorema Cantor.

Bab 23 merumuskan teori kardinalitas: kesetaraan, Schröder–Bernstein, dan aksioma pilihan.