Himpunan terhitung: Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Hadithfajri (bicara | kontrib) Tidak ada ringkasan suntingan |
Melengkapi halaman "Himpunan terhitung" Tag: kemungkinan perlu pemeriksaan terjemahan Suntingan visualeditor-wikitext pranala ke halaman disambiguasi |
||
Baris 1:
{{Short description|Himpunan matematis yang dapat dihitung}}
Dalam [[matematika]], suatu [[Himpunan (matematika)|himpunan]] dikatakan '''terhitung'''<ref>{{Cite book
| last = Warsito
| date = 2021
| url = https://pustaka.ut.ac.id/lib/mata4101-pengantar-matematika-edisi-2/
| title = Pengantar Matematika (BMP)
| location = Tanggerang Selatan
| publisher = Universitas Terbuka
| url-status = live}}</ref><ref>{{Cite book
| last = Setiadji
| date = 2009
| title = Himpunan & logika samar serta aplikasinya
| location = Yogyakarta
| publisher = Graha Ilmu
| url-status = live}}</ref><ref>{{Cite journal
| last = Fatihah
| first = Nurul
| last2 = Haripamyu
| first2 = Haripamyu
| last3 = Ekariani
| first3 = Shelvi
| date = 2020-06-29
| title = Ukuran Luar Lebesgue di <math>\mathbb{R}^n</math>
| url = http://jmua.fmipa.unand.ac.id/index.php/jmua/article/view/574
| journal = Jurnal Matematika UNAND
| volume = 9
| issue = 2
| pages = 76–83
| doi = 10.25077/jmu.9.2.76-83.2020
| issn = 2721-9410}}</ref>, '''tercacah'''<ref>{{cite web
| url = https://pasti.kemdikbud.go.id/istilah_listdet.php?id=45928&char=C&page=258
| website = Pasti (Padanan Istilah)
| title = Daftar Istilah
| publisher = Badan Pengembangan dan Pembinaan Bahasa
| access-date = 21 Oktober 2024
}}</ref>, atau '''terbilang'''<ref>{{cite web
| url = https://repository.billfath.ac.id/khairul/2021/04/khairul_analisis_real_1.pdf#page=2
| title = ANALISIS REAL 1
| last = Umam
| first = Ahmad Khairul
| page = 2
| website = Repositori Universitas Billfath
| access-date = 21 Oktober 2024
}}</ref> jika himpunannya [[Himpunan hingga|berhingga]] atau dapat dibuat [[Bijeksi|korespondensi satu-ke-satu]] dengan himpunan [[bilangan asli]].<ref name=ZeroN/> 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 [[kardinalitas]]nya (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 takterhitung|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.<ref>{{cite book
| last1 = Manetti
| first1 = Marco
| title = Topology
| trans-title = Topologi
| date = 19 June 2015
| publisher = Springer
| isbn = 978-3-319-16958-3
| page = 26
| url = https://books.google.com/books?id=89zyCQAAQBAJ&pg=PA26
| language = en}}</ref> 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.<ref name="Rudin">{{Harvard citation no brackets|Rudin|1976|loc=Chapter 2}}</ref><ref>{{harvnb|Tao|2016|p=181}}</ref>
Istilah ''enumerable''<ref>{{Harvard citation no brackets|Kamke|1950|page=2}}</ref> dan ''denumerable''<ref name="Lang">{{Harvard citation no brackets|Lang|1993|loc=§2 of Chapter I}}</ref><ref name="Apostol">{{Harvard citation no brackets|Apostol|1969|loc=Chapter 1.14|p=23}}</ref><ref>{{cite web
| url = https://analisisreal.mipa.ugm.ac.id/real/himpunan/himpunan-terhitung/
| title = Himpunan Terhitung
| last = noorma_yulia
| website = Menara Ilmu Analisis Real
| publisher = Universitas Gajah Mada
| access-date = 22 Oktober 2024}}</ref> juga terkadang digunakan untuk berturut-turut menyatakan himpunan terhitung dan terhitung.<ref>{{cite book
| last1 = Thierry
| first1 = Vialar
| title = Handbook of Mathematics
| date = 4 April 2017
| publisher = BoD - Books on Demand
| isbn = 978-2-9551990-1-5
| page = 24
| url = https://books.google.com/books?id=RkepDgAAQBAJ&pg=PA24
| language = en}}</ref>
== Definisi ==
Suatu himpunan <math>H</math> dikatakan ''terhitung'' jika:
* Himpunan <math>H</math> adalah [[himpunan hingga]] atau terhitung tak berhingga.<ref name="Lang"/>
* [[Kardinalitas]]nya (dinotasikan dengan <math>\left| H \right|</math>) tidak lebih dari <math>\aleph_0</math> ([[bilangan alef|alef nol]]), yaitu kardinalitas dari himpunan [[bilangan asli]] <math>\mathbb{N}</math>.<ref name=Yaqub/>
* Terdapat suatu [[fungsi injektif]] dari <math>H</math> ke <math>\mathbb{N}</math>.<ref name=Singh>{{cite book
| last1 = Singh
| first1 = Tej Bahadur
| title = Introduction to Topology
| trans-title = Pengantar Topologi
| date = 17 May 2019
| publisher = Springer
| isbn = 978-981-13-6954-4
| page = 422
| url = https://books.google.com/books?id=UQiZDwAAQBAJ&pg=PA422
| language = en}}</ref><ref name=Katzourakis>{{cite book
| last1 = Katzourakis
| first1 = Nikolaos
| last2 = Varvaruca
| first2 = Eugen
| title = An Illustrative Introduction to Modern Analysis
| trans-title = Pengantar Ilustratif Analisis Modern
| date = 2 January 2018
| publisher = CRC Press
| isbn = 978-1-351-76532-9
| url = https://books.google.com/books?id=jBFFDwAAQBAJ&pg=PT15
| language = en}}</ref>
* Himpunan <math>H</math> merupakan himpunan kosong atau terdapat suatu [[fungsi surjektif]] dari <math>\mathbb{N}</math> ke <math>H</math>.<ref name=Katzourakis/>
* Terdapat suatu [[Bijeksi|fungsi bijektif]] antara <math>H</math> dan suatu himpunan bagian dari <math>\mathbb{N}</math>.<ref>{{harvnb|Halmos|1960|loc=p. 91}}</ref>
Semua definisi di atas ekuivalen satu sama lain.
Suatu himpunan <math>H</math> dikatakan ''terhitung [[Himpunan takhingga|tak terhingga]]'' jika:
* Kardinalitasnya (yaitu <math>\left| H \right|</math>) sama dengan <math>\aleph_0</math>.<ref name=Yaqub/>
* Terdapat suatu pemetaan injektif dan surjektif antara <math>H</math> dan <math>\mathbb{N}</math>.
* Himpunan <math>H</math> memiliki [[Bijeksi|korespondensi satu-ke-satu]] dengan <math>\mathbb{N}</math>.<ref>{{harvnb|Kamke|1950|loc=p. 2}}</ref>
* Elemen dari himpunan <math>H</math> dapat disusun dalam suatu barisan tak terhingga <math>a_0, \, a_1, \, a_2, \, \ldots</math>, dengan <math>a_i \neq a_j</math> ketika <math>i \neq j</math>, dan setiap elemen pada <math>H</math> terdaftar.<ref>{{cite book
| last1 = Dlab
| first1 = Vlastimil
| last2 = Williams
| first2 = Kenneth S.
| title = Invitation To Algebra: A Resource Compendium For Teachers, Advanced Undergraduate Students And Graduate Students In Mathematics
| date = 9 June 2020
| publisher = World Scientific
| isbn = 978-981-12-1999-3
| page = 8
| url = https://books.google.com/books?id=l9rrDwAAQBAJ&pg=PA8
| language = en}}</ref><ref>{{harvnb|Tao|2016|p=182}}</ref>
Suatu himpunan disebut ''[[himpunan takterhitung|tak terhitung]]'' jika himpunannya tidak terhitung, atau dengan kata lain, kardinalitasnya lebih dari <math>\aleph_0</math>.<ref name=Yaqub>{{cite book
| last1 = Yaqub
| first1 = Aladdin M.
| title = An Introduction to Metalogic
| trans-title = Pengantar Metalogika
| date = 24 October 2014
| publisher = Broadview Press
| isbn = 978-1-4604-0244-3
| url = https://books.google.com/books?id=cyljCAAAQBAJ&pg=PT187
| language = en}}</ref>
== Sejarah ==
Pada tahun 1874, dalam [[artikel teori himpunan pertama Cantor|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.<ref>{{citation
| title = Roads to Infinity: The Mathematics of Truth and Proof
| trans-title = Jalan Menuju Tak Hingga: Matematika dari Kebenaran dan Bukti
| first = John C.
| last = Stillwell
| author-link = John Stillwell
| publisher = CRC Press
| year = 2010
| isbn = 9781439865507
| page = 10
| lang = en
| url = https://books.google.com/books?id=XvPRBQAAQBAJ&pg=PA10
| quote = Penemuan himpunan tak terhitung oleh Cantor pada 1874 merupakan salah satu kejadian yang paling tidak terduga dalam sejarah matematika. Sebelum tahun 1874, tak terhingga bahkan tidak dianggap sebagai topik matematika yang sah oleh banyak orang, sehingga keperluan untuk membedakan antara himpunan terhitung tak terhingga dan himpunan tak terhitung tak terhingga tidak dapat dibayangkan.}}</ref> Pada tahun tersebut, Cantor menggunakan korespondensi satu-ke-satu untuk mendefinisikan dan membandungkan kardinalitas.<ref>Cantor 1878, p. 242.</ref> 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.<ref>Ferreirós 2007, pp. 268, 272–273.</ref>
== Pengantar ==
''[[Himpunan (matematika)|Himpunan]]'' adalah sekumpulan ''elemen'', dan dapat dinyatakan dengan berbagai cara, salah satunya ialah dengan mendaftar anggota-anggotanya; sebagai contoh, himpunan yang terdiri dari bilangan <math>3</math>, <math>5</math>, dan <math>12</math> dapat dituliskan sebagai <math>\left\{ 3, \, 5, \, 12 \right\}</math>, yang disebut sebagai bentuk roster.<ref>{{Cite web
| date = 2021-05-09
| title = What Are Sets and Roster Form?
| trans-title = Apa Itu Himpunan dan Bentuk Roster?
| url = https://www.expii.com/t/what-are-sets-and-roster-form-4300
| url-status = live
| website = expii
| archive-url = https://web.archive.org/web/20200918224155/https://www.expii.com/t/what-are-sets-and-roster-form-4300
| archive-date = 2020-09-18}}</ref> 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 ("<math>\ldots</math>") 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, <math>\left\{ 1, \, 2, \, 3, \, \ldots, \, 99, \, 100 \right\}</math> mungkin saja menyatakan himpunan [[bilangan bulat]] dari <math>1</math> sampai dengan <math>100</math>. Dalam kasus ini, semua elemennya masih ''mungkin'' didaftarkan, sebab banyak elemennya berhingga. Jika setiap elemen dari himpunan <math>1</math>, <math>2</math>, dan seterusnya, sampai <math>n</math> diberi label, maka hal ini menjadi definisi dari "himpunan berukuran <math>n</math>".
[[File:Aplicación 2 inyectiva sobreyectiva02.svg|thumb|x100px|Pemetaan bijektif dari bilangan bulat ke bilangan genap]]
Beberapa himpunan merupakan himpunan ''tak terhingga''; himpunan-himpunan ini memiliki lebih dari <math>n</math> elemen, dengan <math>n</math> adalah sembarang bilangan asli. Tidak peduli seberapa besar nilai <math>n</math> nya (seperti <math>n = 10^{10^{100}}</math>), himpunan tak terhingga memiliki lebih dari <math>n</math> elemen. Misalnya, himpunan bilangan asli, yang dinyatakan sebagai <math>\left\{ 1, \, 2, \, 3, \, 4, \, \ldots \right\}</math>,<ref name=ZeroN>Oleh karena terdapat [[bijeksi]] antara bilangan asli <math>\left\{ 1, \, 2, \, 3, \, 4, \, \ldots \right\}</math> dan bilangan cacah <math>\left\{ 0, \, 1, \, 2, \, 3, \, 4, \, \ldots \right\}</math>, maka tidak masalah apabila bilangan <math>0</math> dianggap sebagai bilangan asli atau bukan. Mengesampingkan hal tersebut, artikel ini mengikuti [[ISO 31-11]] dan konvensi standar dalam [[logika matematika]], yang menyatakan bahwa <math>0</math> adalah bilangan asli.</ref> 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:
<math display="block>\begin{align}
&\phantom{n} \vdots \\
-2 &\mapsto -4 \\
-1 &\mapsto -2 \\
0 &\mapsto 0 \\
1 &\mapsto 2 \\
2 &\mapsto 4 \\
&\phantom{n} \vdots
\end{align}</math>
dan secara umum, <math>n \mapsto 2n</math> (lihat gambar di kanan). Proses yang baru saja terjadi ialah mengonstruksikan ''korespondensi satu-ke-satu'' (atau ''[[bijeksi]]''), yaitu suatu [[Fungsi (matematika)|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 <math>\aleph_0</math>.
[[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 <math>H</math> disebut ''terhitung'' jika terdapat suatu [[bijeksi|fungsi bijektif]] dari <math>H</math> ke himpunan bagian dari [[bilangan asli]] <math>\mathbb{N} = \left\{ 1, \, 2, \, 3, \, 4, \, \ldots \right\}</math>. Sebagai contoh, didefinisikan pemetaan
<math display="block">\begin{align}
a &\leftrightarrow 1 \\
b &\leftrightarrow 2 \\
c &\leftrightarrow 3
\end{align}</math>
Oleh karena setiap elemen dari himpunan <math>H = \left\{ a, \, b, \, c \right\}</math> dikawankan dengan ''tepat satu'' elemen dari himpunan <math>\left\{ 1, \, 2, \, 3 \right\}</math> (dan begitu juga sebaliknya), maka pemetaannya bersifat bijektif, dan menjadi bukti bahwa <math>H</math> adalah himpunan terhitung. Dengan cara serupa, maka dapat ditunjukkan bahwa setiap himpunan berhingga merupakan himpunan terhitung.
Pada kasus himpunan tak terhingga, suatu himpunan <math>H</math> dikatakan terhitung tak terhingga jika terdapat suatu [[bijeksi|fungsi bijektif]] dari <math>H</math> ke himpunan [[bilangan asli]] <math>\mathbb{N}</math>. Sebagai contoh, himpunan bilangan genap positif <math>\left\{ 2, \, 4, \, 6, \, 8, \, \ldots \right\}</math> merupakan himpunan terhitung tak terhingga, sebab terdapat korespondensi satu-ke-satu <math>n \leftrightarrow 2n</math> sebagai berikut:
<math display="block">\begin{align}
1 &\leftrightarrow 2 \\
2 &\leftrightarrow 4 \\
3 &\leftrightarrow 6 \\
4 &\leftrightarrow 8 \\
&\phantom{n} \vdots
\end{align}</math>
Setiap [[himpunan bagian]] dari bilangan asli merupakan himpunan terhitung. Secara umum,
{{math theorem | math_statement = Setiap himpunan bagian dari suatu himpunan terhitung merupakan himpunan terhitung.<ref>{{harvnb|Halmos|1960|page=91}}</ref>}}
[[File:Pairing natural.svg|thumb|300px|[[Fungsi pemasang|Fungsi pemasang Cantor]] mengawankan setiap bilangan asli dengan suatu pasangan bilangan asli.]]
Himpunan semua [[pasangan terurut]] (atau [[produk Cartesius|hasil-kali Kartesius]]) dari himpunan [[bilangan cacah]] <math>\mathbb{W} \times \mathbb{W}</math> merupakan himpunan terhitung tak terhingga. Hasil [[Peta (matematika)|pemetaannya]] dapat dilihat pada gambar di bagian kanan dan dilakukan sebagai berikut
<math display="block">\begin{align}
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{align}</math>
Pemetaan ini meliput seluruh pasangan terurut.
Bentuk pemetaan segitiga ini dapat diperumum secara [[rekursi|rekursif]] menjadi bilangan asli [[rangkap|rangkap-<math>n</math>]], yaitu <math>\left( a_1, \, a_2, \, a_3, \, \ldots, \, a_n \right)</math> dengan <math>a_k, \, n \in \mathbb{N}</math> untuk setiap <math>k \in \left\{ 1, \, 2, \, 3, \, \ldots, \, n \right\}</math>, dengan cara memetakan secara berulang dua elemen pertama dari rangkap-<math>n</math> nya ke suatu bilangan asli. Sebagai contoh, <math>\left( 0, \, 2, \, 3 \right)</math> dapat ditulis sebagai <math>\left( \left( 0, \, 2 \right), \, 3 \right)</math>. Perhatikan bahwa <math>\left( 0, \, 2 \right)</math> dipetakan ke <math>5</math>. Akibatnya, <math>\left( 0, \, 2, \, 3 \right)</math> dipetakan ke <math>\left( 5, \, 3 \right)</math>, yang kemudian dipetakan ke <math>39</math>. Oleh karena rangkap-<math>2</math> yang berbeda, yaitu pasangan terurut seperti <math>\left( a, \, b \right)</math>, dipetakan ke bilangan asli yng berbeda, maka perbedaan dua rangkap-<math>n</math> pada setidaknya satu elemen saja sudah cukup untuk menjamin rangkap-<math>n</math> nya dipetakan ke bilangan asli yang berbeda, sehingga terbukti bahwa terdapat suatu fungsi injektif dari himpunan rangkap-<math>n</math> ke himpunan bilangan asli <math>\mathbb{N}</math>. Secara umum, maka
{{math theorem | math_statement = [[Produk Cartesius|Hasil-kali Kartesius]] dari berhingga banyaknya himpunan terhitung merupakan himpunan terhitung.<ref>{{Harvard citation no brackets|Halmos|1960|page=92}}</ref>}}
{{math proof | proof = Perhatikan bahwa <math>\mathbb{N} \times \mathbb{N}</math> merupakan himpunan terhitung, sebab terdapat fungsi injektif<ref>{{Harvard citation no brackets|Avelsgaard|1990|page=182}}</ref> <math>f \, \colon \, \mathbb{N} \times \mathbb{N} \to \mathbb{N}</math> dengan
<math display="block">f \! \left( x, \, y \right) = 2^x \cdot 3^y</math>
Jika <math>A</math> dan <math>B</math> merupakan himpunan terhitung, maka terdapat fungsi surjektif
<math display="block">g \, \colon \, \mathbb{N} \to A \qquad \text{dan} \qquad h \, \colon \, \mathbb{N} \to B</math>
Berdasarkan informasi tersebut, fungsi <math>g \times h \, \colon \, \mathbb{N} \times \mathbb{N} \to A \times B</math> bersifat surjektif, sehingga <math>A \times B</math> merupakan himpunan terhitung. Hasil ini dapat diperumum menjadi hasil-kali Kartesius dari berhingga banyaknya himpunan terhitung dengan menggunakan [[induksi matematika]].}}
Himpunan semua [[bilangan bulat]] <math>\mathbb{Z}</math> dan himpunan semua [[bilangan rasional]] <math>\mathbb{Q}</math> secara intuitif terlihat lebih besar dari <math>\mathbb{N}</math>, namun penampilan bisa menipu. Jika pasangan terurut <math>\mathbb{N} \times \mathbb{N}</math> dipandang sebagai [[pecahan|pembilang]] dan [[pecahan|penyebut]] dari suatu pecahan biasa<ref>Pecahan dalam bentuk <math>\dfrac{a}{b}</math>, dengan <math>a</math> dan <math>b \neq 0</math> adalah suatu bilangan bulat</ref>, 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 <math>n</math> dapat dinyatakan sebagai pecahan <math>\dfrac{n}{1}</math>, 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.
{{math theorem | math_statement = Himpunan semua bilangan bulat <math>\mathbb{Z}</math>, himpunan semua bilangan rasional <math>\mathbb{Q}</math>, dan himpunan semua [[bilangan aljabar]] <math>\mathbb{A}</math> merupakan himpunan terhitung.}}
{{math proof | proof =
# Himpunan <math>\mathbb{Z}</math> merupakan himpunan terhitung, sebab terdapat fungsi injektif <math>f \, \colon \, \mathbb{Z} \to \mathbb{N}</math> dengan <math display="block">f(n) = \begin{cases}
2^n & n \geq 0 \\
3^{-n} & n < 0
\end{cases}</math>
# Himpunan <math>\mathbb{Q}</math> merupakan himpunan terhitung, sebab terdapat suatu fungsi surjektif <math>g \, \colon \, \mathbb{Z} \times \mathbb{N} \to \mathbb{Q}</math> dengan <math display="block">g \! \left( m, \, n \right) = \dfrac{m}{n + 1}</math>
# Berdasarkan definisi, setiap bilangan aljabar (termasuk [[bilangan kompleks]] merupakan akar persamaan dari suatu [[polinomial]] dengan koefisien bilangan bulat. Diberikan sembarang <math>a \in \mathbb{A}</math>, dan misalkan <math display="block">c_0 + c_1 x + c_2 x^2 + c_3 x^3 + \ldots + c_k x^k</math> adalah suatu polinomial dengan koefisien bilangan bulat sedemikian sehingga <math>a</math> adalah akar ke-<math>n</math> dari polinomial tersebut, dengan akar-akarnya diurutkan berdasarkan nilai mutlaknya dari kecil ke besar, lalu [[Argumen (analisis kompleks)|argumennya]] diurutkan dari kecil ke besar. Himpunan <math>\mathbb{A}</math> merupakan himpunan terhitung, sebab terdapat suatu fungsi injektif <math>h \, \colon \, \mathbb{A} \to \mathbb{N}</math> dengan <math display="block">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}</math> dimana <math>p_i</math> menyatakan [[bilangan prima]] ke-<math>i</math>.}}
Dalam beberapa kasus, penggunaan lebih dari satu pemetaan adalah hal yang membantu. Misalkan akan dibuktikan bahwa suatu himpunan <math>A</math> merupakan himpunan terhitung dan <math>A</math> bersifat injektif ke himpunan lain (katakanlah) <math>B</math>, maka himpunan <math>A</math> terbukti merupakan himpunan terhitung jika <math>B</math> bersifat injektif ke himpunan bilangan asli. Sebagai contoh, terdapat suatu fungsi injektif dari himpunan semua bilangan rasional positif ke pasangan (rangkap-<math>2</math>) bilangan asli, salah satunya ialah <math>\dfrac{p}{q} \leftrightarrow \left( p, \, q \right)</math> (dengan syarat <math>\operatorname{FPB} \! \left( p, \, q \right) = 1</math>). Oleh karena <math>\mathbb{N} \times \mathbb{N}</math> memiliki korespondensi satu-ke-satu dengan <math>\mathbb{N}</math> (seperti yang telah ditunjukkan sebelumnya), maka himpunan bilangan rasional positif terbukti merupakan himpunan terhitung.
{{math theorem | math_statement = Setiap [[Gabungan (teori himpunan)|gabungan]] berhingga dari himpunan-himpunan terhitung juga merupakan himpunan terhitung.<ref>{{Harvard citation no brackets|Avelsgaard|1990|page=180}}</ref><ref>{{Harvard citation no brackets|Fletcher|Patty|1988|page=187}}</ref>}}
{{math proof | proof = Misalkan <math>n \in \mathbb{N}</math> dan <math>N := \left\{ 1, \, 2, \, 3, \, \ldots, \, n \right\}</math>. Jika <math>A_k</math> adalah himpunan terhitung untuk setiap <math>k \in N</math>, maka terdapat fungsi-fungsi <math>f_k \, \colon \, \mathbb{N} \to A_k</math> yang bersifat surjektif. Akibatnya, fungsi
<math display="block">F \, \colon \, N \times \mathbb{N} \to \bigcup_{k \, = \, 1}^{n} A_k</math>
juga bersifat surjektif, dengan <math>F \! \left( k, \, x \right) = f_k \! \left( x \right)</math>. Oleh karena himpunan <math>N \times \mathbb{N}</math> merupakan himpunan terhitung, maka <math>\displaystyle \bigcup_{k \, = \, 1}^{n} A_k</math> 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.
{{math theorem | math_statement = Dengan mengasumsikan [[aksioma pemilihan terhitung]], maka setiap gabungan terhitung dari himpunan-himpunan terhitung juga merupakan himpunan terhitung.}}
{{math proof | proof = Misalkan <math>n \in \mathbb{N}</math>. Jika <math>A_k</math> adalah himpunan terhitung untuk setiap <math>k \in \mathbb{N}</math>, maka berdasarkan [[aksioma pemilihan terhitung]], terdapat fungsi-fungsi <math>f_k \, \colon \, \mathbb{N} \to A_k</math> yang bersifat surjektif.<ref>{{cite book
| last1 = Hrbacek
| first1 = Karel
| last2 = Jech
| first2 = Thomas
| title = Introduction to Set Theory, Third Edition, Revised and Expanded
| date = 22 June 1999
| publisher = CRC Press
| isbn = 978-0-8247-7915-3
| page = 141
| url = https://books.google.com/books?id=Er1r0n7VoSEC&pg=PA141
| language = en}}</ref> Oleh karena fungsi
<math display="block">F \, \colon \, \mathbb{N} \times \mathbb{N} \to \bigcup_{k \, = \, 1}^{n} A_i</math>
bersifat surjektif, dan bukan injektif, maka tidak ada syarat bahwa himpunannya harus bersifat saling asing.}}
[[File:Countablepath.svg|thumb|300px|"Pelabelan" dari terhitung banyaknya himpunan terhitung]]
Sebagai contoh, diberikan himpunan terhitung <math>A</math>, <math>B</math>, <math>C</math>, 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:
<math display="block">\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}</math>
[[Aksioma pemilihan terhitung]] diperlukan untuk memberikan indeks kepada ''semua'' himpunan <math>A</math>, <math>B</math>, <math>C</math>, <math>\ldots</math>, secara bersamaan.
{{math theorem | math_statement = Misalkan <math>A</math> dan <math>B</math> adalah himpunan.
# Jika fungsi <math>f \, \colon \, A \to B</math> bersifat injektif dan <math>B</math> adalah himpunan terhitung, maka <math>A</math> juga merupakan himpunan terhitung.
# Jika fungsi <math>g \, \colon \, A \to B</math> bersifat surjektif dan <math>A</math> adalah himpunan terhitung, maka <math>B</math> juga merupakan himpunan terhitung.}}
{{math proof | proof = Kedua hal ini merupakan akibat dari definisi himpunan terhitung sebagai fungsi injektif / surjektif.
# Jika <math>B</math> adalah himpunan terhitung, maka terdapat fungsi injektif <math>h \, \colon \, B \to \mathbb{N}</math>. Oleh karena fungsi <math>f</math> bersifat injektif, maka fungsi komposisi <math display="block">h \circ f \, \colon \, A \to \mathbb{N}</math> juga bersifat injektif, sehingga terbukti bahwa <math>A</math> merupakan himpunan terhitung.
# Jika <math>A</math> adalah himpunan terhitung, maka terdapat fungsi surjektif <math>h \, \colon \, \mathbb{N} \to A</math>. Oleh karena fungsi <math>g</math> bersifat surjektif, maka terdapat dua kasus yang mungkin terjadi: himpunan <math>A</math> dan <math>B</math> sama-sama merupakan [[himpunan kosong]], atau fungsi komposisi <math display="block">g \circ h \, \colon \, \mathbb{N} \to B</math> juga bersifat surjektif. Berdasarkan kedua kasus yang diperoleh, terbukti bahwa <math>B</math> merupakan himpunan terhitung.}}
[[Teorema Cantor]] menyatakan bahwa jika <math>X</math> adalah suatu himpunan dan <math>\mathcal{P} \! \left( X \right)</math> adalah [[himpunan kuasa|himpunan kuasa]] dari <math>X</math> (yaitu himpunan seluruh himpunan bagian dari <math>X</math>), maka tidak ada fungsi surjektif dari <math>X</math> ke <math>\mathcal{P} \! \left( X \right)</math>. Pembuktian dari pernyataan ini dapat dilihat pada artikel [[teorema Cantor]]. Salah satu akibat dari teorema ini ialah
{{math theorem | math_statement = Himpunan <math>\mathcal{P} \! \left( \mathbb{N} \right)</math> bukan merupakan himpunan terhitung; atau dengan kata lain, himpunannya [[Himpunan takterhitung|tak terhitung]].}}
== Lihat juga ==
* [[Bilangan alef]]
* [[Pencacahan]]
* [[Paradoks hotel Hilbert]]
* [[Himpunan takterhitung]]
== Rujukan ==
{{reflist}}
== Referensi ==
* {{En icon}}{{Citation | first1=Tom M. | last1=Apostol | author-link=Tom M. Apostol | title=Multi-Variable Calculus and Linear Algebra with Applications | location=New York | publisher=John Wiley + Sons | edition=2nd | series=Calculus | volume=2 | isbn=978-0-471-00007-5 | date=June 1969 | url-access=registration | url=https://archive.org/details/calculus00apos}}
* {{En icon}}{{citation | first=Carol|last=Avelsgaard|title=Foundations for Advanced Mathematics|year=1990|publisher=Scott, Foresman and Company|isbn=0-673-38152-8}}
* {{En icon}}{{Citation | first = Georg | last = Cantor | title = Ein Beitrag zur Mannigfaltigkeitslehre | url = http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002156806 | volume = 1878 | issue = 84 | pages = 242–248 | journal = Journal für die Reine und Angewandte Mathematik | year = 1878 | doi = 10.1515/crelle-1878-18788413| s2cid = 123695365 }}
* {{En icon}}{{Citation | last = Ferreirós | first = José | title = Labyrinth of Thought: A History of Set Theory and Its Role in Mathematical Thought | publisher = Birkhäuser | year = 2007 | edition = 2nd revised | isbn = 978-3-7643-8349-7}}
* {{En icon}}{{citation|first1=Peter|last1=Fletcher|first2=C. Wayne|last2=Patty|title=Foundations of Higher Mathematics|year=1988|publisher=PWS-KENT Publishing Company|location=Boston|isbn=0-87150-164-3}}
* {{En icon}}{{citation|first=Paul R.|last=Halmos|author-link=Paul Halmos|title=Naive Set Theory|trans-title=Teori Himpunan Naif|year=1960|publisher=D. Van Nostrand Company, Inc|title-link=Teori himpunan naif}} Reprinted by Springer-Verlag, New York, 1974. {{ISBN|0-387-90092-6}} (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011. {{ISBN|978-1-61427-131-4}} (Paperback edition).
* {{En icon}}{{citation|first=Erich|last=Kamke|author-link=Erich Kamke|title=Theory of Sets|year=1950|publisher=Dover|location=New York|isbn=978-0486601410|series=Dover series in mathematics and physics}}
* {{En icon}}{{Citation | last1=Lang | first1=Serge | author1-link=Serge Lang | title=Real and Functional Analysis | publisher=Springer-Verlag | location=Berlin, New York | isbn=0-387-94001-4 | year=1993}}
* {{En icon}}{{Citation | last1=Rudin | first1=Walter | author1-link=Walter Rudin | title=Principles of Mathematical Analysis | publisher=McGraw-Hill| location=New York | isbn=0-07-054235-X | year=1976}}
* {{En icon}}{{cite book |last1=Tao |first1=Terence |title=Analysis I |date=2016 |publisher=Springer |location=Singapore |isbn=978-981-10-1789-6 |pages=181–210 |edition=3 |chapter-url=https://link.springer.com/chapter/10.1007/978-981-10-1789-6_8 |chapter=Infinite sets|series=Texts and Readings in Mathematics |volume=37 |doi=10.1007/978-981-10-1789-6_8 }}
{{Portal bar|Aritmetika|Matematika}}
{{Number systems}}
{{Logika matematika}}
{{Teori himpunan}}
[[Kategori:Konsep dasar dalam teori himpunan tak hingga]]
[[Kategori:Bilangan kardinal]]
[[Kategori:Tak hingga]]
| |||