Proof for Strong Induction Principle

$\begingroup$

I am currently studying analysis and I came across the following exercise.

---

Proposotion 2.2.14 Let $m_0$ be a natural number and let $P(m)$ be a property pertaining to an arbitrary natural number $m$. Suppose that for each $m\geq m_0$, we have the following implication: if $P(m')$ is true for all natural numbers $m_0\leq m'< m$, then $P(m)$ is also true. (In particular, this means that $P(m_0)$ is true, since in this case the hypothesis is vacuous.) Then we can conclude that $P(m)$ is true for all natural numbers $m\geq m_0$.

Prove Proposition 2.2.14. (Hint: define $Q(n)$ to be the property that $P(m)$ is true for all $m_0\leq m < n$; note that $Q(n)$ is vacuously true when $n<m_0$.)

---

I have difficulty understanding how I should use the hint and in general what the framework of this proof would look like (probably an inductive proof; but on what variable do we induct, what will be the induction hypothesis and how would I go about proving the inductive step etc.?). Could anyone please provide me with some hints to help me get started?

$\endgroup$ 4

1 Answer

$\begingroup$

Let $B$ be the subset of $N=\{m_0,m_0+1,...\}$ such that $P(m)\iff m\in B$. This $B$ is not empty since for all $m_0\le m'<m_0$ the property $P$ is satisfied, thus also $P(m_0)$. We want to show that $B=N$. So assume that $A:=N\setminus B\ne\emptyset$. Then there is an $m\in A$ such that each $m_0\le n<m$ is in $B$, in other words $m$ is the minimum of $A$. But if $n<m$ implies $P(n)$, then by hypothesis $P(m)$ and so $m\in B$, a contradiction. Hence $B=N$.

Remark: This works for all sets $N$ where each non-empty subset has a minimal element with respect to a relation $R$. These sets are called well-founded.

If you want to use the hint, show that $Q(n)$ implies $Q(n+1)$ and that $Q(m_0)$: Since $Q(m')$ is true for all $m_0\le m'< m_0$, it is also true for $m_0$. Assume $n$ is a natural number $\ge m_0$ such that $Q(n)$. This means that $P(m)\ \forall m_o\le m<n$. By hypothesis this implies $P(n)$, thus $P(m)\ \forall m_0\le m<n+1$, so again by definition of $Q$ we have $Q(n+1)$. Now apply the induction principle.

So we can proof the strong induction principle via the induction principle. However, the normal induction principle itself requires a proof, it that is the proof I wrote in the first paragraph. As mentioned it works for all well-founded sets ($\mathbb N$ is such a set.)

$\endgroup$ 5

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy