10
$\begingroup$

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.

  • 0
    I changed $2n$ to $2^n$, and edited in some TeX.2011-09-06
  • 1
    possible 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 3

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...

  • 0
    Well 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.

  • 1
    This 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