# The proof of theorem of Mathematical Induction.

In the book What is Mathematics? by Richard Courant it is given that we can Mathematical Induction using the Principle of Smallest Integer. There the explanation goes like this :-

Let us consider any sequence of statements A1, A2, A3,.... such that
a) For any positive integer r the truth of Ar+1 will follow from that of Ar.
b) A1 is known to be true.
If one of A's is false, the set C of all positive integers n for which An is false would be non-empty. By the principle of smallest integer, C would contain a smallest integer, p, which must be >1 because of b). Hence Ap would be false, but Ap-1 true. This contradicts a).

I want ask that in the proof above what is the significance of the Principle of Smallest Integer, we could prove it without it. We should have said that if any Ap is false then according to a) Ap-1 can't be true because the truth of Ap-1 implies the truth of Ap and if we go on like this i.e. falsity of Ap-1 implies the falsity of Ap-2 , we would reach where it is proved that A1 is false but this contradicts b) hence we both the conditions a) and b) implies that all the statements A1, A2... are true .

My reasoning could be wrong somewhere as I'm unable to grasp the significance of Smallest Integer Principle and that's where I need the real help. I also want to the flaw (if there is any) in my proof.

• Your reasoning is not correct; the only point is that "and if we go on like this" is exactly where induction is needed: to replace "and so on", or the usage of "dots" in formal proofs. Commented Jul 13, 2019 at 15:37
• @MauroAllegranza May you please give me a detailed answer. Commented Jul 13, 2019 at 15:50
• "we would reach where it is proved that $A_1$ is false..." Yes, but that is a consequence of the fact that $\mathbb N$ has a smallest integer $1$. In e.g. $\mathbb Z$ this would not work. Commented Jul 13, 2019 at 15:56
• See also the similar post. Commented Jul 13, 2019 at 16:04
• Sorry for the misprint in my comemnt above : the intended meaning was "Your reasoning is not incorrect..." Commented Jul 13, 2019 at 16:05

Long comment

The Principle of Mathematical Induction is often an axiom because it is quite obvious :

if $$P$$ holds of $$1$$ and, every time that $$P$$ holds of $$n$$ it holds also of $$n+1$$, then "obviously" we can start from $$1$$ and go on forever without finding any $$k$$ such that $$P$$ does not hold of it.

It is obvious but ... the above is not a proof : the "goes on forever" is not what we "like" in mathematical proofs.

The same for the corresponding argument :

if $$P$$ holds of $$1$$ and, every time that $$P$$ holds of $$n$$ it holds also of $$n+1$$, then if we assume that $$P$$ does not hold for a certain $$k$$, then going back to $$1$$ we "obviously" will find an $$n$$ such that $$P$$ holds of it and does not hold of $$n+1$$, contrary to assumption.

Conclusion : there are many "Principles" that we can use interchangeably, in the sense that, assuming one of them we can prove the others, but we have to assume some of them in order to rigorously license the "form of argument" typical of natural numbers that lies behind the "goes on forver".

This "goes on forver" is exactly what "identifies" natural numbers : start from a "first" one (zero or one) and then add one : we get a new number. Then add one... We can go on forever and we'll always find a new number.

This intuitive concept is rigorously charcterized by the so-called Peano axioms :

The first axiom states that there is a starting point : call it $$0$$.

There is a "successor" function that for every number allow us to find the "next one" : call it "add one" function.

And finally there is the Induction axiom.

I'd like to take a chance on explaining this.

As far as I understand, the Principle of Smallest Integer is some partial case of well-ordering definition --- any subset of a well-ordered set has the smallest element. To get some intuitive feeling, why do we need the aforementioned well-ordering let's take a look at a non-well-ordered set --- real numbers with usual "<" sign (there are certain methods to define a well-order on real numbers, but now we need the ordinary comparison).

Now I use non-negative real numbers to index A-s. At the first glance it seems, we can define induction as: all $$A$$-s are true if

• $$A_0$$ is true;
• if $$A_x$$ is true for any $$x < y$$, then $$A_y$$ is true.

The induction I have just defined looks as transfinite induction, except that transfinite induction needs special comparison "$$\prec$$" that makes reals well-ordered, otherwise it will not work. Let's check out what exactly goes wrong by trying to prove this induction principle.

Proof by contradiction. Say that there is a set of indices $$I$$ such that for any $$i \in I$$ $$A_i$$ is false. If $$I$$ has the least element, call it $$j$$, we can state that:

• either $$j = 0$$, thus $$A_0$$ is false, thus contradiction;
• or for any $$x < j$$, $$A_x$$ should be true, thus $$A_j$$ should be true, but it is false.

Now consider, that I used the fact that $$I$$ should contain the least element. But what if it doesn't? Our proof just breaks! Let's look at the example.

Consider $$I$$ to be the following set $$I = \{2; 1 + \frac{1}{2}; 1 + \frac{1}{3}; \dots\}$$. It contains an infinite number of elements, but does not have the least one (if we compare with ordinary "<" sign). Thus if I try reasoning as before, I will not be able to find any such $$j$$ that $$A_j$$ is false, but all $$A_{x are true --- there always will be some $$j' < j$$ such that $$A_{j'}$$ is false.

In conclusion

• we can define and prove induction for any well-ordered set of indices;
• we need well-ordering for the proof --- the set of all such indices $$i$$ that $$A_i$$ is false should contain the least element $$j$$ so that we will be able to state $$A_{x \prec j}$$ is true.