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
    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.2012-10-22
  • 5
    "Provable" means "derivable from the axioms". You tell me what axioms you are using, I'll tell you whether you can prove Math induction.2012-10-22
  • 2
    In a narrow technical sense, even axioms are provable. It's just that their proofs are very short.2012-10-22
  • 0
    @Harald: Short indeed: +1!2012-10-22
  • 0
    @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! :)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!

  • 1
    The well-ordering principle is the statement that every set can be well-ordered; this is not at all equivalent to the principle of mathematical induction in any of its forms.2012-10-22
  • 0
    @Brian M. Scott: he or she may mean the principle that every nonempty subset of the natural numbers has a least element. This is sometimes called something like "well ordering principle" in elementary texts.2012-10-22
  • 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