Please help with this question. Show that for a finite set $A$ of cardinality $n$, the cardinality of $P(A)$ is $2^n$, where $P(A)$ is the power set of $A$. Thank you in advance for any help that is given.
The number of subsets of a set of cardinality $n$
-
1possible duplicate of [Proving number of subsets of a set size $n$ via induction](http://math.stackexchange.com/questions/44908/proving-number-of-subsets-of-a-set-size-n-via-induction) – 2011-09-06
7 Answers
Think of how you could go about constructing a subset of $A$. For each element, you choose to either include it or exclude it from the subset you are building. That gives you 2 choices for each of the $n$ elements of $A$. Multiplying your choices together, you get $2^n$ total possibilities. That is, there are $2^n$ different subsets you can build from $A$.
HINT:
Suppose I am choosing elements to put in some subset of the power set. Then each element can either be in, or not be in, my subset. So this means that altogether...
-
0Well done. A good hint. – 2011-09-06
Number the elements of $A$ as $a_1, a_2, \dots, a_n$. Consider the map $\chi:P(A) \to \{0,1\}^n$ given by $\chi(X)=(x_1,x_2,\dots,x_n)$, where $x_i=1$ iff $a_i \in X$. Then $\chi$ is a bijection.
-
1This seems like rather sophisticated language and notation for such an elementary question. Is there really anything here that is not in, say, Austin's answer? – 2011-09-06
So this is a finite set?
The most direct hands-on least abstract method would the this:
Start with the set $\{\} = \emptyset$. That's one subset so far.
List the elements in order $a_1, ......., a_k$.
Take the first element $a_1$. You have two options: Add it to the subset you have so far and get the subset $\{a_1\}$; or don't add it to the subset you have so far and still have the subset $\{\}$.
You now have two subsets. $\{a_1\}$ and $\{\}$. You have doubled the number of subsets by include new subsets by adding $\{a_1\}$.
Now Take the second element $a_2$. You have two options: Add it to the subsets you have so far and get the subsest $\{a_1,a_2\}$ and $\{a_2\}$; or don't add it to the subsets you have so far and still have the subset $\{\}$ and $\{a_1\}$.
You now have four subsets. $\{a_1,a_2\}$ and $\{a_2\}$ as well as $\{a_1\}$ and $\{\}$. You have doubled the number of subsets by include new subsets by adding $\{a_2\}$.
Do the same thing for each of the elements. Each time you will be doubling the number subsets.
In the end you will have $2^k$ subsets.
...
A slightly more abstract but far more sophisticated argument would by to consider.
Map a subset $E \in P(A)$ ($E \subset A$) and consider than the numbers $b_i$ where $b_i = 1$ if $a_i \in A$ and $b_i = 0$ if $a_i \not \in A$. Now consider then number $K_E = \sum_{i=1}^k b_i*2^{i-1}$.
(Example: $K_{\emptyset} = 0$ all $b_i = 0$ because $\emptyset$ has no elements. And $K_{\{a_1,a_3, a_4\}} = 13$ because $b_1=b_3=b_4 = 1$ but all other $b_i = 0$ and $K_{\{a_1,a_3, a_4\}} = 1*2^0 + 1*2^2 + 1*2^3 = 13$.)
This mapping is a one-to-one mapping of all the subsets to all then numbers from $0$ to $2^k -1$.
Each subset $S$ of $A$ can be formed by considering each element of $A$ and deciding whether or not that element is to be in the subset.
There are two choices for each element $a$ of $A$ -- either the element $a$ is in $S$, or it is not. Each distinct set of choices (one for each element of $A$) determines a unique subset of $A$. So, since there are $k$ elements with $2$ possible choices each, there is a total of
$\underbrace{2\times2\times\cdots\times 2}_{k\textrm{ factors}}=2^k$ different subsets.
Multiplication is used because you are using "and" to combine the choices. For example, "$a_1$ is in $S$, and $a_2$ is in $S$, and $a_3$ is not in $S$, and etc".
-
0I've always been rather fond of this argument; ***endorsed (+ 1)!!!***. Cheers! – 2018-06-29
We observe that the binomial theorem yields
$2^k = (1 + 1)^k = \displaystyle \sum_{r = 0}^k \dfrac{k!}{r! (k - r)!} 1^r 1^{k - r} = \sum_{r = 0}^k \dfrac{k!}{r! (k - r)!}; \tag 1$
but
$\dfrac{k!}{r! (k - r)!} \tag 2$
is precisely the number of ways we may choose $r$ elements from a set $A$ with $\vert A \vert = k$, irrespective of order; thus it is the number of $r$-element subsets of $A$. It follows then that the sums occurring in (1) count all subsets of $A$, whence
$\vert P(A) \vert = \displaystyle \sum_{r = 0}^k \dfrac{k!}{r! (k - r)!} = 2^k = 2^{\vert A \vert}, \tag 3$
as per request.
I like the functional analysis flavor of considering the set of all functions $f:Y\to X$, denoted $X^Y$. The order of this set is $\lvert X\rvert ^{\lvert Y\rvert}$ (which justifies the notation).
Now, in the case of the power set, $P(Y)$, (which again is appropriately named) we need only decide whether a given element is in a given subset or not: each subset corresponds to a function $f:Y\to \{0,1\}$, with $f(y)=0$ if $y$ is not in the subset, and $f(y)=1$ if it is.
Since here $\lvert X\rvert=\lvert \{0,1\}\rvert =2$, and $\lvert Y\rvert =k$, we get $\lvert P(Y)\rvert =\lvert X^Y\rvert =\lvert X\rvert ^{\lvert Y\rvert}=2^k$...