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$
10
$\begingroup$
combinatorics
elementary-set-theory
-
0I changed $2n$ to $2^n$, and edited in some TeX. – 2011-09-06
-
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
3 Answers
6
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$.
4
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
4
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