When is proof by well-ordering preferable to proof by induction?

Question

Exercise 1: Prove that for $n=1,2,3,\ldots$ we have $P(n).$

Proof: $P(1)$ can be seen to be true because blah blah blah. If $n$ is any value for which $P(n)$ is true, then we can argue that etc. etc. and see that $P(n+1)$ must also be true. So by the principle of mathematical induction, the desired result must hold.

Exercise 2: Use the well-ordering of $\mathbb N$ to show that for all $n\in\mathbb N$, $P(n).$

Proof: Suppose the desired result is false. Then for some $n\in\mathbb N$, $P(n)$ must be false. Let $n$ be the smallest such member of $\mathbb N.$ Since $P(n)$ is false, the following argument shows that $P(n-1)$ is also false. But that contradicts the minimality of $n$.

What examples show that one method is preferable in some cases and the other in some other cases? Are there any in which the second method is simpler than the first?

Answer 1

In the case of statements of the form $\forall n \in \mathbb{N}. P(n)$, the two proof techniques are equivalent. But well-ordered induction is a much more general proof technique -- we can use it to prove results of the form $\forall n \in S. P(n)$ for any well-ordered set $S$. In fact, the technique also applies to the class of ordinals (which is not a set but can be well-ordered).

Answer 2

With well-ordered sets $S$ in general, or indeed with the class of all ordinals, one can do a form of mathematical induction in which no basis for induction is needed: \begin{gather} \text{Let } T = \{n\in S : P(n)\}. \\[6pt] \text{Suppose for all } n\in S, \text{ if } \Big( \forall k<n \quad P(k)\Big) \text{ then } P(n). \tag I \\[6pt] \text{Then } T=S. \end{gather} There is no need to prove that $P$ holds in the smallest case, because it is vacuously true that $\forall k < \text{smallest case, }P(k),$ and thus $(I)$ alone is enough to show $P$ holds in the smallest case.

Now How do we show that this induction method is valid? Since we have no assumptions about $S$ and any structure on $S$ except well-ordering, it appears that we must prove it by well ordering. Let $\ell = \min(S\smallsetminus T).$ By minimality of $\ell,$ we have $\forall k<\ell,\,\,P(k).$ By $(I),$ we deduce $P(\ell).$ But that contradicts the fact that $\ell\notin T.$

In other words, a proof by well-ordering is the very means by which one proves that induction is valid on well-ordered sets in general.

(This does not rule out the possibility that there may be some other instances where it is better to use the well-ordering form of argument than the induction form.)

Answer 3

If we're only talking about $ \mathbb{N} $, the second proof you provided is the proof of the induction principle, so the two are equivalent.

As to which style is used, I would say that the first style is preferred, mostly because it hides the technical details of why the induction principle holds, and lets you concentrate on the actual proof.