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.

  • 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

7 Answers 7

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
3

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
1

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

0

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

  • 0
    I've always been rather fond of this argument; ***endorsed (+ 1)!!!***. Cheers!2018-06-29
0

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.

0

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