1
$\begingroup$

In T.Tao's Analysis 1 book I've read the following:

Axiom 2.5 (Principle of mathematical induction):

Let $P(n)$ be any property pertaining to a natural number $n$. Suppose that $P(0)$ is true, and suppose that whenever $P(n)$ is true, $P(n+1)$ is also true. Then $P(n)$ is true for every natural number $n$.

Proposition 2.2.14 (Strong principle of induction):

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. Then $P(m)$ is true for all numbers $m\geq m_0$.


Since I've seen in many proofs the principle of induction (not the strong version) used with the base case $n=1$ I want to prove the following:

"Let $P(m)$ be a property pertaining to a natural number $m$ such that $P(1)$ is true and whenever $P(m)$ is true, $P(m+1)$ is also true. Then $P(m)$ is true $\forall m\in\mathbb{N}, m\geq 1$."

Here's what I've done:

Let $Q(n)$ be the property that $P(m)$ is true for $m=n+1$; then $Q(0)$ is true by hypothesis and if we suppose that $Q(n')$ is true for all natural numbers $0\leq n'<n$ then this means in particular that $Q(n-1)$ is true thus $P(n)$ is true so by hypothesis we have also that $P(n+1)$ is true thus $Q(n)$ is true and so by the strong principle of induction $Q(n)$ is true $\forall n\in\mathbb{N}$ and (being $\{m\in\mathbb{N}:m=n+1, n\in\mathbb{N}\}=\{m\in\mathbb{N}:m\geq 1\}$) we can conclude that $P(m)$ is true $\forall m\in\mathbb{N}, m\geq 1$, as desired.

a) Is my proof correct?

b) Is there any way to make it simpler/better?

c) Is there a way to prove the statement using only the axiom of mathematical induction?

Best regards,

lorenzo

$\endgroup$
2
$\begingroup$

As you say, let $Q(n) = P(n+1)$. Then $P(1) = Q(0)$, and $$P(n)\Rightarrow P(n+1), n\ge 1 \equiv Q(n-1)\Rightarrow Q(n), n\ge 1 \equiv Q(n)\Rightarrow Q(n+1), n\ge 0.$$ So together, $P(0)$ and $P(n)\Rightarrow P(n+1)$, $n\ge 1$ are equivalent to $Q(0)$ and $Q(n)\Rightarrow Q(n+1)$, $n\ge 0$. Thus $Q(n)$ holds for all $n\ge 0$; i.e., $P(n+1)$ holds for all $n\ge 0$; i.e., $P(n)$ holds for all $n\ge 1$.

But really, the "names" of the numbers $0$ and $1$ don't matter: just squint so you can't see the labels on the number line. It's the fact that the set of integers you're concerned with has a lower bound that matters. You can equally well prove induction where the base case is, say $P(17)$, or $P(-12)$.

You might want to look at the definition of a well-ordered set and the discussion of mathematical induction on Wikipedia.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.