17
$\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 hypotesis, 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 an new element $\{a\}$, therefore the set that do not contain $\{a\}$ still has cardinality $n$ and the set that contains $\{a\}$ is just $\{a\}$, one element...

Can someone please elucidate?

$\endgroup$
  • 1
    $\begingroup$ It is the sets that contain $a$. $\endgroup$ – André Nicolas Sep 14 '14 at 16:45
9
$\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$
  • $\begingroup$ Sorry, you lost me on the fourth sentence. Can you show me explicitly what is $Z$? $\endgroup$ – Carlos - the Mongoose - Danger Sep 14 '14 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$ – Carlos - the Mongoose - Danger Sep 14 '14 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$ – Chandran Goodchild Feb 9 at 13:02
10
$\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$
  • $\begingroup$ this explanation was very clear to understand $\endgroup$ – Sujal Mandal Jul 23 '18 at 4:54
5
$\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$
0
$\begingroup$

You say : The construction of a new set S is the union of the old set with cardinality n and an new element {a}, therefore the set that do not contain {a} still has cardinality n and the set that contains {a} is just {a}, one element...

Consider the old set $S$ of cardinality $n$ whose power set has cardinality $2^n$. What is the power set of $S \cup \{a\}$. Each set $T \in \mathcal P (S)$ gives rise to two sets in $\mathcal P(S \cup \{a\})$, one which contains $a$ and one which does not. Thus, you have $2 \times 2^n$ sets in $\mathcal P(S \cup \{a\})$.

$\endgroup$

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.