[Math] Prove; Powerset Cardinality is $2^n$ – I have trouble understanding the prove.

elementary-set-theoryinduction

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

Prove:

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$

Best Answer

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.

Related Question