# is it possible to prove the method of mathematical induction itself?

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

-
this formulation is wrong {} is a subset of N but doesn't contain 1. I guess you mean to say IF (i) and (ii) hold then S = N. –  sperners lemma Oct 22 '12 at 11:46
"Provable" means "derivable from the axioms". You tell me what axioms you are using, I'll tell you whether you can prove Math induction. –  Gerry Myerson Oct 22 '12 at 11:49
In a narrow technical sense, even axioms are provable. It's just that their proofs are very short. –  Harald Hanche-Olsen Oct 22 '12 at 11:52
@Harald: Short indeed: +1! –  Brian M. Scott Oct 22 '12 at 12:10
@HaraldHanche-Olsen: In a more technical sense (to the point of silliness), it's simply that the minimal length proofs of axioms are very short. It's possible to give an arbitrary long proof of an axiom! :) –  Michael Joyce Oct 22 '12 at 12:40

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<b$, 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.

-