In Example 7.2.8 a one-to-one correspondence was defined from the power set of {a, b} to

Chapter 7, Problem 56

(choose chapter or problem)

In Example 7.2.8 a one-to-one correspondence was defined from the power set of {a, b} to the set of all strings of 0’s and 1’s that have length 2. Thus the elements of these two sets can be matched up exactly, and so the two sets have the same number of elements.

a. Let \(X=\left\{x_{1}, x_{2}, \ldots, x_{n}\right\}\) be a set with n elements. Use Example 7.2.8 as a model to define a one-to-one correspondence from \(\mathscr{P}(X)\), the set of all subsets of X, to the set of all strings of 0’s and 1’s that have length n.

b. Use the one-to-one correspondence of part (a) to deduce that a set with n elements has \(2^{n}\) subsets. (This provides an alternative proof of Theorem 6.3.1.)

Text Transcription:

X={x_1, x_2, ldots, x_n}

mathscr P(X)

2^n