Himpunan terhitung

Keterhitungan himpunan adalah semacam pengganti ukuran himpunan. Pada himpunan tak hingga, kita tidak bisa bekerja dengan banyaknya anggota, karena banyaknya anggota ternyata… tak hingga. Ukuran himpunan juga disebut kardinalitas.

Ukuran himpunan tak hingga

Menentukan ukuran himpunan berhingga itu mudah: kita hitung banyak anggotanya. Jadi, himpunan M = {a, b, c, d, e} berukuran 5, ditulis |M| = 5.

Pada himpunan tak hingga, keadaannya jauh lebih rumit. Bagaimana kita bisa membandingkan ukuran himpunan-himpunan tak hingga? Apakah hal itu mungkin, atau semua himpunan tak hingga “sama besar”?

Sebagai contoh, ambil himpunan bilangan asli dan himpunan bilangan asli genap. Kita peroleh himpunan ℕ = {1, 2, 3, 4, 5, 6, …} dan S = {2, 4, 6, …}. Rasanya ingin dikatakan bahwa himpunan bilangan asli lebih besar daripada himpunan bilangan genap, karena bilangan asli memuat semua bilangan genap dan masih ditambah anggota lain, yaitu bilangan ganjil.

Jadi, kita bisa menulis S ⊂ ℕ: himpunan S adalah himpunan bagian sejati dari himpunan ℕ. Lalu kita bisa berkata bahwa jika S ⊂ ℕ, himpunan ℕ lebih besar, karena memuat lebih banyak anggota daripada himpunan S.

Salah satu alasan mengapa ukuran himpunan tidak bisa diukur dengan relasi himpunan bagian adalah bahwa dua himpunan bisa berbeda ukuran walaupun tidak ada yang merupakan himpunan bagian dari yang lain. Hal ini dapat ditunjukkan bahkan pada himpunan berhingga: A = {1, 3, 4, 9} dan B = {b, u, r, z, m}. Berlaku |A| = 4 dan |B| = 5. Himpunan B lebih besar daripada himpunan A, tetapi tidak berlaku A ⊂ B. Pada himpunan tak hingga, hal ini terlihat pada bilangan genap dan bilangan ganjil. Tidak ada yang merupakan himpunan bagian dari yang lain.

Jadi, relasi himpunan bagian bukan alat yang ideal untuk memutuskan apakah suatu himpunan lebih besar daripada himpunan lain.

Bijeksi

Kita coba pendekatan lain. Misalkan ada dua himpunan, A dan B. Kita katakan bahwa keduanya sama besar jika di antara keduanya terdapat pemetaan bijektif (korespondensi satu-satu). Apa artinya? Kita ambil satu anggota dari himpunan A dan satu anggota dari himpunan B, lalu kita bentuk pasangan (a, b). Kedua anggota ini kita keluarkan dari himpunannya, lalu kita lanjutkan. Jika kita berhasil “mengosongkan” kedua himpunan, kita telah menemukan pemetaan bijektif.

Contoh pada himpunan berhingga: A = {a, b, c} dan B = {1, 2, 3}. Pasangan pertama bisa (a, 1), berikutnya (b, 2), dan terakhir (c, 3). Semua anggota kedua himpunan sudah habis, jadi kita telah menemukan pemetaan bijektif. Yang penting, pemetaan bijektif ini bukan satu-satunya. Penyelesaian berikut juga sah: (a, 3), (b, 1), (c, 2).

Pada himpunan tak hingga, hal ini menjadi lebih menarik. Kita coba bilangan asli ganjil dan genap. Secara intuitif kita merasa bahwa banyaknya seharusnya sama. Mari kita coba. Bilangan ganjil pertama kita pasangkan dengan bilangan genap pertama: (1, 2). Lalu bilangan ganjil kedua dengan bilangan genap kedua: (3, 4). Dan seterusnya. Kita peroleh pasangan-pasangan (1, 2), (3, 4), (5, 6), (7, 8), … Kita bisa menuliskan bahwa setiap bilangan ganjil l dipetakan ke bilangan genap l + 1, dan setiap bilangan genap s adalah peta dari bilangan ganjil s − 1. Jadi, untuk setiap bilangan ganjil dan setiap bilangan genap ada pasangan yang memuat bilangan itu. Himpunan bilangan ganjil dan himpunan bilangan genap sama besar.

Bilangan genap dan bilangan asli

Sekarang kita pakai cara yang sama untuk membandingkan himpunan bilangan asli dan himpunan bilangan genap. Kita mempunyai himpunan ℕ = {1, 2, 3, 4, 5, 6, …} dan S = {2, 4, 6, …}. Secara intuitif kita menduga himpunan bilangan asli lebih besar.

Namun, mari kita cari pemetaan bijektifnya. Setiap bilangan asli n kita petakan ke bilangan yang dua kali lipatnya, yaitu 2n. Kita peroleh pasangan-pasangan (1, 2), (2, 4), (3, 6), (4, 8), (5, 10), … Untuk setiap bilangan asli n terdapat pasangan (n, 2n), dan untuk setiap bilangan genap s terdapat pasangan (s/2, s). Kita telah menemukan pemetaan bijektif, jadi himpunan bilangan genap dan himpunan bilangan asli sama besar: keduanya mempunyai kardinalitas yang sama.

Hal ini mungkin terasa membingungkan, karena bilangan asli seolah-olah memuat lebih banyak anggota daripada bilangan genap. Bilangan asli memuat semua bilangan genap dan masih ditambah semua bilangan ganjil. Namun, kita bisa menemukan bijeksi, jadi kedua himpunan sama besar.

Membandingkan dengan bilangan asli

Bilangan asli sebenarnya menentukan ukuran terkecil himpunan tak hingga. Apakah suatu himpunan lain sama besar dengan himpunan bilangan asli sering dapat diperiksa dengan cukup mudah. Kita cukup menemukan bijeksi ke bilangan asli. Dalam praktik, artinya kita cukup bisa memberi nomor pada anggota himpunan M kita, yaitu menyusunnya berurutan.

Jadi, jika anggota suatu himpunan dapat kita urutkan sehingga jelas anggota mana yang pertama, kedua, ketiga, keempat, kesepuluh, dan seterusnya, himpunan itu sama besar dengan ℕ. Himpunan seperti itu disebut himpunan terhitung.

Dengan mudah terlihat bahwa bilangan asli genap dan bilangan asli ganjil terhitung, karena kita bisa menentukan bilangan genap/ganjil yang pertama, kedua, ketiga, dan seterusnya. Bagaimana dengan bilangan bulat genap, yaitu himpunan S = {…, −4, −2, 0, 2, 4, …}? Bisakah kita mengurutkannya? Bisa. Kita cukup memakai urutan yang sama seperti tadi dan tepat setelah setiap bilangan genap positif kita tuliskan lawannya: S = {0, 2, −2, 4, −4, 6, −6, …}. Hal yang sama berlaku, misalnya, untuk bilangan bulat.

Ukuran himpunan bilangan rasional

Contoh yang lebih menarik adalah bilangan rasional, yaitu pecahan. Bisakah kita mengurutkannya? Bisa, tetapi caranya sedikit lebih rumit. Kita susun tabel dengan tak hingga banyak baris dan kolom. Setiap sel berisi pecahan. Pada kolom ke-n dan baris ke-m terdapat pecahan n/m. Jadi, pada kolom ke-1 dan baris ke-2 terdapat $\frac{1}{2}$, dan pada kolom ketiga dan baris keempat terdapat 3/4.

$$\begin{array}{ccccc}1/1& 2/1& 3/1& 4/1& \dots \\ 1/2& 2/2& 3/2& 4/2& \dots \\ 1/3& 2/3& 3/3& 4/3& \dots \\ 1/4& 2/4& 3/4& 4/4& \dots \\ \dots & \dots & \dots & \dots & \dots \end{array}$$

Bagaimana cara mengurutkan dan memberi nomor pada bilangan-bilangan ini? Kita tidak bisa menomorinya baris demi baris atau kolom demi kolom, karena kita akan langsung “tenggelam” dalam satu baris atau kolom yang tak berujung. Sebagai gantinya, kita ambil bilangan menurut diagonal: (diagonal pertama:) 1/1, (diagonal kedua:) 2/1, 1/2, (diagonal ketiga:) 3/1, 2/2, 1/3, (diagonal keempat:) 4/1, 3/2, 2/3, 1/4, … Di dalamnya masih banyak pecahan yang bernilai sama, tetapi hal itu tidak masalah. Yang lebih mengganggu adalah tidak adanya bilangan negatif. Masalah ini mudah diatasi: setiap kali kita menuliskan suatu pecahan, langsung di belakangnya kita tuliskan lawannya. Terakhir, di paling depan masih kurang nol. Selesai, kita sudah mempunyai semua bilangan rasional dalam satu barisan.

Secara keseluruhan, kita peroleh barisan: 0, 1/1, −1/1, 2/1, −2/1, 1/2, −1/2, 3/1, −3/1, 2/2, −2/2, 1/3, −1/3, …

Ukuran himpunan bilangan real

Apakah himpunan bilangan real sama besar dengan himpunan bilangan asli? Pertanyaan ini lebih sulit dijawab daripada untuk bilangan rasional. Kita gunakan bukti dengan kontradiksi. Andaikan bilangan real terhitung, yaitu terdapat pemetaan bijektif ke bilangan asli. Artinya, bilangan real dapat diurutkan. Misalkan pemetaan berikut adalah urutan tersebut:

$$\begin{array}{ccccccccc}0,& 3& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& 9& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& 3& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& 7& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& 7& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& 6& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& 0& \dots \\ \dots \end{array}$$

Tabel ini memuat tujuh bilangan real pertama dalam urutan kita. Urutannya tentu boleh sembarang, tidak harus menurut besarnya bilangan.

Menurut pengandaian, tabel tak hingga ini memuat semua bilangan real secara berurutan. (Tabelnya juga tak hingga; di sini hanya ditampilkan tujuh baris pertama.) Sekarang kita akan mencoba menemukan atau membentuk suatu bilangan real yang tidak ada di dalam tabel ini. Jika bilangan seperti itu ditemukan, hal ini bertentangan dengan pengandaian bahwa tabel memuat semua bilangan real. Dari situ kita dapat menyimpulkan bahwa himpunan bilangan real tidak terhitung.

Bilangan yang tidak ada di dalam tabel kita bentuk seperti ini:

$$\begin{array}{ccccccccc}0,& \boxed{\text{3}}& 5& 2& 2& 4& 6& 0& \dots \\ 0,& 2& \boxed{\text{9}}& 2& 4& 3& 7& 5& \dots \\ 0,& 7& 2& \boxed{\text{3}}& 0& 8& 4& 5& \dots \\ 0,& 1& 4& 3& \boxed{\text{7}}& 9& 0& 6& \dots \\ 0,& 0& 8& 6& 5& \boxed{\text{7}}& 5& 8& \dots \\ 0,& 7& 5& 4& 6& 3& \boxed{\text{6}}& 3& \dots \\ 0,& 3& 4& 1& 9& 7& 0& \boxed{\text{0}}& \dots \\ \dots \end{array}$$

Kita mulai dengan menuliskan 0,… Seperti inilah awal bilangan real baru kita. Pada tempat desimal pertama kita tuliskan angka yang berbeda dengan angka pada tempat pertama bilangan real pertama dalam urutan kita (dalam tabel ditandai dengan kotak). Di situ terdapat angka 3, jadi kita pilih misalnya 1 dan memperoleh bilangan 0,1…

Kita lanjutkan. Pada tempat kedua kita tuliskan angka yang berbeda dengan angka pada tempat kedua bilangan real kedua. Di situ terdapat 9, jadi kita pilih misalnya 2. Kita peroleh bilangan 0,12… Pada tempat ketiga kita tuliskan angka yang berbeda dengan angka ketiga bilangan real ketiga. Di situ terdapat 3, jadi kita pilih misalnya 7. Kita peroleh 0, 127…

Demikian seterusnya. Pada posisi ke-n bilangan baru selalu kita tuliskan angka yang berbeda dengan angka pada posisi ke-n dari bilangan ke-n dalam urutan kita.

Apa yang kita peroleh? Kita memperoleh bilangan yang berbeda dari setiap bilangan dalam urutan kita, sedikitnya pada satu angka. Ambil hasil sementara terakhir: 0,127… Bilangan ini pasti berbeda dari bilangan pertama dalam urutan kita, sedikitnya pada angka pertama, karena memang begitulah kita menyusunnya. Dari bilangan kedua bilangan ini berbeda sedikitnya pada angka kedua, dan dari bilangan ketiga pada angka ketiga. Secara umum, bilangan baru ini berbeda dari bilangan ke-n dalam urutan, sedikitnya pada angka di posisi ke-n.

Jadi, bilangan yang baru dibentuk ini tidak ada di dalam tabel yang seharusnya menggambarkan bijeksi antara bilangan asli dan bilangan real. Dengan demikian, himpunan bilangan real lebih besar daripada himpunan bilangan asli. Himpunan bilangan real bukan himpunan terhitung, melainkan himpunan tak terhitung.

Sumber lain

• Are there more odd or even numbers?