Jawab:
Kalau tau bahwa banyak himpunan bagian dari suatu himpunan S adalah
[tex](\# \text{himpunan bagian dari S}) = \displaystyle{2^{\#S}}[/tex]
maka
a.) Karena banyak himpunan bagian dari P adalah 32, didapat
[tex]32 = (\# \text{himpunan bagian dari P}) = \displaystyle{2^{\#P}}[/tex]
maka banyak himpunan P, yaitu [tex]\#P[/tex] adalah
[tex]\#P = ^2\log(32) = 5[/tex]
b.) Karena banyak himpunan bagian dari Q adalah 1, didapat
[tex]1 = (\# \text{himpunan bagian dari P}) = \displaystyle{2^{\#Q}}[/tex]
maka banyak himpunan Q, yaitu [tex]\#Q[/tex] adalah
[tex]\#Q = ^2\log(1) = 0[/tex].
Pembuktian [tex](\# \text{himpunan bagian dari S}) = \displaystyle{2^{\#S}}[/tex]
Dengan induksi,
(kasus dasar)
untuk kasus [tex]S = \emptyset[/tex] , yaitu [tex]\#S = 0[/tex] didapat
[tex]\{\text{A : A himpunan bagian dari S} \} = \{\emptyset\}[/tex]
sehingga banyak himpunan bagian dari S adalah 1.
(asumsi benar untuk S dengan [tex]\#S = n[/tex])
Jika benar untuk semua himpunan S dengan [tex]\#S = n[/tex] berlaku
[tex](\# \text{himpunan bagian dari S}) = \displaystyle{2^{\#S}} = 2^n[/tex] , maka
(pembuktian untuk [tex]\#T= n+1[/tex])
jika untuk sembarang himpunan [tex]T[/tex] dengan [tex]\#T= n+1[/tex], kita dapat tulis
[tex]T = \{t_1,t_2,...,t_n,t_{n+1}\} = \{t_1,t_2,...,t_n\} \cup \{t_{n+1}\}[/tex]
kita bisa membentuk subhimpunan dari [tex]T[/tex] dengan cara membentuk subhimpunan terlebih dahulu pada himpunan [tex]\{t_1,t_2,...,t_n\}[/tex] (Terdapat [tex]2^n[/tex] cara dari asumsi induksi), lalu memutuskan apakah mengikutsertakan [tex]t_{n+1}[/tex] masuk pada subhimpunan tersebut (ada 2 cara).
Dari aturan perkalian didapat
[tex](\# \text{himpunan bagian dari T}) = \displaystyle{2^{\#\{t_1,t_2,...,t_n\}}} = 2^n 2 = 2^{n+1}[/tex]
Karena sudah terbukti pada kasus n+1. maka terbukti pernyataan bahwa
[tex](\# \text{himpunan bagian dari S}) = \displaystyle{2^{\#S}}[/tex] untuk semua himpunan berhingga [tex]S.[/tex]
[answer.2.content]
