Modul (Pendahuluan 1.3) Himpunan Hingga Dan Himpunan Tak Hingga [PDF]

Citation preview

SUB BAB 1.3 HIMPUNAN HINGGA DAN TAK HINGGA Ketika kita menghitung unsur dari suatu himpunan, kita selalu berkata “satu, dua, tiga,…” kemudian berhenti jika sudah semuanya terhitung. Dari suatu perspektif matematis, apa yang kita lakukan didefinisikan sebagai suatu pemetaan bijektif antara himpunan tersebut dengan suatu bagian dari bilangan asli ℕ. Jika himpunan tersebut ketika kita menghitung anggotanya tidak akan pernah terhenti, seperti himpunan bilangan asli itu sendiri, maka kita mendeskripsikan himpunan tersebut menjadi himpunan tak hingga. Istilah “hingga” dan “tak hingga” sebenarnya sudah sangat primitif, dan sangat mungkin bahwa kita tidak pernah memeriksa gagasan ini dengan sangat hati-hati. Pada bagian ini kita akan mendefinisikan istilah-istilah ini secara tepat beserta konsekuensi mendasar yang perlu untuk diketahui. 1.3.1 Definisi (a) Himpunan kosong ∅ dikatakan memiliki sejumlah 𝟎 unsur (b) Jika 𝑛 ∈ ℕ, suatu himpunan 𝑆 dikatakan memiliki sejumlah 𝒏 unsur jika terdapat suatu bijeksi dari ℕ𝑛 = {1,2,3, … , 𝑛} pada 𝑆 (c) Suatu himpunan 𝑆 dikatakan hingga jika 𝑆 = ∅ atau 𝑆 memiliki sejumlah 𝑛 unsur untuk suatu 𝑛 ∈ ℕ. (d) Suatu himpunan 𝑆 dikatakan tak hingga jika himpunan tersebut tidak hingga.



Mari kita ingat kembali bahwa invers dari suatu bijeksi adalah suatu bijeksi, hal ini mudah untuk melihat bahwa suatu himpunan 𝑆 memiliki 𝑛 unsur jika dan hanya jika terdapat suatu bijeksi dari 𝑆 pada himpunan {1,2,3, … , 𝑛}. Selain itu, karena komposisi dari dua bijeksi adalah suatu bijeksi, maka kita dapat melihat bahwa pada suatu himpunan 𝑆1 memiliki 𝑛 unsur jika dan hanya jika 𝑆2 memiliki 𝑛 unsur. Lebih lanjut, suatu himpunan 𝑇1 hingga jika dan hanya jika terdapat suatu bijeksi dari 𝑇1 pada himpunan lain yaitu 𝑇2 dimana 𝑇2 merupakan himpunan hingga. Sekarang kita perlu untuk menentukan beberapa sifat dasar dari himpunan hingga agar yakin bajwa definisi yang kita miliki tidak mengarah pada kesimpulan yang bertentangan dengan pengalaman kita sebelumnya dalam berhitung. 1.3.2. Teorema Ketunggalan Jika 𝑆 adalah suatu himpunan hingga, maka jumlah unsur dari 𝑆 adalah suatu bilangan yang tunggal di ℕ. 1.3.3. Teorema Himpunan bilangan asli ℕ adalah suatu himpunan tak hingga.



1.3.4. Teorema (a) Jika 𝐴 adalah himpunan dengan 𝑚 unsur, 𝐵 adalah himpunan dengan 𝑛 unsur, dan 𝐴 ∩ 𝐵 = ∅, maka 𝐴 ∪ 𝐵 memiliki 𝑚 + 𝑛 unsur. (b) Jika 𝐴 adalah suatu himpunan dengan 𝑚 ∈ ℕ dan 𝐶 ⊆ 𝐴 adalah suatu himpunan dengan 1 unsur, maka 𝐴\𝐶 dengan 𝑚 − 1 unsur. (c) Jika 𝐶 adalah suatu himpunan tak hingga dan 𝐵 adalah himpunan hingga, maka 𝐶\𝐵 adalah himpunan tak hingga. Bukti. (a) Misal 𝐴 adalah himpunan dengan 𝑚 unsur, 𝐵 adalah himpunan dengan 𝑛 unsur, dan 𝐴 ∩ 𝐵 = ∅. Akan dibuktikan bahwa, 𝐴 ∪ 𝐵 memiliki 𝑚 + 𝑛 unsur. Perhatikan bahwa, 𝐴 memiliki 𝑚 unsur, maka terdapat bijeksi sebut 𝑓 dari ℕ𝑚 pada 𝐴. 𝐵 memiliki 𝑛 unsur, maka terdapat bijeksi sebut 𝑔 dari ℕ𝑛 pada 𝐵. Untuk membuktikan 𝐴 ∪ 𝐵 memiliki 𝑚 + 𝑛 unsur, kita akan mendefinisikan ℎ pada ℕ𝑚+𝑛 = {1,2, … , 𝑚, 𝑚 + 1, 𝑚 + 2, … 𝑚 + 𝑛} dengan ℎ(𝑖) = 𝑓(𝑖) untuk 𝑖 = 1,2, … , 𝑚, dan ℎ(𝑖) = 𝑔(𝑖 − 𝑚) untuk 𝑖 = 𝑚 + 1, 𝑚 + 2, … 𝑚 + 𝑛. Akan dibuktikan bahwa ℎ merupakan fungsi bijektif dari ℕ𝑚+𝑛 pada 𝐴 ∪ 𝐵. Pertama, akan ditunjukkan bahwa ℎ injektif. Ambil sebarang anggota 𝑖1 , 𝑖2 ∈ ℕ𝑚+𝑛 dengan ℎ(𝑖1 ) = ℎ(𝑖2 ). Maka diperoleh dua kasus yaitu ℎ(𝑖) = 𝑓(𝑖) atau ℎ(𝑖) = 𝑔(𝑖 − 𝑚). Pada kasus pertama, ℎ(𝑖1 ) = ℎ(𝑖2 ), maka 𝑓(𝑖1 ) = 𝑓(𝑖2 ) 𝑖1 = 𝑖2 Karena 𝑓 bijektif. Pada kasus kedua, ℎ(𝑖1 ) = ℎ(𝑖2 ), maka 𝑔(𝑖1 − 𝑚) = 𝑔(𝑖2 − 𝑚), 𝑖 − 𝑚 = 1,2, … 𝑛 𝑖1 − 𝑚 = 𝑖2 − 𝑚 𝑖1 = 𝑖2 Dari dua kasus di atas, diperoleh bahwa, ℎ adalah fungsi injektif. Kedua, akan ditunjukkan bahwa ℎ surjektif. Ambil sebarang 𝑦 dari 𝐴 ∪ 𝐵. Akan dibuktikan terdapat 𝑖 ∈ ℕ𝑚+𝑛 dengan ℎ(𝑖) = 𝑦. Karena 𝑦 ∈ 𝐴 ∪ 𝐵 dan 𝐴 ∩ 𝐵 = ∅ maka terdapat dua kasus yang tak mungkin terjadi bersamaan, 𝑦 ∈ 𝐴 atau 𝑦 ∈ 𝐵. Untuk 𝑦 ∈ 𝐴, karena 𝑓 surjektif pilih 𝑖 ∈ ℕ𝑚+𝑛 dimana 𝑓(𝑖) = 𝑦. Dengan demikian, ℎ(𝑖) = 𝑓(𝑖) = 𝑦 Untuk 𝑦 ∈ 𝐵, karena 𝑔 surjektif pilih 𝑖 ∈ ℕ𝑚+𝑛 dimana 𝑖 − 𝑚 ∈ ℕ𝑛 dan 𝑔(𝑖 − 𝑚) = 𝑦. Maka ℎ(𝑖) = 𝑔(𝑖 − 𝑚) = 𝑦.



Karena ℎ injektif dan surjektif, maka benar bahwa ℎ adalah suatu bijeksi dari ℕ𝑚+𝑛 pada 𝐴 ∪ 𝐵. Artinya, 𝐴 ∪ 𝐵 berisi 𝑚 + 𝑛 unsur. qed (b) dan (c) pembuktian diserahkan kepada pembaca. 1.3.5. Teorema Misalkan 𝑆 dan 𝑇 adalah himpunan dan 𝑇 ⊆ 𝑆. (a) Jika 𝑆 adalah himpunan hingga, maka 𝑇 adalah suatu himpunan hingga. (b) Jika 𝑇 adalah himpunan tak hingga, maka 𝑆 adalah suatu himpunan tak hingga. Bukti (a) Misal 𝑆 adalah himpunan hingga, dan 𝑇 ⊆ 𝑆. Akan dibuktikan 𝑇 adalah himpunan hingga. Jika 𝑇 = ∅ maka jelas bahwa 𝑇 adalah hingga. Jika 𝑇 ≠ ∅, maka akan dibuktikan secara induksi pada jumlah anggota dari 𝑆. Misal 𝑃(𝑛): Himpunan 𝑆 memiliki 𝑛 unsur maka 𝑇 ≠ ∅ dengan𝑇 ⊆ 𝑆 merupakan himpunan hingga. Jika 𝑛 = 1 maka S memiliki 1 unsur, maka 𝑇 haruslah sama dengan 𝑆, sehingga 𝑇 himpunan hingga. Artinya 𝑃(1) benar. Asumsikan, himpunan 𝑆 memiliki 𝑘 unsur maka 𝑇 ≠ ∅ dengan 𝑇 ⊆ 𝑆 merupakan himpunan hingga. Selanjutnya, misalkan 𝑆 memiliki 𝑘 + 1 unsur. Maka akan ada bijeksi 𝑓 dari ℕ𝑘+1 pada 𝑆. Sekarang misal 𝑇 ⊆ 𝑆. Jika 𝑓(𝑘 + 1) ∉ 𝑇, kita dapat mempertimbangkan 𝑇 sebagai subset dari 𝑆1 = 𝑆\{𝑓(𝑘 + 1)}, yang memiliki 𝑘 unsur. Maka dengan hipotesis induksi, diperoleh 𝑇 merupakan himpunan hingga. Di sisi lain jika 𝑓(𝑘 + 1) ∈ 𝑇, maka 𝑇1 = 𝑇\{𝑓(𝑘 + 1)} dan 𝑇1 ⊆ 𝑆1 . Karena 𝑆1 memiliki 𝑘 unsur, dengan hipotesis induksi diperoleh 𝑇1 merupakan himpunan hingga. Hal ini mengakibatkan 𝑇 = 𝑇1 ∪ {𝑓(𝑘 + 1)} adalah himpunan hingga. Qed (b) Bukti dari pernyataan ini dapat ditarik kesimpulan menggunakan kontrapositif dari pernyataan (a).



Himpunan Terhitung Sekarang kita akan mempelajari tentang tipe dari himpunan tak hingga. 1.3.6. Definisi (a) Suatu himpunan 𝑆 dikatakan denumerable (tak hingga terhitung) jika terdapat suatu bijeksi dari ℕ pada 𝑆.



(b) Suatu himpunan 𝑆 dikatakan terhitung jika 𝑆 hingga atau 𝑆 denumerable. (c) Suatu himpunan 𝑆 dikatakan tak terhitung jika 𝑆 tidak terhitung. Dari sifat bijeksi, akan jelas bahwa 𝑆 denumerabel jika dan hanya jika terdapat suatu bijeksi dari 𝑆 pada ℕ. Selain itu, bahwa suatu himpunan 𝑆1 dikatakan denumerabel jika dan hanya jika terdapat suatu bijeksi dari 𝑆1 pada 𝑆2 yang denumerabel. Lebih lanjut, suatu himpunan 𝑇1 terhitung jika dan hanya jika terdapat suatu bijeksi dari 𝑇2 dimana 𝑇2 terhitung. Hingga akhirnya, suatu himpunan yang tak hingga terhitung adalah denumerabel. 1.3.7. Contoh (a) Himpunan 𝐸 = {2𝑛: 𝑛 ∈ ℕ} sebagai himpunan bilangan genap adalah denumerabel, karena terdapat pemetaan 𝑓: ℕ → 𝐸 yang didefinisikan dengan 𝑓(𝑛) = 2𝑛 untuk 𝑛 ∈ ℕ yang merupakan bijeksi dari ℕ pada 𝐸. Dengan cara serupa, diperoleh 𝑂 = {2𝑛 − 1: 𝑛 ∈ ℕ} yaitu sebagai himpunan bilangan ganjil adalah denumerabel. (b) Himpunan ℤ sebagai himpunan semua bilangan bulat juga denumerabel. Dalam mengonstruksi suatu bijeksi dari ℕ pada ℤ, kita memetakan 1 pada 0, kita petakan himpunan bilangan asli genap pada bilangan bulat positif, dan kita petakan himpunan bilangan asli ganjil kecuali 1 pada himpunan bilangan bulat negative. Pemetaan dapat ditunjukkan dengan pencacahan sebagai berikut: ℤ = {0,1, −1,2, −2,3, −3, … }. (c) Gabungan dari dua himpunan disjoin yang denumerabel adalah himpunan yang denumerabel Pastilah, jika 𝐴 = {𝑎1 , 𝑎2 , 𝑎3 , . . } dan 𝐵 = {𝑏1 , 𝑏2 , 𝑏3 , … }, kita dapat mencacah unsur dari 𝐴 ∪ 𝐵 sebagai: 𝑎1 , 𝑏1 , 𝑎2 , 𝑏2 , 𝑎3 , 𝑏3 , … 1.3.8. Teorema Himpunan ℕ × ℕ adalah denumerabel. 1.3.9. Teorema Misal 𝑆 dan 𝑇 adalah himpunan dan 𝑇 ⊆ 𝑆. (a) Jika 𝑆 adalah himpunan terhitung, maka 𝑇 adalah himpunan terhitung. (b) Jika 𝑇 adalah himpunan tak terhitung, maka 𝑆 adalah himpunan tak terhitung. 1.3.10. Teorema Pernyataan berikut adalah ekuivalent: (a) 𝑆 adalah himpunan terhitung. (b) Terdapat suatu surjeksi dari ℕ pada 𝑆. (c) Terdapat suatu injeksi dari 𝑆 ke ℕ.



1.3.11. Teorema Himpunan ℚ berupa semua bilangan rasional adalah denumerabel.



Latihan 1.3 1. Buktikan bahwa suatu himpunan tak kosong 𝑇1 adalah hingga jika dan hanya jika terdapat suatu bijeksi dari 𝑇1 pada suatu himpunan hingga 𝑇2 . 2. Buktikan teorema bagian (b) dan (c) pada teorema 1.3.4 3. Misalkan 𝑆 = {1,2} dan 𝑇 = {𝑎, 𝑏. 𝑐} (a) Tentukan banyaknya injeksi berbeda dari 𝑆 ke 𝑇. (b) Tentukan banyaknya surjeksi berbeda dari 𝑇 pada 𝑆. 4. Tunjukkan suatu bijeksi antara ℕ dan himpunan semua bilangan bulat ganjil lebih dari 13. 5. Buktikan bahwa suatu himpunan 𝑇1 denumerabel jika dan hanya jika terdapat suatu bijeksi dari 𝑇1 pada suatu himpunan 𝑇2 yang denumerabel. 6. Berikan suatu contoh dari suatu kumpulan terhitung dari himpunan hingga yang gabungannya tidak hingga. 7. Buktikan dengan detail bahwa jika 𝑆 dan 𝑇 adalah denumerabel, maka 𝑆 ∪ 𝑇 denumerabel. 8. Gunakan PIM untuk membuktikan bahwa jika 𝑆 memiliki 𝑛 unsur, maka 𝒫(𝑆) = 2𝑛 .