Himpunan terhitung
Pengantar

Himpunan adalah sekumpulan elemen, dan dapat dinyatakan dengan berbagai cara, salah satunya ialah dengan mendaftar anggota-anggotanya; sebagai contoh, himpunan yang terdiri dari bilangan  3,  5, dan  12 dapat dituliskan sebagai  \left\{3,\,5,\,12\right\}, yang disebut sebagai bentuk roster. Akan tetapi, hal ini hanya efektif untuk himpunan yang kecil. Untuk himpunan yang besar, metode roster akan memakan waktu yang lama serta rawan terjadi galat. Daripada mendaftar setiap elemen satu per satu, terkadang tanda elipsis (" \ldots ") digunakan untuk mewakilkan banyak elemen diantara elemen awal dan akhir pada suatu himpunan, jika penulis yakin bahwa pembaca dapat menebak dengan mudah apa yang tanda elipsis wakilkan; sebagai contoh,  \left\{1,\,2,\,3,\,\ldots ,\,99,\,100\right\} mungkin saja menyatakan himpunan bilangan bulat dari  1 sampai dengan  100. Dalam kasus ini, semua elemennya masih mungkin didaftarkan, sebab banyak elemennya berhingga. Jika setiap elemen dari himpunan  1,  2, dan seterusnya, sampai  n diberi label, maka hal ini menjadi definisi dari "himpunan berukuran  n".
Beberapa himpunan merupakan himpunan tak terhingga; himpunan-himpunan ini memiliki lebih dari  n elemen, dengan  n adalah sembarang bilangan asli. Tidak peduli seberapa besar nilai  n nya (seperti  n=10^{10^{100}}), himpunan tak terhingga memiliki lebih dari  n elemen. Misalnya, himpunan bilangan asli, yang dinyatakan sebagai  \left\{1,\,2,\,3,\,4,\,\ldots \right\}, memiliki tak hingga banyaknya elemen, sehingga ukuran himpunannya tidak dapat dinyatakan dengan bilangan asli apa pun. Salah satu hal yang wajar dilakukan ialah membagi himpunan-himpunan yang ada menjadi beberapa kelas: Satukan semua himpunan yang memiliki satu elemen; semua himpunan yang memiliki dua elemen; ...; dan terakhir, satukan semua himpunan tak hingga dan anggaplah mereka memiliki ukuran yang sama. Cara pandang ini dapat dilakukan untuk himpunan terhitung tak terhingga, dan menjadi asumsi yang berlaku sebelum penemuan Geog Cantor. Sebagai contoh, terdapat tak hingga banyaknya bilangan ganjil, tak hingga banyaknya bilangan genap, dan tak hingga banyaknya bilangan bulat secara keseluruhan. Semua himpunan tadi dapat dipandang memiliki ukuran yang sama, sebab setiap bilangan genap dapat dilabeli dengan tunggal menggunakan suatu bilangan bulat:
 {\begin{aligned}&{\phantom {n}}\vdots \\-2&\mapsto -4\\-1&\mapsto -2\\0&\mapsto 0\\1&\mapsto 2\\2&\mapsto 4\\&{\phantom {n}}\vdots \end{aligned}}
dan secara umum,  n\mapsto 2n (lihat gambar di kanan). Proses yang baru saja terjadi ialah mengonstruksikan korespondensi satu-ke-satu (atau bijeksi), yaitu suatu fungsi yang menghubungkan dua himpunan dengan syarat setiap elemen pada masing-masing himpunan dikawankan dengan tepat satu elemen pada himpunan lainnya. Gagasan matematika dari "ukuran", kardinalitas, adalah dua himpunan memiliki ukuran yang sama jika dan hanya jika terdapat suatu fungsi bijektif yang menghubungkan keduanya. Semua himpunan yang memiliki korespondensi satu-ke-satu dengan bilangan bulat disebut sebagai himpunan terhitung tak terhingga dan kardinalitasnya dinotasikan dengan  \aleph _{0}.
Georg Cantor menunjukkan bahwa tidak semua himpunan tak terhingga merupakan himpunan terhitung tak terhingga. Misalnya, himpunan bilangan riil tidak dapat dibuat korespondensi satu-ke-satu dengan bilangan asli. Himpunan bilangan riil memiliki kardinalitas yang lebih dari himpunan bilangan asli, dan disebut sebagai tak terhitung.