Return to Homework 1, Glossary, Theorems
Problem 1
Let $A$ be a finite set of order $n$. Based on the preceding exercise, make a conjecture about the value of $|\mathcal{P}(A)|$. Then try to prove your conjecture.
Solution
First, we must show that there are $2^{n}$ subsets for a set of order $n$. The empty set is the only subset of itself so $2^{0} = 1$, which is true. Now, assume there are $2^{k}$ subsets for a set, $B$, with $k$ elements. Consider, $A = B \cup \{y\}$, where $y \notin B$. Consider each of the subsets of $A$. $A$ has each of the subsets of $B$, and the element $y$ is either an element or not an element of each of the subsets. Hence, $A$ has $2 \cdot 2^{k} = 2^{k+1}$ subsets. Since a set, $A$, of order $n$ has $2^{n}$ subsets and the $\mathcal{P}(A)$ is the set of all of the subsets, $\mathcal{P}(A)$ must have $2^{n}$ elements.