Proofs of a mathematical statement or theorem can have different levels of rigor and I have a question about this.

In the method of mathematical induction, there are statements numbered with 1, 2, 3 etc and we need to prove them. The method says that to prove that these infinitely many statements are correct, two conditions are sufficient: 1) show that statement #1 is correct and 2) show that every statement implies its successor. Now, this means that #1 implies #2, and #2 implies #3, etc etc., and therefore, we proved that the two conditions imply that the infinitely many statements are true.

Now I am wondering: what would a mathematician say about the rigor of this proof? is anything missing in the logic of the proof? could he/she demand more rigor? I'm arising this question because a friend of mine has argued that a more rigorous proof needs to invoke the well ordering principle and related things. So could this stuff be considered more rigorous, or perhaps just completely equivalent?

  • $\begingroup$ There isn't a way to make it more rigorous, because induction or an equivalent must be taken as an axiom. For example, in set theory, we have the axiom of infinity, which says essentially "an inductive set exists", which we usually understand to mean "$\mathbb{N}$ exists." The reason for this is that proofs by definition must have finite length, whereas the only possible "proof" of the principle of induction would be infinite. $\endgroup$ – Ian Feb 4 '15 at 1:26
  • 2
    $\begingroup$ Let $\,S\,$ be the set of naturals where the statement is true. Then set-theoretically it amounts to $$S=\Bbb N\,\iff\, 1\in S\,\ {\rm and}\,\ n\in S\,\Rightarrow\, n\!+\!1\in S$$ That is not a proof of mathematical induction but, rather, an equivalent reformulation of it. $\endgroup$ – Bill Dubuque Feb 4 '15 at 1:45

Well I can't say for sure whether there is a non-circular way to justify induction (Ian essentially claims any justification would be infinite), but certainly your 'proof' is not valid justification. All you have 'established', being as generous as I possibly can, is that given your two conditions we can prove that #1, #2 and #3 are true. I do not accept "etc", so you will have to define it or explain what it means and why I should accept your usage of it.


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.