Kasus khusus

Bagian ini akan menggunakan kasus spesifik ketika ${\displaystyle H}$ merupakan himpunan terhitung tak terhingga. Tanpa mengurangi keumuman, akan digunakan himpunan ${\displaystyle H=\mathbb {N} =\left\{1,\,2,\,3,\,4,\,\ldots \right\}}$, yaitu himpunan semua bilangan asli.

Misalkan himpunan ${\displaystyle \mathbb {N} }$ sama banyaknya dengan himpunan kuasanya, ${\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}$. Himpunan ${\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}$ memuat tak terhingga banyaknya himpunan bagian dari ${\displaystyle \mathbb {N} }$, seperti himpunan bilangan genap positif ${\displaystyle \left\{2,\,4,\,6,\,8,\,\ldots \right\}=\left\{2n\mid n\in \mathbb {N} \right\}}$ dan himpunan kosong ${\displaystyle \varnothing }$. Beberapa himpunan yang termuat pada ${\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}$ antara lain: $${\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)=\left\{\varnothing ,\,\left\{1,\,2\right\},\,\left\{1,\,2,\,3\right\},\,\left\{4\right\},\,\left\{1,\,5\right\},\,\left\{3,\,4,\,6\right\},\,\left\{2,\,4,\,6,\,8,\,\ldots \right\},\,\ldots \right\}}$$

Oleh karena ${\displaystyle \mathbb {N} }$ diasumsikan sama banyaknya dengan ${\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}$, maka setiap elemen dari ${\displaystyle \mathbb {N} }$ dapat melabeli setiap elemen dari ${\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}$, dengan syarat tidak ada elemen dari kedua himpunan yang tidak terlabeli. Salah satu cara pelabelannya adalah sebagai berikut: $${\displaystyle \mathbb {N} \,{\begin{Bmatrix}1&\longleftrightarrow &\left\{4,\,5\right\}\\2&\longleftrightarrow &\left\{1,\,2,\,3\right\}\\3&\longleftrightarrow &\left\{4,\,5,\,6\right\}\\4&\longleftrightarrow &\left\{1,\,3,\,5\right\}\\\vdots &\vdots &\vdots \end{Bmatrix}}\,{\mathcal {P}}\!\left(\mathbb {N} \right)}$$ Diberikan suatu proses pelabelan, beberapa bilangan asli melabelkan himpunan bagian yang memuat dirinya sendiri. Misalnya, pada contoh di atas, bilangan ${\displaystyle 2}$ melabelkan himpunan ${\displaystyle \left\{1,\,2,\,3\right\}}$, yang memuat ${\displaystyle 2}$ sebagai anggotanya. Misalkan bilangan-bilangan tersebut disebut egois. Beberapa bilangan asli lainnya melabelkan himpunan bagian yang tidak memuat dirinya sendiri. Misalnya, pada contoh di atas, bilangan ${\displaystyle 1}$ melabelkan himpunan ${\displaystyle \left\{4,\,5\right\}}$, yang tidak memuat ${\displaystyle 1}$ sebagai anggotanya.

Dengan menggunakan ide ini, maka dapat dikonstruksikan suatu himpunan bilangan asli yang istimewa. Himpunan ini akan memberikan kontradiksi yang sedang diincar. Misalkan ${\displaystyle {\cancel {E}}}$ adalah himpunan semua bilangan yang tidak egois. Berdasarkan definisi, himpunan kuasa ${\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}$ memuat semua himpunan bilangan asli, yang mengakibatkan ${\displaystyle {\cancel {E}}\in {\mathcal {P}}\!\left(\mathbb {N} \right)}$. Jika pemetaannya bersifat bijektif, maka ${\displaystyle {\cancel {E}}}$ harus dilabelkan dengan suatu bilangan asli, misalnya ${\displaystyle e}$. Akan tetapi, hal ini menimbulkan masalah.

1. Jika ${\displaystyle e\in {\cancel {E}}}$, maka ${\displaystyle e}$ merupakan bilangan egois, dan hal ini bertentangan dengan definisi dari ${\displaystyle {\cancel {E}}}$.
2. Jika ${\displaystyle e\not \in {\cancel {E}}}$, maka ${\displaystyle e}$ adalah bilangan yang tidak egois, sehingga ${\displaystyle e}$ seharusnya menjadi anggota dari ${\displaystyle {\cancel {E}}}$.

Akibatnya, tidak mungkin ada elemen ${\displaystyle e}$ yang dipetakan ke ${\displaystyle {\cancel {E}}}$.

Oleh karena tidak ada bilangan asli yang melabelkan himpunan ${\displaystyle {\cancel {E}}}$, maka pengandaian di awal bernilai salah, yaitu terdapat bijeksi antara ${\displaystyle \mathbb {N} }$ dan ${\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}$.

Perhatikan bahwa himpunan ${\displaystyle {\cancel {E}}}$ mungkin saja kosong. Hal ini mengakibatkan setiap bilangan asli ${\displaystyle n}$ dipetakan ke himpunan bagian yang memuat ${\displaystyle n}$. Dengan kata lain, setiap bilangan asli melabelkan suatu himpunan tak kosong dan tidak ada bilangan yang melabelkan himpunan kosong. Akan tetapi, ${\displaystyle \varnothing \in {\mathcal {P}}\!\left(\mathbb {N} \right)}$, sehingga pemetaannya tetap tidak meliput ${\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}$.

Berdasarkan pembuktian melalui kontradiksi ini, terbukti bahwa ${\displaystyle \left|\mathbb {N} \right|\neq \left|{\mathcal {P}}\!\left(\mathbb {N} \right)\right|}$. Selain itu, ${\displaystyle \left|\mathbb {N} \right|>\left|{\mathcal {P}}\!\left(\mathbb {N} \right)\right|}$ juga tidaklah mungkin, sebab berdasarkan definisi, ${\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}$ memuat semua singleton, dan singleton-singleton ini membentuk "salinan" dari ${\displaystyle \mathbb {N} }$ di dalam ${\displaystyle {\mathcal {P}}\!\left(\mathbb {N} \right)}$. Akibatnya, hanya tersisa satu kemungkinan, yaitu $${\displaystyle \left|\mathbb {N} \right|<\left|{\mathcal {P}}\!\left(\mathbb {N} \right)\right|}$$

Kasus umum

Argumen Cantor terbilang elegan dan sangat sederhana. Bukti lengkapnya disajikan dibawah, beserta penjelasan rinci setelahnya.

Misalkan ${\displaystyle X}$ dan ${\displaystyle Y}$ adalah sembarang himpunan. Berdasarkan definisi dari kardinalitas, maka ${\displaystyle \left|X\right|<\left|Y\right|}$ jika dan hanya jika terdapat suatu fungsi injektif tetapi tidak bijektif dari ${\displaystyle X}$ ke ${\displaystyle Y}$. Hal ini dapat diraih dengan menunjukkan bahwa tidak ada pemetaan surjektif dari ${\displaystyle X}$ ke ${\displaystyle Y}$. Inilah inti dari teorema Cantor: tidak ada fungsi surjektif dari sembarang himpunan ${\displaystyle H}$ ke himpunan kuasanya. Untuk membuktikan ini, maka cukup dengan menunjukkan bahwa tidak ada fungsi ${\displaystyle f}$ (yang memetakan elemen pada ${\displaystyle H}$ ke himpunan bagian dari ${\displaystyle H}$) yang dapat meraih setiap himpunan bagian yang ada. Dengan kata lain, maka cukup ditunjukkan bahwa terdapat suatu himpunan bagian dari ${\displaystyle H}$ yang tidak sama dengan ${\displaystyle f\!\left(x\right)}$, untuk setiap ${\displaystyle x\in H}$. Ingat kembali bahwa setiap ${\displaystyle f\!\left(x\right)}$ merupakan himpunan bagian dari ${\displaystyle H}$. Himpunan bagian dengan sifat tersebut diberikan melalui konstruksi berikut: $${\displaystyle {\cancel {H}}=\left\{x\in H\mid x\not \in f\!\left(x\right)\right\}}$$ Himpunan ${\displaystyle {\cancel {H}}}$ terkadang dikenal sebagai himpunan diagonal Cantor dari ${\displaystyle f}$. Berdasarkan definisi dari himpunan ${\displaystyle {\cancel {H}}}$, maka untuk setiap ${\displaystyle x\in H}$, ${\displaystyle x\in {\cancel {H}}}$ jika dan hanya jika ${\displaystyle x\not \in f\!\left(x\right)}$. Akan dikaji dua kasus berikut:

1. Jika ${\displaystyle x\in f\!\left(x\right)}$, maka ${\displaystyle x\not \in {\cancel {H}}}$, sehingga ${\displaystyle f\!\left(x\right)\neq {\cancel {H}}}$.
2. Jika ${\displaystyle x\not \in f\!\left(x\right)}$, maka ${\displaystyle x\in {\cancel {H}}}$, sehingga ${\displaystyle f\!\left(x\right)\neq {\cancel {H}}}$.

Berdasarkan kedua kasus di atas, himpunan ${\displaystyle f\!\left(x\right)\neq {\cancel {H}}}$ untuk setiap ${\displaystyle x\in H}$ sebab himpunan ${\displaystyle {\cancel {H}}}$ dikonstruksikan dari elemen pada ${\displaystyle H}$ yang bayangan oleh fungsi ${\displaystyle f}$ tidak memuat dirinya sendiri. Dengan kata lain, terbukti bahwa terdapat suatu elemen ${\displaystyle c\in H}$ sedemikian sehingga persyaratan ${\displaystyle f\!\left(c\right)=B}$ mengakibatkan kontradiksi berikut: $${\displaystyle {\begin{aligned}c\in {\cancel {H}}&\iff c\not \in f\!\left(c\right)&&{\text{(berdasarkan definisi dari }}{\cancel {H}}{\text{)}}\\c\in {\cancel {H}}&\iff c\in f\!\left(c\right)&&{\text{(berdasarkan asumsi bahwa }}f\!\left(x\right)={\cancel {H}}{\text{)}}\\\end{aligned}}}$$ sehingga berdasarkan reductio ad absurdum, asumsi di awal bernilai salah.^[1] Akibatnya, tidak ada ${\displaystyle c\in H}$ yang memenuhi ${\displaystyle f\!\left(c\right)={\cancel {H}}}$. Dengan kata lain, himpunan ${\displaystyle {\cancel {H}}}$ bukanlah bayangan dari ${\displaystyle f}$ dan fungsi ${\displaystyle f}$ tidak memetakan setiap elemen ke himpunan kuasa dari ${\displaystyle H}$, yang berarti, ${\displaystyle f}$ tidak bersifat surjektif.

Terakhir, untuk melengkapi pembuktiannya, perlu ditunjukkan bahwa terdapat suatu fungsi injektif dari ${\displaystyle H}$ ke himpunan kuasanya. Proses mencari fungsi tersebut tidaklah sulit: petakan elemen ${\displaystyle x}$ ke himpunan singleton ${\displaystyle \left\{x\right\}}$. Sekarang pembuktiannya sudah lengkap, dan berlaku ketaksamaan tegas ${\displaystyle \left|H\right|<\left|{\mathcal {P}}\!\left(H\right)\right|}$ untuk setiap himpunan ${\displaystyle H}$.

Oleh karena elemen ${\displaystyle x}$ muncul dua kali pada ekspresi "${\displaystyle x\in f\!\left(x\right)}$", maka argumen ini disebut sebagai argument diagonal. Untuk himpunan terhitung (atau berhingga), argumentasi dari pembuktian di atas dapat diilustrasikan dengan membuat tabel yang

1. setiap barisnya dilabeli oleh suatu elemen ${\displaystyle x}$ dari himpunan ${\displaystyle H=\left\{x_{1},\,x_{2},\,x_{3},\,\ldots \right\}}$ secara berurutan. Himpunan ${\displaystyle H}$ diasumsikan terurut linear sehingga tabelnya dapat dikonstruksikan.
2. setiap kolomnya dilabelkan oleh suatu elemen ${\displaystyle y}$ dari himpunan ${\displaystyle {\mathcal {P}}\!\left(H\right)}$. Kolomnya diurutkan berdasarkan argumen dari ${\displaystyle f}$. Dengan kata lain, kolomnya dilabeli sebagai ${\displaystyle f\!\left(x_{1}\right)\!,\,f\!\left(x_{2}\right)\!,\,f\!\left(x_{3}\right)\!,\,\ldots }$ dengan urutan ini.
3. perpotongan dari setiap baris ${\displaystyle x}$ dan kolom ${\displaystyle y}$ berisi nilai benar/salah dari pernyataan ${\displaystyle x\in y}$. Dengan kata lain, setiap baris berisi nilai fungsi indikator dari himpunan pada masing-masing kolom.

Diberikan suatu urutan yang dipilih untuk label baris dan kolom, diagonal utama ${\displaystyle D}$ dari tabel ini berisi nilai kebenaran dari pernyataan ${\displaystyle x\in f\!\left(x\right)}$ untuk setiap ${\displaystyle x\in H}$. Salah satu tabelnya dapat dilihat sebagai berikut: $${\displaystyle {\begin{array}{c|ccccc}&f(x_{1})&f(x_{2})&f(x_{3})&f(x_{4})&\cdots \\\hline x_{1}&{\color {red}B}&B&S&B&\cdots \\x_{2}&B&{\color {red}S}&S&S&\cdots \\x_{3}&S&S&{\color {red}B}&B&\cdots \\x_{4}&S&B&B&{\color {red}B}&\cdots \\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots \end{array}}}$$ Himpunan ${\displaystyle {\cancel {H}}}$ pada paragraf sebelumnya dikonstruksikan berdasarkan negasi dari nilai kebenaran pada diagonal utama ${\displaystyle D}$ (yang pada contoh di atas, diwarnai dengan merah), yaitu menukar "benar" dan "salah".^[1] Akibatnya, fungsi indikator dari himpunan ${\displaystyle {\cancel {H}}}$ akan berbeda dengan setiap kolom pada setidaknya satu entri, sehingga tidak ada kolom yang mewakili ${\displaystyle {\cancel {H}}}$.