Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
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. –  Gerry Myerson Oct 22 '12 at 11:49
2  
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
add comment

2 Answers

up vote 5 down vote accepted

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.

share|improve this answer
add comment

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!

share|improve this answer
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. –  Brian M. Scott Oct 22 '12 at 12:03
    
@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. –  Carl Mummert Oct 22 '12 at 12:08
    
@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. –  Brian M. Scott Oct 22 '12 at 12:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.