Himpunan terhitung
Kajian formal

Berdasarkan definisi, suatu himpunan  H disebut terhitung jika terdapat suatu fungsi bijektif dari  H ke himpunan bagian dari bilangan asli  \mathbb {N} =\left\{1,\,2,\,3,\,4,\,\ldots \right\}. Sebagai contoh, didefinisikan pemetaan
 {\begin{aligned}a&\leftrightarrow 1\\b&\leftrightarrow 2\\c&\leftrightarrow 3\end{aligned}}
Oleh karena setiap elemen dari himpunan  H=\left\{a,\,b,\,c\right\} dikawankan dengan tepat satu elemen dari himpunan  \left\{1,\,2,\,3\right\} (dan begitu juga sebaliknya), maka pemetaannya bersifat bijektif, dan menjadi bukti bahwa  H adalah himpunan terhitung. Dengan cara serupa, maka dapat ditunjukkan bahwa setiap himpunan berhingga merupakan himpunan terhitung.
Pada kasus himpunan tak terhingga, suatu himpunan  H dikatakan terhitung tak terhingga jika terdapat suatu fungsi bijektif dari  H ke himpunan bilangan asli  \mathbb {N} . Sebagai contoh, himpunan bilangan genap positif  \left\{2,\,4,\,6,\,8,\,\ldots \right\} merupakan himpunan terhitung tak terhingga, sebab terdapat korespondensi satu-ke-satu  n\leftrightarrow 2n sebagai berikut:
 {\begin{aligned}1&\leftrightarrow 2\\2&\leftrightarrow 4\\3&\leftrightarrow 6\\4&\leftrightarrow 8\\&{\phantom {n}}\vdots \end{aligned}}
Setiap himpunan bagian dari bilangan asli merupakan himpunan terhitung. Secara umum,
Teorema — Setiap himpunan bagian dari suatu himpunan terhitung merupakan himpunan terhitung.
Himpunan semua pasangan terurut (atau hasil-kali Kartesius) dari himpunan bilangan cacah  \mathbb {W} \times \mathbb {W}  merupakan himpunan terhitung tak terhingga. Hasil pemetaannya dapat dilihat pada gambar di bagian kanan dan dilakukan sebagai berikut
 {\begin{aligned}0&\leftrightarrow \left(0,\,0\right)\\1&\leftrightarrow \left(1,\,0\right)\\2&\leftrightarrow \left(0,\,1\right)\\3&\leftrightarrow \left(2,\,0\right)\\4&\leftrightarrow \left(1,\,1\right)\\5&\leftrightarrow \left(0,\,2\right)\\6&\leftrightarrow \left(3,\,0\right)\end{aligned}}
Pemetaan ini meliput seluruh pasangan terurut.
Bentuk pemetaan segitiga ini dapat diperumum secara rekursif menjadi bilangan asli rangkap- n, yaitu  \left(a_{1},\,a_{2},\,a_{3},\,\ldots ,\,a_{n}\right) dengan  a_{k},\,n\in \mathbb {N}  untuk setiap  k\in \left\{1,\,2,\,3,\,\ldots ,\,n\right\}, dengan cara memetakan secara berulang dua elemen pertama dari rangkap- n nya ke suatu bilangan asli. Sebagai contoh,  \left(0,\,2,\,3\right) dapat ditulis sebagai  \left(\left(0,\,2\right),\,3\right). Perhatikan bahwa  \left(0,\,2\right) dipetakan ke  5. Akibatnya,  \left(0,\,2,\,3\right) dipetakan ke  \left(5,\,3\right), yang kemudian dipetakan ke  39. Oleh karena rangkap- 2 yang berbeda, yaitu pasangan terurut seperti  \left(a,\,b\right), dipetakan ke bilangan asli yng berbeda, maka perbedaan dua rangkap- n pada setidaknya satu elemen saja sudah cukup untuk menjamin rangkap- n nya dipetakan ke bilangan asli yang berbeda, sehingga terbukti bahwa terdapat suatu fungsi injektif dari himpunan rangkap- n ke himpunan bilangan asli  \mathbb {N} . Secara umum, maka
Teorema — Hasil-kali Kartesius dari berhingga banyaknya himpunan terhitung merupakan himpunan terhitung.
Perhatikan bahwa  \mathbb {N} \times \mathbb {N}  merupakan himpunan terhitung, sebab terdapat fungsi injektif  f\,\colon \,\mathbb {N} \times \mathbb {N} \to \mathbb {N}  dengan
 f\!\left(x,\,y\right)=2^{x}\cdot 3^{y}
Jika  A dan  B merupakan himpunan terhitung, maka terdapat fungsi surjektif
 g\,\colon \,\mathbb {N} \to A\qquad {\text{dan}}\qquad h\,\colon \,\mathbb {N} \to B
Berdasarkan informasi tersebut, fungsi  g\times h\,\colon \,\mathbb {N} \times \mathbb {N} \to A\times B bersifat surjektif, sehingga  A\times B merupakan himpunan terhitung. Hasil ini dapat diperumum menjadi hasil-kali Kartesius dari berhingga banyaknya himpunan terhitung dengan menggunakan induksi matematika.
Himpunan semua bilangan bulat  \mathbb {Z}  dan himpunan semua bilangan rasional  \mathbb {Q}  secara intuitif terlihat lebih besar dari  \mathbb {N} , namun penampilan bisa menipu. Jika pasangan terurut  \mathbb {N} \times \mathbb {N}  dipandang sebagai pembilang dan penyebut dari suatu pecahan biasa, maka setiap pecahan bernilai positif dapat dikawankan dengan suatu bilangan asli yang berbeda satu sama lain. Representasi ini juga memuat bilangan asli, sebab setiap bilangan asli  n dapat dinyatakan sebagai pecahan  {\dfrac {n}{1}}, sehingga dapat disimpulkan bahwa jumlah bilangan rasional positif sama banyaknya dengan bilangan bulat positif. Hal ini juga berlaku untuk seluruh bilangan rasional, seperti pada pernyataan berikut.
Teorema — Himpunan semua bilangan bulat  \mathbb {Z} , himpunan semua bilangan rasional  \mathbb {Q} , dan himpunan semua bilangan aljabar  \mathbb {A}  merupakan himpunan terhitung.
Himpunan  \mathbb {Z}  merupakan himpunan terhitung, sebab terdapat fungsi injektif  f\,\colon \,\mathbb {Z} \to \mathbb {N}  dengan  f(n)={\begin{cases}2^{n}&n\geq 0\\3^{-n}&n<0\end{cases}}
Himpunan  \mathbb {Q}  merupakan himpunan terhitung, sebab terdapat suatu fungsi surjektif  g\,\colon \,\mathbb {Z} \times \mathbb {N} \to \mathbb {Q}  dengan  g\!\left(m,\,n\right)={\dfrac {m}{n+1}}
Berdasarkan definisi, setiap bilangan aljabar (termasuk bilangan kompleks merupakan akar persamaan dari suatu polinomial dengan koefisien bilangan bulat. Diberikan sembarang  a\in \mathbb {A} , dan misalkan  c_{0}+c_{1}x+c_{2}x^{2}+c_{3}x^{3}+\ldots +c_{k}x^{k} adalah suatu polinomial dengan koefisien bilangan bulat sedemikian sehingga  a adalah akar ke- n dari polinomial tersebut, dengan akar-akarnya diurutkan berdasarkan nilai mutlaknya dari kecil ke besar, lalu argumennya diurutkan dari kecil ke besar. Himpunan  \mathbb {A}  merupakan himpunan terhitung, sebab terdapat suatu fungsi injektif  h\,\colon \,\mathbb {A} \to \mathbb {N}  dengan  h\!\left(a\right)=2^{n}\cdot 3^{c_{0}}\cdot 5^{c_{1}}\cdot 7^{c_{2}}\cdot \ldots \cdot {p_{k+2}}^{c_{k}} dimana  p_{i} menyatakan bilangan prima ke- i.
Dalam beberapa kasus, penggunaan lebih dari satu pemetaan adalah hal yang membantu. Misalkan akan dibuktikan bahwa suatu himpunan  A merupakan himpunan terhitung dan  A bersifat injektif ke himpunan lain (katakanlah)  B, maka himpunan  A terbukti merupakan himpunan terhitung jika  B bersifat injektif ke himpunan bilangan asli. Sebagai contoh, terdapat suatu fungsi injektif dari himpunan semua bilangan rasional positif ke pasangan (rangkap- 2) bilangan asli, salah satunya ialah  {\dfrac {p}{q}}\leftrightarrow \left(p,\,q\right) (dengan syarat  \operatorname {FPB} \!\left(p,\,q\right)=1). Oleh karena  \mathbb {N} \times \mathbb {N}  memiliki korespondensi satu-ke-satu dengan  \mathbb {N}  (seperti yang telah ditunjukkan sebelumnya), maka himpunan bilangan rasional positif terbukti merupakan himpunan terhitung.
Teorema — Setiap gabungan berhingga dari himpunan-himpunan terhitung juga merupakan himpunan terhitung.
Misalkan  n\in \mathbb {N}  dan  N:=\left\{1,\,2,\,3,\,\ldots ,\,n\right\}. Jika  A_{k} adalah himpunan terhitung untuk setiap  k\in N, maka terdapat fungsi-fungsi  f_{k}\,\colon \,\mathbb {N} \to A_{k} yang bersifat surjektif. Akibatnya, fungsi
 F\,\colon \,N\times \mathbb {N} \to \bigcup _{k\,=\,1}^{n}A_{k}
juga bersifat surjektif, dengan  F\!\left(k,\,x\right)=f_{k}\!\left(x\right). Oleh karena himpunan  N\times \mathbb {N}  merupakan himpunan terhitung, maka  \displaystyle \bigcup _{k\,=\,1}^{n}A_{k} juga merupakan himpunan terhitung.
Dengan pengetahuan bahwa terdapat himpunan tak terhitung, maka terlintas pikiran untuk mendorong lebih jauh hasil terakhir ini, dan jawabannya adalah "iya" dan "tidak"; Hasil ini dapat diperluas, namun perlu diasumsikan suatu aksioma tambahan sebagai berikut.
Teorema — Dengan mengasumsikan aksioma pemilihan terhitung, maka setiap gabungan terhitung dari himpunan-himpunan terhitung juga merupakan himpunan terhitung.
Misalkan  n\in \mathbb {N} . Jika  A_{k} adalah himpunan terhitung untuk setiap  k\in \mathbb {N} , maka berdasarkan aksioma pemilihan terhitung, terdapat fungsi-fungsi  f_{k}\,\colon \,\mathbb {N} \to A_{k} yang bersifat surjektif. Oleh karena fungsi
 F\,\colon \,\mathbb {N} \times \mathbb {N} \to \bigcup _{k\,=\,1}^{n}A_{i}
bersifat surjektif, dan bukan injektif, maka tidak ada syarat bahwa himpunannya harus bersifat saling asing.
Sebagai contoh, diberikan himpunan terhitung  A,  B,  C, dan seterusnya. Pertama, setiap elemen dari masing-masing himpunan akan dilabeli oleh suatu rangkap, lalu setiap rangkap akan dilabeli dengan suatu indeks menggunakan varian pemetaan segitiga kelak-kelok yang telah ditunjukkan sebelumnya:
 {\begin{array}{c|c|c}{\text{Indeks}}&{\text{Rangkap}}&{\text{Elemen}}\\\hline 0&\left(0,\,0\right)&a_{0}\\1&\left(0,\,1\right)&a_{1}\\2&\left(1,\,0\right)&b_{0}\\3&\left(0,\,2\right)&a_{2}\\4&\left(1,\,1\right)&b_{1}\\5&\left(2,\,0\right)&c_{0}\\6&\left(0,\,3\right)&a_{3}\\7&\left(1,\,2\right)&b_{2}\\8&\left(2,\,1\right)&c_{1}\\9&\left(3,\,0\right)&d_{0}\\10&\left(0,\,4\right)&a_{4}\\\vdots &\vdots &\vdots \end{array}}
Aksioma pemilihan terhitung diperlukan untuk memberikan indeks kepada semua himpunan  A,  B,  C,  \ldots , secara bersamaan.
Teorema — Misalkan  A dan  B adalah himpunan.
Jika fungsi  f\,\colon \,A\to B bersifat injektif dan  B adalah himpunan terhitung, maka  A juga merupakan himpunan terhitung.
Jika fungsi  g\,\colon \,A\to B bersifat surjektif dan  A adalah himpunan terhitung, maka  B juga merupakan himpunan terhitung.
Kedua hal ini merupakan akibat dari definisi himpunan terhitung sebagai fungsi injektif / surjektif.
Jika  B adalah himpunan terhitung, maka terdapat fungsi injektif  h\,\colon \,B\to \mathbb {N} . Oleh karena fungsi  f bersifat injektif, maka fungsi komposisi  h\circ f\,\colon \,A\to \mathbb {N}  juga bersifat injektif, sehingga terbukti bahwa  A merupakan himpunan terhitung.
Jika  A adalah himpunan terhitung, maka terdapat fungsi surjektif  h\,\colon \,\mathbb {N} \to A. Oleh karena fungsi  g bersifat surjektif, maka terdapat dua kasus yang mungkin terjadi: himpunan  A dan  B sama-sama merupakan himpunan kosong, atau fungsi komposisi  g\circ h\,\colon \,\mathbb {N} \to B juga bersifat surjektif. Berdasarkan kedua kasus yang diperoleh, terbukti bahwa  B merupakan himpunan terhitung.
Teorema Cantor menyatakan bahwa jika  X adalah suatu himpunan dan  {\mathcal {P}}\!\left(X\right) adalah himpunan kuasa dari  X (yaitu himpunan seluruh himpunan bagian dari  X), maka tidak ada fungsi surjektif dari  X ke  {\mathcal {P}}\!\left(X\right). Pembuktian dari pernyataan ini dapat dilihat pada artikel teorema Cantor. Salah satu akibat dari teorema ini ialah
Teorema — Himpunan  {\mathcal {P}}\!\left(\mathbb {N} \right) bukan merupakan himpunan terhitung; atau dengan kata lain, himpunannya tak terhitung.