Discrete Mathematics
This is a preserved file from cs2102 Fall 2016. An updated version may exist at https://uvacs2102.github.io/

Class 10: In(tro)duction


Schedule

Problem Set 4 is due Friday at 6:29pm.

Next week, you should finish reading MCS Chapter 5 (Induction). Another presentation of Induction is Chapter 10 from the Book of Proof (you are not required to read this, but it is encouraged and has lots more examples of proofs by induction).

Exam 1 will be in class on Thursday, 6 October.

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.

###