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:
Subsets [ml={1,2,..,n} Power set:2lml ={SS C [n]} 2= A not-so-combinatorial proof: Let f(u)=2iml f(n)=2f(n-1)
Subsets A not-so-combinatorial proof: Let f(n)=2f(n 1) [n] = {1, 2,...,n} 2[n] = f(n) = 2[n] 2[n] Power set: = {S | S ✓ [n]}
f6m)=l2网 f(n)=2f(n-1) 2m={S E [n]|n年S}U{Scm|n∈S} 2川=2-川+}2-川=20m-1） Sum rule: finite disjoint sets S and T SUT=S+T
f(n)=2f(n 1) Sum rule: finite disjoint sets S and T |S T| = |S| + |T| = 2f(n 1) f(n) = 2[n] 2[n] = 2[n] = 2[n1] 2[n1] + {S ✓ [n] | n 62 S} {S ✓ [n] | n 2 S}
Subsets [ml={1,2,.,n} Power set:2lm={SSC [n]} 2叫=2 Let f(n)=2in f(n)=2f(n-1) f(0)=1201=1
Subsets f(n)=2f(n 1) f(0) = |2| = 1 Power set: [n] = {1, 2,...,n} 2[n] = Let f(n) = 2[n] 2n 2[n] = {S | S ✓ [n]}
Three rules Sum rule: finite disjoint sets S and T SUT=S+T Product rule: finite sets S and T |S×TI=IS1·IT到 Bijection rule: finite sets S and T 3φ：S 1-1T→lS1=T到 on-to
Three rules Product rule: |S ⇥ T| = |S|·|T| finite sets S and T Sum rule: finite disjoint sets S and T |S T| = |S| + |T| Bijection rule: finite sets S and T ⇤ : S 11 ⇥ onto T = |S| = |T|