Class 12: Review

### Schedule

**Problem Set 5** is due **Friday at 6:29pm**.

See Class 11 Notes for information and preparation advice for Exam 1, which will be in class next Thursday, 5 October.

## 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:

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

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$.

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”.

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

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

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.

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?