0
$\begingroup$

Since the method of mathematical induction follows some sort of 'algorithm', would the method itself be provable?

namely,

give that the method of mathematical induction is as follows:

if S is a subset of N, these holds:

(i) S contains 1

(ii) whenever S contains a natural number n, it contains n + 1

  • 0
    @HaraldHanche-Olsen: In a $m$ore tech$n$ical sense (to the point o$f$ silliness), it's si$m$ply that the *minimal length* proo$f$s of axioms are very short. It's possible to give an arbitrary long proof of an axiom! :)2012-10-22

2 Answers 2

5

It’s an immediate consequence of the fact that the positive integers are well-ordered by the usual order $<$. Let $B=\Bbb N\setminus S$; if $B\ne\varnothing$, let $b=\min B$, which exists because $<$ well-orders $\Bbb Z^+$. We proved that $1\in S$, so $1\notin B$, and therefore $b\ne 1$. Thus, $b=n+1$ for some $n\in\Bbb Z^+$. Clearly $n, so $n\notin B$; but $n\in\Bbb Z^+$, so $n\in S$, and therefore by hypothesis $b=n+1\in S$, contradicting the choice of $b$. Thus, $B=\varnothing$, and $S=\Bbb Z^+$.

In the standard set-theoretic framework (ZF(C) the fact that $\Bbb Z^+$ is well-ordered by $<$ is largely a matter of definition: it’s defined to be a subset (or order-isomorphic to a subset) of $\omega$, the first infinite ordinal, and all ordinals are by construction well-ordered by $<$.

In the framework of the Peano axioms matters are a bit different: in that setting it’s actually an axiom.

But it will be true in any reasonable axiomatic setting for elementary number theory, because any such setting must match our intuitive notion of $\Bbb Z^+$, which is of a well-ordered set in which every element can be reached from $1$ in a finite number of steps.

0

You have to use the Well-ordering principle to prove Math Induction! In fact, the Well-ordering principle is equivalent to the principle of mathematical induction!

  • 0
    @Carl: I did think of that, which is why I specified what I meant by it instead of just disagreeing. With luck LJym89 will clarify.2012-10-22