Strong Induction Principle

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

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

then

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

As an inference rule:

$$ \infer{\forall m \in \mathbb{N} . P(m)}{P(0), \forall n \in \mathbb{N} . (P(0) \vee P(1) \wedge \cdots \wedge P(n)) \implies P(n + 1)} $$

With arbitrary basis, $b \in \mathbb{N}$:

$$ \infer{\forall m \in { b, b+1, b+2, \ldots } . P(m)}{P(b), \forall n \in \mathbb{N} . (P(b) \vee P(b + 1) \wedge \cdots \wedge P(n)) \implies P(n + 1)} $$

Show that strong induction is not actually stronger than regular induction. (Hint: if the predicate for strong induction is $P(m)$, explain how to construct a predicate, $P’(m)$, that works with regular induction.)

##

Example Strong Induction Proof

Theorem: Every number, $n \in \mathbb{N}, n \geq 4$ can be written as $\alpha \cdot 2 + \beta \cdot 5$ where $\alpha, \beta \in \mathbb{N}$.

Proof by Strong Induction:

1. First we need to define the predicate: $$P(n) := \exists \alpha, \beta \in \mathbb{N} . n = \alpha \cdot 2 + \beta \cdot 5$$.

2. Basis: we are proving for all $n > 3$:

   $P(4)$: $\alpha = 2, \beta = 0$ gives $4 = 2 \cdot 2 + 0 \cdot 5$. $P(5)$: $\alpha = 0, \beta = 1$ gives $5 = 0 \cdot 2 + 1 \cdot 5$.

3. Induction step: $\forall n \in {6, \ldots }$

   By strong induction, assume $P(m)$ is true for all $m \in { 4, 5, 6, \ldots, m}$.

   Show $P(m + 1)$: Since $P(m - 1)$ is true (by the \emph{strong} induction hypothesis), we know $\exists \alpha, \beta \in \mathbb{N} . m - 1 = \alpha \cdot 2 + \beta \cdot 5$. We can show $P(m + 1)$ since $m + 1 = (\alpha + 1) \cdot 2 + \beta \cdot 5$.

Proof by Contra-Positive (Review)

Recall: $P \implies Q$ is equivalent to $\neg Q \implies \neg P$. (If you are shaky on this, prove it to yourself using a truth table.)

Typical use: where the negation of the proposition is easier to reason about than the original proposition (e.g., irrational is a complex property to describe, but rational (NOT irrational) is a simple one. So to prove that ``If $r$ is irrational then $\sqrt{r}$ is also irrational” we can prove the contrapositive which is “if $\sqrt{r}$” is rational, then $r$ is also rational$ which is quite straightforward.

Proof by Contradiction (Review)

To prove $P$, show $\neg P \implies False$.

Example: Proving the $\mathbb{Z}$ is not well ordered.

Goal: proving the proposition $G$ saying ``$\mathbb{Z}$ has no minimum”.

1. To prove by contradiction, assume $\neg G$ (that is, $\mathbb{Z}$ does have a minimum).

2. Then, $\exists m \in \mathbb{Z}$ that is the minimum of $\mathbb{Z}$.

3. But, this leads to a contradiction: $m - 1 \in \mathbb{Z}$ and $m - 1 < m$. So, even though the number $m$ was said to be the minimum of $\mathbb{Z}$, it is in fact not the minimum.

4. Thus, we have a contradiction, so something must be wrong. All our logical inferences after step 1 are correct, so the assumption we made in step 1 must be invalid. If $\neg G$ is invalid, $G$ must be true.

Typical use: when the statment we want to prove has universal quantifier. for example, $\forall x \in \mathbb{Z}. P(x)$. Note that the statment that $\mathbb{Z}$ has \emph{no} minimum, when written formally, uses a universal quantifier (make sure to double check it). Then, instead of arguing that for all $x \in A$, $P(x)$ holds, we assume (for sake of contradiction) that there exists one $x$ for which $\neg(P(x))$ (note that this is indeed the negated statement) from which we get a contradiction.

Binary Relation Properties

When we draw the graph of binary relations, the Domain (input" set) has outgoing edges. Codomain (output” set) has incoming edges. So when we use the compact notation referring to different properties of binary relations, keep in mind that the words ``in-out” refer to the edge (not the input/output sets). The properties about outgoing edges are function ($\le 1 out$) and total ($\ge 1$ out). Adding elements to the codomain cannot effect these properties. The properties about incoming edges are surjection ($\ge 1$ in) and injection ($\le 1$ in). Adding elements to the domain cannot effect these properties.

When we say the any relation with property $X$ (e.g., $\ge 1$ out) about the relations \emph{must} also have propety $Y$. It means that property $X$ implies $Y$ logically (about relations). In case the answer is “no” (i.e. that property $X$ does not imply $Y$) all we have to find is one relation $R$ that satisfies property $X$ but not property $Y$. If the answer is `yes’ we need to show that for all $R$, if property $X$ holds, so does $Y$. So doing so might need more work.

If an edge is added to the graph of a relation, which properties might be impacted?

If an edge is removed to the graph of a relation, which properties might be impacted?

If an element is removed from the domain of a relation, which properties might be impacted?

If an element is removed from the codomain of a relation, which properties might be impacted?