I have trouble to understand the Induction step of the following prove.

Can someone explain to me what happens in the Induction step 3. and 4.?

I don't really get the idea which is used, or it is simply not understandable enough written for me.

Prove source: https://proofwiki.org/wiki/Cardinality_of_Power_Set


For all $n \in \mathbb{N}$, let $P(n)$ be the proposition: $$|S| = n \implies |\mathcal{P}(S)| = 2^n $$ where $\mathcal{P}(S)$ is the powerset of $S$

Basis for the Induction:

  1. It holds $ S = \emptyset \Longleftrightarrow |S| = 0 $.
  2. Then $\mathcal{P}(S) = \{\emptyset\}$, such that $|\mathcal{P}(S)| = 1 = 2^0$.
  3. From (1.) and (2.) it follows that proposition $P(0)$ holds.
Induction Hypothesis:

We need to show that, if $P(k)$ is true, where $k \geq 2$, then it logically follows that $P(k+1)$ is true. So if this is our Induction Hypothesis: $$ |S| = k \implies |\mathcal{P}(S)| = 2^k $$ We need to show that: $$ |S| = k+1 \implies |\mathcal{P}(S)| = 2^{k+1} $$

Induction Step:

  1. Let $|S| = k+1$ and let $x \in S$.
  2. Consider the sets $S' = S \backslash \{x\}$, where $x$ is some element of $S$. We see that $|S'| = k$
  3. We now adjoin $x$ to all the subsets of $S'$. Counting the subsets of $S$, we have: all the subsets of $S'$ and all the subsets of $S'$ with $x$ adjoined to them.
  4. From the Induction Hypothesis, there are $2^k$ subsets of $S'$. Adding $x$ to each of these, does not change their number, so there are another $2^k$ subsets of $S$, consisting of all the subsets $S'$ with $x$ adjoined to them.
  5. In total that makes $2^k + 2^k = 2 \cdot 2^k = 2^{k+1}$ subsets of $S$. So $P(k) \implies P(k+1)$ and the result follows by the principle of mathematical induction.
  6. Therefore: $\forall n \in \mathbb{N} : |S| = n \implies |\mathcal{P}(S)| = 2^n$
  • $\begingroup$ What is the problem ? There are those sets with $x$ and those without $x$. $\endgroup$ – Rene Schipperus Oct 22 '17 at 13:56
  • $\begingroup$ Hm I see, it was really confusing to me, that they adjoin $x$ to $S'$ and then talk about counting the subsets in $S'$ and $S'$ with $x$ adjoined. Maybe they should use different names these two sets, then it would be clearer. $\endgroup$ – Derping Oct 22 '17 at 14:21

I'll illustrate with an example. Let's say we have a four element set $S = \lbrace 1, 2, 3, 4 \rbrace$. We know that, given any three element set, it has $2^3 = 8$ subsets.

Let's take out our $x$ from $S$ to form a three element set $S'$. I'm going to choose $x = 2$, for no particular reason, so $S' = \lbrace 1, 3, 4 \rbrace$. Under the induction hypothesis, we assume $S'$ has $8$ subsets, which are the following: $$\lbrace \rbrace, \lbrace 1 \rbrace, \lbrace 3 \rbrace, \lbrace 4 \rbrace, \lbrace 1, 3 \rbrace, \lbrace 3, 4 \rbrace, \lbrace 1, 4\rbrace, \lbrace 1, 3, 4 \rbrace.$$ Note that the above list are all subsets of $S$; the fact that none of them contain $x = 2$ doesn't change this. In fact these are all the sets we can form without choosing $x = 2$. We can get the rest of the sets by adding in $x = 2$ into each of the sets, to get another $8$ subsets: $$\lbrace 2 \rbrace, \lbrace 1, 2 \rbrace, \lbrace 2, 3 \rbrace, \lbrace 2, 4 \rbrace, \lbrace 1, 2, 3 \rbrace, \lbrace 2, 3, 4 \rbrace, \lbrace 1, 2, 4\rbrace, \lbrace 1, 2, 3, 4 \rbrace.$$ Try to convince yourself that the two collections of subsets form all subsets of $S'$. Every subset of $S$ that doesn't contain $2$ corresponds uniquely with a subset of $S$ that does contain $2$. We know there are $2^3$ of the former, and due to this relationship, there must also be $2^3$ of the latter. So, in total, we have $2^3 + 2^3 = 2 \cdot 2^3 = 2^4$ subsets.


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.