###### Problem 360

###### (a)

Write down a list of the subsets of \(\{1, 2 \}\text{.}\) Don't forget the empty set! Group the sets containing containing 2 separately from the others.

###### (b)

Write down a list of the subsets of \(\{1, 2, 3 \}\text{.}\) Group the sets containing 3 separately from the others.

###### (c)

Look for a natural way to match up the subsets containing 2 in PartÂ a with those not containing 2. Look for a way to match up the subsets containing 3 in PartÂ b containing 3 with those not containing 3.

###### (d)

On the basis of the previous part, you should be able to find a bijection between the collection of subsets of \(\{1, 2, \ldots , n \}\) containing \(n\) and those not containing \(n\text{.}\) (If you are having difficulty figuring out the bijection, try rethinking PartsÂ a and b, perhaps by doing a similar exercise with the set \(\{1,2,3,4\}\text{.}\)) Describe the bijection (unless you are very familiar with the notation of sets, it is probably easier to describe to describe the function in words rather than symbols) and explain why it is a bijection. Explain why the number of subsets of \(\{1, 2, \ldots , n \}\) containing \(n\) equals the number of subsets of \(\{1, 2, \ldots, n-1 \}\text{.}\)

###### (e)

PartsÂ a and b suggest strongly that the number of subsets of a \(n\)-element set is \(2^n\text{.}\) In particular, the empty set has \(2^0\) subsets, a one-element set has \(2^1\) subsets, itself and the empty set, and in PartsÂ a and b we saw that two-element and three-element sets have \(2^2\) and \(2^3\) subsets respectively. So there are certainly some values of \(n\) for which an \(n\)-element set has \(2^n\) subsets. One way to prove that an \(n\)-element set has \(2^n\) subsets for all values of \(n\) is to argue by contradiction. For this purpose, suppose there is a nonnegative integer \(n\) such that an \(n\)-element set doesn't have exactly \(2^n\) subsets. In that case there may be more than one such \(n\text{.}\) Choose \(k\) to be the smallest such \(n\text{.}\) Notice that \(k -1\) is still a positive integer, because \(k\) can't be 0, 1, 2, or 3. Since \(k\) was the smallest value of \(n\) we could choose to make the statement âAn \(n\)-element set has \(2^n\) subsetsâ false, what do you know about the number of subsets of a \((k - 1)\)-element set? What do you know about the number of subsets of the \(k\)-element set \(\{1, 2, \ldots, k \}\) that don't contain \(k\text{?}\) What do you know about the number of subsets of \(\{1, 2, \ldots, k \}\) that do contain \(k\text{?}\) What does the sum principle tell you about the number of subsets of \(\{1, 2, \ldots, k \}\text{?}\) Notice that this contradicts the way in which we chose \(k\text{,}\) and the only assumption that went into our choice of \(k\) was that ``there is a nonnegative integer \(n\) such that an \(n\)-element set doesn't have exactly \(2^n\) subsets." Since this assumption has led us to a contradiction, it must be false. What can you now conclude about the statement ``for every nonnegative integer \(n\text{,}\) an n-element set has exactly \(2^n\) subsets?"