The number of subsets of a set of cardinality $n$ 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.
 A: 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$.
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...
A: 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.
A: 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".
A: 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$.
A: 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$...
A: 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.
