The principle of mathematical induction can be proved if the following axioms are assumed:
(A1) (The Well-Ordering Principle) Every non-empty subset of the natural numbers ℕ = {0, 1, 2, ...} has a least element.
(A2) Let m ∈ ℕ. If m > 0, then ∃n ∈ ℕ: m = n + 1.
Proof: Suppose
(1) P(0)
and
(2) For all n ∈ ℕ: P(n) ⇒ P(n + 1)
We wish to prove:
(3) P is true for all integer values of m.
Let S be the set of numbers for which P is false.
Using (1), we see that 0 ∉ S and is therefore not the minimal element of S.
Using (A2), if m > 0, then m = n + 1. If n ∈ S, then m, being bigger, cannot be the minimal element of S. But if n ∉ S, we have P(n) and, using (2), P(n + 1). It follows that m ∉ S and m cannot be the minimal element of S.
Thus, S has no minimal element, and by (A1) must be empty. P is therefore true for all integer values of m.
The axiom (A1) can be proved by the principle of mathematical induction. Indeed, given (A2), the two are equivalent.
Let S be a set of natural numbers. We want to prove that if S has no smallest element, then S is empty.
Proof: Consider a set S with no smallest element and let P(n) be the statement that n ∉ S.
(1) Since S has no smallest element, 0 ∉ S and so P(0) is true.
(2) Suppose that P(n) is true for some n. That is, n ∉ S. Since S has no smallest element, n + 1 ∉ S either and so we have P(n + 1).
By induction, we know that P(n) is true for all n, and therefore S = ∅.
Sources: wikipedia.org and Paul R Halmos, Naive Set Theory