Himpunan terhitung

Templat:Short description Dalam matematika, suatu himpunan dikatakan terhitung, tercacah, atau terbilang jika himpunannya berhingga atau dapat dibuat korespondensi satu-ke-satu dengan himpunan bilangan asli. Dengan kata lain, suatu himpunan disebut terhitung jika terdapat suatu fungsi injektif dari himpunan tersebut ke bilangan asli; ini artinya setiap elemen pada himpunan tersebut dapat dilabeli dengan tepat satu bilangan asli, atau elemen-elemen dari himpunannya dapat dihitung satu demi satu, walau mungkin saja proses perhitungannya mustahil selesai akibat jumlah elemen yang tak hingga banyaknya.

Dengan menggunakan istilah teknis, jika diasumsikan aksioma pemilihan terhitung, suatu himpunan disebut terhitung jika kardinalitasnya (banyaknya elemen pada himpunan tersebut) tidak lebih dari kardinalitas bilangan asli. Suatu himpunan terhitung yang bukan merupakan himpunan berhingga disebut terhitung tak terhingga.

Konsep ini diatribusikan kepada Georg Cantor, yang membuktikan keujudan dari himpunan-himpunan tak terhitung, yaitu himpunan-himpunan yang bukan merupakan himpunan terhitung; seperti contohnya himpunan semua bilangan riil.

Catatan penggunaan istilah

Walaupun artikel ini menggunakan istilah "terhitung" dan "terhitung tak terhingga" yang cukup umum digunakan, kedua istilah tersebut tidaklah universal. Beberapa referensi menggunakan istilah terhitung sebagai apa yang dimaksud disini sebagai terhitung tak terhingga, dan paling banyak terhitung sebagai apa yang dimaksud disini sebagai terhitung.

Istilah enumerable dan denumerable juga terkadang digunakan untuk berturut-turut menyatakan himpunan terhitung dan terhitung.

Definisi

Suatu himpunan $H$ dikatakan terhitung jika:

• Himpunan $H$ adalah himpunan hingga atau terhitung tak berhingga.
• Kardinalitasnya (dinotasikan dengan $\left|H\right|$) tidak lebih dari ${\mathrm{\aleph }}_0$ (alef nol), yaitu kardinalitas dari himpunan bilangan asli $\mathbb{N}$.
• Terdapat suatu fungsi injektif dari $H$ ke $\mathbb{N}$.
• Himpunan $H$ merupakan himpunan kosong atau terdapat suatu fungsi surjektif dari $\mathbb{N}$ ke $H$.
• Terdapat suatu fungsi bijektif antara $H$ dan suatu himpunan bagian dari $\mathbb{N}$.

Semua definisi di atas ekuivalen satu sama lain.

Suatu himpunan $H$ dikatakan terhitung tak terhingga jika:

• Kardinalitasnya (yaitu $\left|H\right|$) sama dengan ${\mathrm{\aleph }}_0$.
• Terdapat suatu pemetaan injektif dan surjektif antara $H$ dan $\mathbb{N}$.
• Himpunan $H$ memiliki korespondensi satu-ke-satu dengan $\mathbb{N}$.
• Elemen dari himpunan $H$ dapat disusun dalam suatu barisan tak terhingga $a_0,a_1,a_2,\dots$, dengan $a_i\ne a_j$ ketika $i\ne j$, dan setiap elemen pada $H$ terdaftar.

Suatu himpunan disebut tak terhitung jika himpunannya tidak terhitung, atau dengan kata lain, kardinalitasnya lebih dari ${\mathrm{\aleph }}_0$.

Sejarah

Pada tahun 1874, dalam artikel teori himpunan pertama miliknya, Cantor membuktikan bahwa himpunan bilangan riil merupakan himpunan tak terhitung, yang menunjukkan bahwa tidak semua himpunan tak terhingga merupakaan himpunan terhitung. Pada tahun tersebut, Cantor menggunakan korespondensi satu-ke-satu untuk mendefinisikan dan membandungkan kardinalitas. Pada tahun 1883, beliau memperluas bilangan asli dengan bilangan ordinal takhingga miliknya, dan menggunakan himpunan ordinal untuk membuat tak terhingga banyaknya himpunan yang memiliki kardinalitas yang beda-beda.

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 $\{3,5,12\}$, 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 ("$\dots$") 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, $\{1,2,3,\dots ,99,100\}$ 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$".

Pemetaan bijektif dari bilangan bulat ke bilangan genap

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 $\{1,2,3,4,\dots \}$, 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{array}{cc}& \phantom{n}⋮\\ -2& \mapsto -4\\ -1& \mapsto -2\\ 0& \mapsto 0\\ 1& \mapsto 2\\ 2& \mapsto 4\\ & \phantom{n}⋮\end{array}$$ 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 ${\mathrm{\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.

Kajian formal

Berdasarkan definisi, suatu himpunan $H$ disebut terhitung jika terdapat suatu fungsi bijektif dari $H$ ke himpunan bagian dari bilangan asli $\mathbb{N}=\{1,2,3,4,\dots \}$. Sebagai contoh, didefinisikan pemetaan $$\begin{array}{cc}a& \leftrightarrow 1\\ b& \leftrightarrow 2\\ c& \leftrightarrow 3\end{array}$$ Oleh karena setiap elemen dari himpunan $H=\{a,b,c\}$ dikawankan dengan tepat satu elemen dari himpunan $\{1,2,3\}$ (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 $\{2,4,6,8,\dots \}$ merupakan himpunan terhitung tak terhingga, sebab terdapat korespondensi satu-ke-satu $n\leftrightarrow 2n$ sebagai berikut: $$\begin{array}{cc}1& \leftrightarrow 2\\ 2& \leftrightarrow 4\\ 3& \leftrightarrow 6\\ 4& \leftrightarrow 8\\ & \phantom{n}⋮\end{array}$$ Setiap himpunan bagian dari bilangan asli merupakan himpunan terhitung. Secara umum, Templat:Math theorem

Fungsi pemasang Cantor mengawankan setiap bilangan asli dengan suatu pasangan bilangan asli.

Himpunan semua pasangan terurut (atau hasil-kali Kartesius) dari himpunan bilangan cacah $𝕎\times 𝕎$ merupakan himpunan terhitung tak terhingga. Hasil pemetaannya dapat dilihat pada gambar di bagian kanan dan dilakukan sebagai berikut $$\begin{array}{cc}0& \leftrightarrow (0,0)\\ 1& \leftrightarrow (1,0)\\ 2& \leftrightarrow (0,1)\\ 3& \leftrightarrow (2,0)\\ 4& \leftrightarrow (1,1)\\ 5& \leftrightarrow (0,2)\\ 6& \leftrightarrow (3,0)\end{array}$$ Pemetaan ini meliput seluruh pasangan terurut.

Bentuk pemetaan segitiga ini dapat diperumum secara rekursif menjadi bilangan asli rangkap-$n$, yaitu $(a_1,a_2,a_3,\dots ,a_n)$ dengan $a_k,n\in \mathbb{N}$ untuk setiap $k\in \{1,2,3,\dots ,n\}$, dengan cara memetakan secara berulang dua elemen pertama dari rangkap-$n$ nya ke suatu bilangan asli. Sebagai contoh, $(0,2,3)$ dapat ditulis sebagai $((0,2),3)$. Perhatikan bahwa $(0,2)$ dipetakan ke $5$. Akibatnya, $(0,2,3)$ dipetakan ke $(5,3)$, yang kemudian dipetakan ke $39$. Oleh karena rangkap-$2$ yang berbeda, yaitu pasangan terurut seperti $(a,b)$, 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

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 $\frac{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.

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 $\frac{p}{q}\leftrightarrow (p,q)$ (dengan syarat $\mathrm{FPB}(p,q)=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.

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.

"Pelabelan" dari terhitung banyaknya himpunan terhitung

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}{ccc}\text{Indeks}& \text{Rangkap}& \text{Elemen}\\ 0& (0,0)& a_0\\ 1& (0,1)& a_1\\ 2& (1,0)& b_0\\ 3& (0,2)& a_2\\ 4& (1,1)& b_1\\ 5& (2,0)& c_0\\ 6& (0,3)& a_3\\ 7& (1,2)& b_2\\ 8& (2,1)& c_1\\ 9& (3,0)& d_0\\ 10& (0,4)& a_4\\ ⋮& ⋮& ⋮\end{array}$$

Aksioma pemilihan terhitung diperlukan untuk memberikan indeks kepada semua himpunan $A$, $B$, $C$, $\dots$, secara bersamaan.

Teorema Cantor menyatakan bahwa jika $X$ adalah suatu himpunan dan $𝒫\left(X\right)$ adalah himpunan kuasa dari $X$ (yaitu himpunan seluruh himpunan bagian dari $X$), maka tidak ada fungsi surjektif dari $X$ ke $𝒫\left(X\right)$. Pembuktian dari pernyataan ini dapat dilihat pada artikel teorema Cantor. Salah satu akibat dari teorema ini ialah Templat:Math theorem

Lihat juga

• Bilangan alef
• Pencacahan
• Paradoks hotel Hilbert
• Himpunan takterhitung

Referensi

• Templat:En iconTemplat:Citation
• Templat:En iconTemplat:Citation
• Templat:En iconTemplat:Citation
• Templat:En iconTemplat:Citation
• Templat:En iconTemplat:Citation
• Templat:En iconTemplat:Citation Reprinted by Springer-Verlag, New York, 1974. Templat:ISBN (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. Templat:ISBN (Paperback edition).
• Templat:En iconTemplat:Citation
• Templat:En iconTemplat:Citation
• Templat:En iconTemplat:Citation
• Templat:En iconTemplat:Cite book