By now we've seen the basics of number theory, including the Divison Theorem, Euclid's algorithm, modular arithmetic, and the notions of prime and relatively prime numbers. There's more to see but in order to progress any further, we're going to need another tool in our mathematical toolbox: Induction.
In lecture 4, we defined the natural numbers as follows: \begin{align*} \mathbb{N} =& \emptyset & \text{(corresponding to $0$)} \\ \text{or } & n \cup \{n\} & \text{(corresponding to $n+1$)} \end{align*}
In the late 1800s, Giuseppe Peano presented an even simpler definition of the natural numbers that relied on only two symbols: \begin{align*} \mathbb{N} =~& 0 & \\ \text{or } & S~n & \text{where $n$ is a number} \end{align*}
$S$ is just a symbol here, standing for successor. In this system, we would write $1$ as $S~n$ and $5$ as $S~(S~(S~(S~(S~n))))))$. Essentially, this is just counting with your fingers.
There's a nice correspondence here with how you would define a list in most functional programming languages. Here's Haskell:
data List a = Nil
| Cons a (List a)
Since $0$ and $S~n$ together define all the numbers, it should make sense that if a proposition $P$ is true about $0$ and adding an $S$ preserves $P$'s truth, then $P$ is always true. Formally:
Definition 9.1. Axiom of Induction: For any proposition $P$ about a natural number if:
Let's prove something in Peano arithmetic. To begin with, here's Peano's definition of $+$.
Note that the definition doesn't say that $n + 0 = n$. So let's prove it ourselves - by induction!
Theorem 9.2. $\forall n, n+0 = n$
Using these axioms, we can prove all of the desired properties of $+$, $\times$, and $\leq$, including commutativity, associativity and the transitivity of $\leq$. These make great exercises for practicing induction.
There is an injured shark thrashing about in the water. Nearby there are $n$ sharks. Each would like to eat the injured shark but would become injured in the process and potential victims of the remaining sharks. Every shark is perfectly logical and values its life more than eating. What will happen?
Feel free to give this puzzle some thought. Assume there is always a closest shark that could, if it chose to, eat the injured shark.
A good way to think about such puzzles (and math problems broadly!) is to consider small numbers. Let's do that.
There's an emerging pattern here, so let's state our theorem.
Theorem 9.3
Note that we started with the $0$ case which was trivial. That doesn't matter, $0$ remains the smallest number. In this case it might feel tempting to also prove the $n=1$ case, which is fine as long as we prove the $0$ case as well. In the future we will see some proofs where it's acceptable to start with some $n>0$, because the claim starts with "if $n$ is greater than $5$ then..." But even in those cases, we can start with zero (we might just have to consider in our inductive hypothesis whether $k$ is $5$).
If you enjoy these kinds of problems, try the Blue Eyes logic puzzle. (If you have brown eyes, I hope you don't find yourself on an island with 99 blue eyed people and a green eyed guru.)
Now let's jump back to set theory. In lecture four we stated the following theorem.
Theorem 4.8. If $A$ is a finite set, then $|\mathcal P(A)| = 2^{|A|}$.
Now, using induction, we can prove this.
Proof. We will prove this by induction on the size of $A$, $n = |A|$.
Base case. We have $|A| = 0$ and therefore, $A = \emptyset$. Then $\mathcal P(A) = \{\emptyset\}$. Observe that $|P(\emptyset)| = |\{\emptyset\}| = 1 = 2^0$.
Inductive case. Let $n = k$ and assume that for every set $X$ with $|X| = k$, then $|\mathcal P(X)| = 2^k$. Let $|A| = k+1$ and we will show that $|\mathcal P(A)| = 2^{k+1}$.
Choose an element $a \in A$. We define the set $A' = \{x \in A \mid x \neq a\}$ containing all elements of $A$ except $a$. Then $|A'| = |A| - 1$, since we removed $a$. Then $|A'| = k$ and by our inductive hypothesis, $|\mathcal P(A')| = 2^k$.
Now, consider a subset of $A'$, $B \in \mathcal P(A')$. For each subset $B \subseteq A'$, we can obtain two subsets of $A$, $B$ and $B \cup \{a\}$. Therefore, we have $2 \cdot 2^k = 2^{k+1}$ subsets of $A$. $\tag*{$\Box$}$