3
$\begingroup$

I thought the following was the case: In a proof by induction, one must use the inductive hypothesis at some point. Otherwise, the proof is either a) wrong or b) correct yet needn't be written in the form of an induction.

Here's a solution to an exercise from Tao's Analysis I book in which an inductive proof is performed that does not utilize the inductive hypothesis: https://taoanalysis.wordpress.com/2020/03/16/exercise-2-2-2/

Indeed, there is a second proposition in Tao's book that uses inductive proof without touching the inductive hypothesis. In this case, he provides the proof himself. (If you have the book, it's Proposition 2.2.8.).

I myself am not capable of pinpointing what's going on here. Questions:

  1. Can this proof be performed without using induction? If so, how? I'm not putting my money on this being possible, as Tao explicitly recommends using induction even in the newest edition of the book.
  2. If the proof must be written in this inductive form, what is going on here? What lesson can we extract concerning the nature of mathematical induction? Why do we need induction even though we don't need the inductive hypothesis?
  3. Are there other inductive proofs that ignore the inductive hypothesis? What "type of proof" constitutes this category?

If I'm terribly confused, be so kind and help me out of my confusion. (: Thanks!

$\endgroup$
3
  • $\begingroup$ I, too, would have though that the induction hypothesis was necessary for the same reasons you state, but this proof is just using the fact that every natural number is 0 or $x+1$ for some natural number $x$, which I guess is also contained in induction. $\endgroup$
    – TomKern
    Dec 27, 2022 at 1:30
  • $\begingroup$ If a proof does not at some point use the induction hypothesis (whether in the weak or strong form) , it is not an induction proof. There are other proof techniques , so first we have to determine whether the given proof is inductive at all. Sometimes , the use of the induction hypothesis is hidden (or omitted because it is obvious how it would be applied). That does however not mean that it was not (perhaps implicitely) used. $\endgroup$
    – Peter
    Dec 27, 2022 at 11:18
  • $\begingroup$ @Peter Care to apply this line of thought to the example I linked to? As is, I'm gravitating towards believing that what you're saying isn't exactly correct (see the two answers to my original post for context). $\endgroup$ Dec 27, 2022 at 14:55

2 Answers 2

4
$\begingroup$

The implicit assumption here is that if

  1. $P(0)$ is true, and
  2. $P(a)$ is true implies that $P(a + 1)$ is true for any natural $a$,

then $P$ is true over all naturals (including $0$). Notice that replacing \begin{align*} P(a) \ \text{is true implies that} \ P(a + 1) \end{align*} with \begin{align*} P(a) \ \text{and} \ P(a + 1) \ \text{are true} \end{align*} results in a stronger assumption. So, if we have a proof that works with the stronger assumption, it still implies that $P$ is true over all naturals.

Usually, any proof using this stronger assumption would mean that the induction is redundant. But any proof of this problem that avoids using this inductive process results in having to use the fact that every natural has a predecessor, which is part of what we're trying to prove!

So, we can only use the fact that successors are defined. Then the proof looks like a traditional proof by induction because we're using the assumption mentioned at the beginning along with successor operators, both of which we happen to do in proofs by induction in general.

Put another way, this is a linguistic issue. The notion usually associated with the word "induction" is building up truth successively to prove that a statement is true over positive integers. This is the point that the hint is getting at, rather than strictly requiring that the induction hypothesis be used to show that $P(a) \implies P(a + 1)$ for any positive integer $a$.

$\endgroup$
3
$\begingroup$

Writing the principle of induction in symbolic form helped me understand what's going on here. $$ \left(P(0)\wedge\forall a\,(P(a)\Rightarrow P(a^{++})\right)\Rightarrow\forall a\,(P(a)) $$ In the proof you cite, it's possible to prove $\ \forall a\, P(a^{++})\ $ without assuming $\ P(a)\ $ for any $\ a\ $ or using the principle of induction in any other way. A fortiori, therefore, we get a proof of $\ \forall a\,(P(a)\Rightarrow P(a^{++}))\ $ for free. However it's still not possible to draw the conclusion $\ \forall a\,(P(a))\ $ without the base case $\ P(0)\ $. To answer your first two questions, then:

  1. I don't think it's possible to prove the result without somewhere relying on the principle of induction.
  2. Induction is needed because the proof fails without the base case.
$\endgroup$
5
  • 1
    $\begingroup$ What is $a^{++}$? In programming it is often the successor, but this is not SO, and in set theory this will usually denote the double successor. $\endgroup$
    – Asaf Karagila
    Dec 27, 2022 at 9:15
  • $\begingroup$ It's the notation used for successor in the exercise solution at the link given in the question. I had difficulty understanding the solution myself until I realised that this must have been the case. I confirmed this suspicion by consulting this online copy of Tao's book. The notation is introduced on p.18. $\endgroup$ Dec 27, 2022 at 10:47
  • $\begingroup$ Ugh, this is terrible. Thanks for the source, though. $\endgroup$
    – Asaf Karagila
    Dec 27, 2022 at 10:57
  • $\begingroup$ Thanks, this response helped me see through things best! (The other answer is great, too, though.) So, the claim that a proof is only inductive if it uses the induction hypothesis to prove the induction step is, though a by and large correct heuristic, strictly speaking wrong. Instead, it suffices that the axiom of induction is put to work, as it is here. Is this a fair conclusion? $\endgroup$ Dec 27, 2022 at 13:50
  • $\begingroup$ Yes, I agree with your conclusion. $\endgroup$ Dec 29, 2022 at 7:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .