Himpunan terhitung

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  dikatakan terhitung jika:
 Himpunan  adalah himpunan hingga atau terhitung tak berhingga.
 Kardinalitasnya (dinotasikan dengan ) tidak lebih dari  (alef nol), yaitu kardinalitas dari himpunan bilangan asli .
 Terdapat suatu fungsi injektif dari  ke .
 Himpunan  merupakan himpunan kosong atau terdapat suatu fungsi surjektif dari  ke .
 Terdapat suatu fungsi bijektif antara  dan suatu himpunan bagian dari .
Semua definisi di atas ekuivalen satu sama lain.

Suatu himpunan  dikatakan terhitung tak terhingga jika:
 Kardinalitasnya (yaitu ) sama dengan .
 Terdapat suatu pemetaan injektif dan surjektif antara  dan .
 Himpunan  memiliki korespondensi satu-ke-satu dengan .
 Elemen dari himpunan  dapat disusun dalam suatu barisan tak terhingga , dengan  ketika , dan setiap elemen pada  terdaftar.

Suatu himpunan disebut tak terhitung jika himpunannya tidak terhitung, atau dengan kata lain, kardinalitasnya lebih dari .

 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.Cantor 1878, p. 242. 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.Ferreirós 2007, pp. 268, 272–273.

 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 , , dan  dapat dituliskan sebagai , 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 ("") digunakan untuk mewakilkan banyak elemen di antara elemen awal dan akhir pada suatu himpunan, jika penulis yakin bahwa pembaca dapat menebak dengan mudah apa yang tanda elipsis wakilkan; sebagai contoh,  mungkin saja menyatakan himpunan bilangan bulat dari  sampai dengan . Dalam kasus ini, semua elemennya masih mungkin didaftarkan, sebab banyak elemennya berhingga. Jika setiap elemen dari himpunan , , dan seterusnya, sampai  diberi label, maka hal ini menjadi definisi dari "himpunan berukuran ".

Beberapa himpunan merupakan himpunan tak terhingga; himpunan-himpunan ini memiliki lebih dari  elemen, dengan  adalah sembarang bilangan asli. Tidak peduli seberapa besar nilai  nya (seperti ), himpunan tak terhingga memiliki lebih dari  elemen. Misalnya, himpunan bilangan asli, yang dinyatakan sebagai ,Oleh karena terdapat bijeksi antara bilangan asli  dan bilangan cacah , maka tidak masalah apabila bilangan  dianggap sebagai bilangan asli atau bukan. Mengesampingkan hal tersebut, artikel ini mengikuti ISO 31-11 dan konvensi standar dalam logika matematika, yang menyatakan bahwa  adalah bilangan asli. 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:

dan secara umum,  (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 .

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  disebut terhitung jika terdapat suatu fungsi bijektif dari  ke himpunan bagian dari bilangan asli . Sebagai contoh, didefinisikan pemetaan

Oleh karena setiap elemen dari himpunan  dikawankan dengan tepat satu elemen dari himpunan  (dan begitu juga sebaliknya), maka pemetaannya bersifat bijektif, dan menjadi bukti bahwa  adalah himpunan terhitung. Dengan cara serupa, maka dapat ditunjukkan bahwa setiap himpunan berhingga merupakan himpunan terhitung.

Pada kasus himpunan tak terhingga, suatu himpunan  dikatakan terhitung tak terhingga jika terdapat suatu fungsi bijektif dari  ke himpunan bilangan asli . Sebagai contoh, himpunan bilangan genap positif  merupakan himpunan terhitung tak terhingga, sebab terdapat korespondensi satu-ke-satu  sebagai berikut:

Setiap himpunan bagian dari bilangan asli merupakan himpunan terhitung. Secara umum,

Himpunan semua pasangan terurut (atau hasil-kali Kartesius) dari himpunan bilangan cacah  merupakan himpunan terhitung tak terhingga. Hasil pemetaannya dapat dilihat pada gambar di bagian kanan dan dilakukan sebagai berikut

Pemetaan ini meliput seluruh pasangan terurut.

Bentuk pemetaan segitiga ini dapat diperumum secara rekursif menjadi bilangan asli rangkap-, yaitu  dengan  untuk setiap , dengan cara memetakan secara berulang dua elemen pertama dari rangkap- nya ke suatu bilangan asli. Sebagai contoh,  dapat ditulis sebagai . Perhatikan bahwa  dipetakan ke . Akibatnya,  dipetakan ke , yang kemudian dipetakan ke . Oleh karena rangkap- yang berbeda, yaitu pasangan terurut seperti , dipetakan ke bilangan asli yng berbeda, maka perbedaan dua rangkap- pada setidaknya satu elemen saja sudah cukup untuk menjamin rangkap- nya dipetakan ke bilangan asli yang berbeda, sehingga terbukti bahwa terdapat suatu fungsi injektif dari himpunan rangkap- ke himpunan bilangan asli . Secara umum, maka

Himpunan semua bilangan bulat  dan himpunan semua bilangan rasional  secara intuitif terlihat lebih besar dari , namun penampilan bisa menipu. Jika pasangan terurut  dipandang sebagai pembilang dan penyebut dari suatu pecahan biasa,Pecahan dalam bentuk , dengan  dan  adalah suatu bilangan bulat 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  dapat dinyatakan sebagai pecahan , 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  merupakan himpunan terhitung dan  bersifat injektif ke himpunan lain (katakanlah) , maka himpunan  terbukti merupakan himpunan terhitung jika  bersifat injektif ke himpunan bilangan asli. Sebagai contoh, terdapat suatu fungsi injektif dari himpunan semua bilangan rasional positif ke pasangan (rangkap-) bilangan asli, salah satunya ialah  (dengan syarat ). Oleh karena  memiliki korespondensi satu-ke-satu dengan  (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.

Sebagai contoh, diberikan himpunan terhitung , , , 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:

Aksioma pemilihan terhitung diperlukan untuk memberikan indeks kepada semua himpunan , , , , secara bersamaan.

Teorema Cantor menyatakan bahwa jika  adalah suatu himpunan dan  adalah himpunan kuasa dari  (yaitu himpunan seluruh himpunan bagian dari ), maka tidak ada fungsi surjektif dari  ke . Pembuktian dari pernyataan ini dapat dilihat pada artikel teorema Cantor. Salah satu akibat dari teorema ini ialah

 Lihat juga 
 Bilangan alef
 Pencacahan
 Paradoks hotel Hilbert
 Himpunan takterhitung

 Rujukan 

 Referensi 





  Reprinted by Springer-Verlag, New York, 1974.  (Springer-Verlag edition). Reprinted by Martino Fine Books, 2011.  (Paperback edition).





Kategori:Konsep dasar dalam teori himpunan tak hingga
Kategori:Bilangan kardinal
Kategori:Tak hingga