Let A be a finite, nonempty set of cardinality n, and let P(A) denote the set...

 

Transcribed Image Text:

Let A be a finite, nonempty set of cardinality n, and let P(A) denote the set of all subsets of A (called the power set of A). (a) Find a bijection f (A) {0,1}", where {0,1}" denotes the Cartesian product of n copies of {0, 1}. Prove that your function is a bijection. Hint: Which n-tuple is a natural choice for f(0)? Which n-tuple is a natural choice for f(A)? How might you relate the 1's and 0's in an n-tuple to the elements of a subset? (b) Use question 1(b) to determine, with proof, the cardinality of P(A). Let A be a finite, nonempty set of cardinality n, and let P(A) denote the set of all subsets of A (called the power set of A). (a) Find a bijection f (A) {0,1}", where {0,1}" denotes the Cartesian product of n copies of {0, 1}. Prove that your function is a bijection. Hint: Which n-tuple is a natural choice for f(0)? Which n-tuple is a natural choice for f(A)? How might you relate the 1's and 0's in an n-tuple to the elements of a subset? (b) Use question 1(b) to determine, with proof, the cardinality of P(A).