31
$\begingroup$

Theorem. Let $X$ denote an arbitrary set such that $|X|=n$. Then $|\mathcal P(X)|=2^n$.

Proof. The proof is by induction on the numbers of elements of $X$.

For the base case, suppose $|X|=0$. Clearly, $X=\emptyset$. But the empty set is the only subset of itself, so $|\mathcal P(X)|=1=2^0$.

Now, the induction step. Suppose $|X|=n$; by the induction hypothesis, we know that $|\mathcal P(X)|=2^n$. Let $Y$ be a set with $n+1$ elements, namely $Y=X\cup\{a\}$. There are two kinds of subsets of $Y$: those that include $a$ and those that don't. The first are exactly the subsets of $X$, and there are $2^n$ of them. The latter are sets of the form $Z\cup\{a\}$, where $Z\in\mathcal P(X)$; since there are $2^n$ possible choices for $Z$, there must be exactly $2^n$ subsets of $Y$ of which $a$ is an element. Therefore $|\mathcal P(Y)|=2^n+2^n=2^{n+1}$. $\square$

Image that replaced text.

From the above explanation, I don't understand why the set that contains $\{a\}$ will contain $2^{|n|}$ elements when it should clearly be $2^{|1|}$.

The construction of a new set $S$ is the union of the old set with cardinality $n$ and a new element $\{a\}$, therefore the set that does not contain $\{a\}$ still has cardinality $n$ and the set that contains $\{a\}$ is just $\{a\}$, one element.

Can someone please elucidate?

$\endgroup$
1
  • 2
    $\begingroup$ It is the sets that contain $a$. $\endgroup$ Sep 14, 2014 at 16:45

6 Answers 6

24
$\begingroup$

You misread the proof. Since set $X$ has $n$ elements, the induction hypothesis tells us that $|\mathcal{P}(X)| = 2^n$. The set $Y = X \cup \{a\}$ has $n + 1$ elements. It subsets are either subsets of $X$, of which there are $2^n$ by the induction hypothesis, or the union of a subset $Z$ of $X$ with $\{a\}$. By the induction hypothesis, there are $2^n$ subsets $Z$ of $X$. Hence, there are $2^n$ subsets of the form $Z \cup \{a\}$ of the set $Y$. Hence, $Y$ has $2^n$ subsets that do not contain $a$ and $2^n$ subsets that do contain $a$ for a total of $2^n + 2^n = 2 \cdot 2^n = 2^{n + 1}$ subsets of $Y$, which is what the author wants to show.

$\endgroup$
4
  • 1
    $\begingroup$ Sorry, you lost me on the fourth sentence. Can you show me explicitly what is $Z$? $\endgroup$
    – Fraïssé
    Sep 14, 2014 at 17:00
  • $\begingroup$ Oh I think I see it now, could you elaborate whether if I take the union of two sets say {A,B} U {C}, do I get {A, B, C} or {A, B, {A,C}, {B,C}}? $\endgroup$
    – Fraïssé
    Sep 14, 2014 at 17:11
  • 1
    $\begingroup$ @ Aåkon I think it's the former. He introduced $Z$ ($2^{n}$ times) to show that $\mid \mathcal{P}(Y) \setminus \mathcal{P}(X) \mid = \mid \mathcal{P}(X)\mid$ $\endgroup$ Feb 9, 2019 at 13:02
  • $\begingroup$ @N.F .Taussig: There are a confusing point in this proof. You state that $Y = X \cup \{a \}$ has as its subsets either subsets of $X$, or unions of $\{a\}$ with subsets $Z$ of $X$. But what is the proof of this assumption? $\endgroup$
    – Edward.Lin
    Feb 25 at 18:56
24
$\begingroup$

Here is an another, combinatorial proof. Let $X$ be a set with $n$ elements. To form a subset of $X$, we go over each element of $X$ and exercise a choice of whether or not to include in the subset. Every sequence of choices gives a different subset.

Since for every element, there are 2 choices, for $n$ elements, there are $2 \times 2 \times ...$ $n$ times, choices.

Therefore, there are $2^n$ distinct subsets of $X$.

$\endgroup$
1
  • 1
    $\begingroup$ this explanation was very clear to understand $\endgroup$ Jul 23, 2018 at 4:54
10
$\begingroup$

Suppose you've already shown that $X=\{1,2\}$ has $2^2=4$ subsets, namely ${\cal P}(X)=\{\emptyset,\{1\},\{2\},X\}$. Now you add a new element $a=3$ to get $Y=X\cup \{a\}=\{1,2,3\}$. The four subsets of $X$ are also subsets of $Y$, but you get new subsets - those which contain $a$, e.g. $\{1,3\}$. But each of these is one of the ones you already had together with the new $a$, e.g. $\{1,3\}$ is $\{1\} \cup \{3\}$.

So, the new ones are $\emptyset \cup \{3\}$, $\{1\} \cup \{3\}$, $\{2\} \cup \{3\}$, and $X \cup \{3\}$ and those are exactly as much as you already had - four of them. Which implies that ${\cal P}(Y)$ has twice as much elements (the old ones and the new ones) as ${\cal P}(X)$, so $2\times2^2=2^3=8$.

$$ \begin{array}{|c|c|} \hline \text{Subsets of }X&\text{New subsets}\\ \hline \emptyset&\{3\}\\ \hline \{1\}&\{1,3\}\\ \hline \{2\}&\{2,3\}\\ \hline X&Y\\ \hline \end{array} $$

$\endgroup$
3
$\begingroup$

Alternative proof:

Represent a subset of $X$ as a binary number such that its $k^{th}$ bit is set if and only if the $k^{th}$ element is taken.

E.g., $\{a,b,c\}\to111$, $\{a,c\}\to101$, $\{c\}\to001$, ...

You can convince yourself that the two representations are equivalent, and that the second includes all binary numbers from $0$ to $2^{|X|}-1$.


Note that if you add an element, the subset of $X$ with signature $m$ generates two new subsets, with signatures $2m$ and $2m+1$.

$\endgroup$
1
$\begingroup$

I will prove the claim by induction. First suppose $|A|=1$. That is, $A=\{a_1\}$. Thus, $P(A) =\{ \{a\}, \{ \emptyset \} \}$. So, it can be concluded that $|A|=2^1=2$. My inductive hypothesis is that $|A|=n$ and $|P(A)|=2^n$. Now let's consider $A'$, where $A'$ is $A$ with one new element added, call it $a_{n+1}$. That is to say $A'= \{a_1,a_2,a_3,\dots,a_{n+1} \}$. When considering $P(A')$ two types of sets arise, those containing $a_{n+1}$ and those that do not. Allow $B_i$ to represent any particular member of $P(A)$. Notice that $|P(A')|=|P(A)|+|B_k \cup\{a_{n+1}\}|$, for all $k\in \mathbb{N}$ satisfying $1\leq k\leq 2^n$. Therefore $|P(A')|=2^n+2^n=2\cdot 2^n=2^{n+1}$. $\square$

$\endgroup$
1
$\begingroup$

Here is another one that uses the Binomial Theorem.

Take, for example, the set $A = \{1, 2, 3, 4\}$

Then, $P(A) = \{∅, \{1\}, \{2\}, \{3\}, \{4\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{2, 4\}, \{3, 4\}, \{4, 1\}, \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 1\}, \{4, 1, 2\}, \{1, 2, 3, 4\}\}$

In $P(A)$, see that the number of subsets with cardinality 0 is 1, there are 4 subsets with cardinality 1, 6 with cardinality 2, then 4 again with 3 and then 1 more with cardinality 4. $\pmb{1-4-6-4-1}$; $16$ total. Note that these are the coefficients of the terms when you expand the binomial theorem (binomial coefficients) with $n=4$.

Now we want the sum of these numbers. This is can be easily achieved by replacing $x=y=1$ in the binomial formula where $n$ is the cardinality of set A and the formula follows from there.


Why the pattern appears is very simple. Let $n$ be $|A|$. You want to fill subsets of cardinalities $0, 1, \cdots,\ n$. You have n elements to choose from. So to fill the first subset with cardinality 0, you use $\binom{n}{0}$, for the second with cardinality 1 we use $\binom{n}{1}$ and so on.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.