Pembuktian Rumus Banyak Subset Dalam Sebuah Himpunan

Posted by Fandi on Tuesday, January 17, 2017 in sains | 1 comment

Assalamu ‘alaikum,,

Terdapat sebuah rumus yang menyatakan bahwa, sebuah himpunan dengan  “n” anggota memiliki himpunan bagian sebanyak 2 ⁿ. bagaimana cara membuktikannya ? berikut uraiannya :

Didefinisikan F merupakan sebuah himpunan dengan anggota sebanyak n, dapat dituliskan sebagai :

 

Ambil sebarang satu elemen dari himpunan F yaitu a_k dengan k ≤ n , kemudian pisahkan himpunan bagian dari himpunan F menjadi dua kelompok, yaitu kelompok yang memuat a_k dan kelompok yang tidak memuat a_k. kedua kelompok tersebut dapat dilihat pada tabel dibawah

Misalkan banyak himpunan bagian dari himpunan F dinyatakan dengan S(n) berarti banyak subset dari himpunan F yang tidak memuat a_k adalah S(n-1). Tabel di atas juga menunjukkan bahwa banyak subset dari himpunan F yang memuat a_k sama dengan yang tidak memuat a_k berarti

Hasil yang sama didapatkan apabila melakukan hal seperti di atas pada himpunan dengan (n-1) elemen , seperti berikut

Berarti

Sama dengan sebelumnya, akan didapatkan

Dengan melanjutkan hal yang sama hingga (n – 1) kali, didapatkan

Berarti

Karena banyak subset pada himpunan yang memiliki satu anggota adalah 2 atau S(1) = 2 , maka