6

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?

Michael Hardy
  • 1
  • Isn't this just a matter of taste? – mathematician Apr 18 '17 at 06:02
  • @mathematician : I doubt it's only a matter of taste. – Michael Hardy Apr 18 '17 at 06:49
  • I think it's mostly a matter of taste, but also sometimes the property in question may be more related to the order of $\mathbb{N}$, in which case some would be more enclined to present it using the well ordering, whereas sometimes it's more of an algebraic property in which case some would be more enclined to use the induction principle. I don't think there's a general rule though. – Maxime Ramzi Apr 18 '17 at 06:56
  • Surely it depends on the nature of P. Induction needs a direct and recognizable inference. Well ordered needs an indirect inability to "start". – fleablood Apr 18 '17 at 07:10
  • Is this question restricted to $\mathbb N$, or do you include arbitrary well-ordered sets and transfinite induction? (I guess not, since you did not tag the question ([tag:transfinite-induction].) I should add that I do not have any interesting examples in mind - I am just trying to help to clarify the scope of the question. – Martin Sleziak Apr 18 '17 at 07:14
  • @mathematician : $\ldots\ldots,$for example, for a particular proposition $P$, one way may be simpler than the other. – Michael Hardy Apr 18 '17 at 07:28
  • 1
    @MartinSleziak : I had in mind $\mathbb N$, but if there is something of interest for other well-ordered sets, maybe it would be appropriate here. – Michael Hardy Apr 18 '17 at 07:28
  • 2
    Answer: when it's shorter. – Gerry Myerson Apr 18 '17 at 07:36
  • @GerryMyerson : So what are some good illustrative examples making it clear that in some cases one way is shorter and in some cases the other way is shorter? – Michael Hardy Apr 18 '17 at 07:38
  • http://www.mathpages.com/home/kmath288.htm – Count Iblis Apr 18 '17 at 07:49
  • 1
    @CountIblis Yes, proof by infinite descent seems like quite reasonable idea. (We could formulate it as proof by induction by trying to prove: "For any $n$ there exists no solutions $\le n$." But proof based on well-ordering principle - which starts with the smallest solution - seems to be more natural in such cases.) – Martin Sleziak Apr 18 '17 at 08:07
  • 1
    I'm sure, Michael, that you could find all the examples you could want by just taking sample theorems and writing up two proofs and seeing which is shorter. – Gerry Myerson Apr 18 '17 at 09:34
  • The proposition that every natural number is divisible by some prime is something that I've never thought about much, but I find that I've always thought about it by thinking of the contradictory nature of a minimal counterexample. And "minimal" would have to mean when ordered by divisibility. – Michael Hardy May 05 '17 at 03:26

3 Answers3

2

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).

Hans Hüttel
  • 4,271
  • I don't see that this addresses the question, which is: "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?" – Michael Hardy Apr 18 '17 at 17:52
  • 1
    My answer is really just saying that it does not matter, really. – Hans Hüttel Apr 18 '17 at 19:02
  • But I think it does matter in cases where one method results in a more complicated proof than the other. A proof by induction can be rearranged into a proof by contradiction that uses well-ordering, but in some cases this appears to make the proof look more complicated than it really is, i.e. more complicated than the proof by induction. I'm wondering whether in some cases it would be the other way around. – Michael Hardy Apr 18 '17 at 19:57
  • A proof by well-ordering need not be a proof by contradiction. If $(S,<)$ is a well-ordered structure, we can prove $\forall x \in S. P(x)$ if we can prove that whenever $P(y)$ holds for all $y < x$, then also $P(x)$. – Hans Hüttel Apr 18 '17 at 19:59
  • That appears to be a form of mathematical induction. – Michael Hardy Apr 18 '17 at 20:11
  • 1
    It is a generalisation of induction over the natural numbers. – Hans Hüttel Apr 18 '17 at 20:44
  • So the same question would apply to ordinals as to $\mathbb N. \qquad$ – Michael Hardy Apr 19 '17 at 02:07
1

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.)

Michael Hardy
  • 1
0

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.

Josselin Poiret
  • 607
  • This doesn't really address the question, which says "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?" – Michael Hardy Apr 18 '17 at 17:52
  • What I am saying is that I don't think the second option is preferable. In fact, I've never seen it anywhere, outside of proofs of the induction principle. – Josselin Poiret Apr 18 '17 at 17:54