Power Sets (continued from Class 9)

The power set of $A$ ($\textrm{pow}(A)$) is the set of all subsets of $A$: $B \in \textrm{pow}(A) \iff B \subseteq A$.

Prove that the size of the power set of a set $S$ with $|S| = N$ is $2^N$.

Proof using Well-Ordering Principle

The goal is to prove for all sets $A$: $|\textrm{pow}(A)| = 2^{|A|}$.

Recall (from Class 9) that $N_k = { n | n \in \mathbb{N} \wedge n < k } $ and $|\mathbb{N}_n| = n$.

Because of the bijection between any set $A$ where $|A| = n$ to $\mathbb{N}_n$, we can prove the general property by showing $\forall n \in \mathbb{N} \ldotp P(n)$ where $P(n) ::= |\textrm{pow}(\mathbb{N}_n)| = 2^n$.

We follow the structure of every well-ordering proof:

1. Define the set of counterexamples: $$ C ::= { n \in \mathbb{N} | \quad |\textrm{pow}(\mathbb{N}_n)| \neq 2^n } $$
2. Assume $C$ is $\fillin\fillin\fillin$.
3. By the well-ordering principle, there must be some smallest element, $m \in C$.

4. Reach a contradiction: we show that $\fillin\fillin\fillin$ holds.

   • Since $m$ is the smallest element of $C$, $P(n)$ must hold for all $\fillin\fillin\fillin$.
   • We know $P(0)$ is true since $\mathbb{N}_0 = \emptyset$ and $\textrm{pow}(\emptyset) = \fillin\fillin\fillin\fillin$. We have, $|\textrm{pow}(\mathbb{N}_0)| = \fillin\fillin = \fillin\fillin$, satisfying $P(0)$.
   • Thus, $m > 0$. This means $m - 1 \in \mathbb{N}$.
   • So, we know $P(\fillin\fillin)$ holds.
   • Thus, we can construct $\textrm{pow}(\mathbb{N}{m})$ by keeping all the elements of $\textrm{pow}(\mathbb{N}{m - 1})$ and adding each of those elements with $(m-1)$ inserts. More formally, $$ \textrm{pow}(\mathbb{N}m) = \textrm{pow}(\mathbb{N}{m - 1}) \quad \cup \bigcup{S \in \textrm{pow}(\mathbb{N}{m - 1})} (S \cup \fillin\fillin\fillin) $$ The size of this set is $2 |\textrm{pow}(\mathbb{N}{m - 1})|$ since it contains two sets for each set in $\textrm{pow}(\mathbb{N}{m - 1})$ (the original one, and the one with $m-1$ added, which we know is a new set since $m - 1 \notin \mathbb{N}_{m - 1}$).
     
   • Since $P(m-1)$, we know $|\textrm{pow}(\mathbb{N}{m - 1})| = \fillin\fillin\fillin$. The size of the new set, $|\textrm{pow}(\mathbb{N}{m})| = 2 \cdot 2^{m - 1} = 2^{m}$. This means that $P(m)$ holds.

5. Hence, $C$ must be empty. We reached a contradiction using the well-ordering principle by showing the $P(m)$ holds for $m \in C$, which must mean the $C$ is empty. If there are no counter-examples, then $P(n)$ holds for all $n \in \mathbb{N}$.

Induction Principle

Let $P$ be a predicated on $\mathbb{N}$. If

• $P(0)$ is true, and
• $P(n) \implies P(n + 1)$ for all $n \in \mathbb{N}$,

then

• $P(m)$ is true for all $m \in \mathbb{N}$.

Template for Induction Proofs

1. State, “We prove by induction.”
2. Define a predicate, $P(n)$. This is the induction hypothesis. Our goal is to show that $P(n)$ is true for all $n \in \mathbb{N}$.
3. Prove $P(0)$ is true. (base case or basis step.)
4. Prove that $P(n) \implies P(n + 1)$ for every $n \in \mathbb{N}$. (induction step)
5. Conclude that $P(n)$ is true for all $n \in \mathbb{N}$ by induction.

How is the method of proof by induction principle similar to and different from proof by well-ordering principle?

Induction Practice

Prove the non-negative integers are well ordered by the induction principle.

###

Prove the power set size property, $|\textrm{pow}(A)| = 2^{|A|}$, by induction.

###