Subsets [ml={1,2,.,n} Power set:2lm ={SSC [n]} 2=10,1=2m Combinatorial proof: Sm=>Xs∈0,1mXs()={ igs one-to-one correspondence Subsets |{0, 1}n| = 2n one-to-one correspondence [n] = {1, 2,...,n} ￾ ￾ ￾ 2[n] ￾ ￾ ￾ = S ✓ [n] ￾S 2 {0, 1}n ￾S(i) = ( 1 i 2 S 0 i 62 S 2[n] = {S | S ✓ [n]} Combinatorial proof: Power set: