Proving Mathematical Induction is Correct

Date: 08/31/2001 at 06:46:52
From: Soh Irene
Subject: How to prove that mathematical induction is correct?

Hi,

I have being trying to prove that mathematical induction is correct. 
I know that I can use proof by contradiction, but I do not know how to 
start.

Irene

Date: 08/31/2001 at 08:13:36
From: Doctor Jerry
Subject: Re: How to prove that mathematical induction is correct?

Hi Soh Irene,

If I understand what  you have said, then I think that the  best reply 
I can make to you is that in many approaches to mathematics in which 
mathematical induction is used as a proof technique, there is an axiom 
guaranteeing this technique. Sometimes the axiom is stated this way:

The set N = {1,2,3,...} of natural numbers has the following property: 
If M is a subset of N for which 1 is in M and n+1 is in M whenever 
m is in M, then M = N.

Proof by mathematical induction is based on this axiom.

- Doctor Jerry, The Math Forum
  http://mathforum.org/dr.math/   

Date: 08/31/2001 at 08:41:41
From: Doctor Jordi
Subject: Re: How to prove that mathematical induction is correct?

Hello. Thanks for writing.

You may have a hard time proving mathematical induction, depending on 
the axioms you are using. What principles are you relying on?  If you 
are using the fundamental axioms of Zermelo-Fraenkel set theory (the 
"standard" axioms of set theory) you will not be able to prove 
mathematical induction. You need an extra axiom: the infamous Axiom of 
Choice, or one of its equivalent forms. 

The four statements I give below are all equivalent, meaning that if 
you assume one of them to be true, the others follow as consequences, 
but none of them can be proven from the other fundamental axioms in 
Zermelo-Fraenkel set theory alone.

  Axiom of Choice
  ---------------
  Given a collection of nonempty sets A, it is possible to form a new 
  set that includes one element from every set in A.

  Zorn's Lemma
  ------------
  If in a set A it is possible to give a partial ordering of this set  
  (a partial ordering is analogous to the relationship "less than or 
  equal" in the real numbers) and if every chain of partially ordered 
  elements in A has an upper bound (an upper bound is an element p 
  such that all elements in the chain are "less than or equal" to p) 
  then A has a maximal element (means that there is an element m in A 
  such that all other elements in A are "less than or equal" to m).

  Well-Ordering Principle
  -----------------------
  Every nonempty subset of the natural numbers (positive integers) 
  contains a least member.

  Mathematical Induction
  ----------------------
  If A is a subset of natural numbers such that 
     i) 1 is in A
    ii) if a natural number k is in A then k + 1 must also be in A
  Then A is the set of natural numbers.

There are other equivalent statements that are often used (such as 
Zermelo's postulate) and the above four I gave are sometimes written 
in different forms, of varying degrees of abstraction and generality.  
I gave the last two explicitly as statements about the natural 
numbers, because it will be easier to formulate the appropriate 
proofs.

As I said before, assuming any one of the four statements above one 
can prove the other three, but proving mathematical induction from, 
say, the Axiom of Choice directly is not all that straightforward.  
Instead, it is much simpler to prove mathematical induction from the 
well-ordering principle. As an example, let's prove the converse, by 
indirect method.

  THEOREM: Mathematical induction implies the well-ordering principle.

  Proof: Let A be a nonempty subset of the natural numbers, as given 
  by the hypothesis of the well-ordering principle. Suppose A has no 
  least member.  Let B be the set of all natural numbers that are not 
  in A. Clearly 1 is in B (for otherwise 1 would be in A and hence A 
  would have a least member). Moreover, if 1, 2, 3, ..., k are not in 
  A then k+1 is not in A, for otherwise k+1 would be the least member 
  in A. In other words, this shows that if k is in B, then k+1 is in 
  B. By the principle of mathematical induction, it follows that B is 
  the set of natural numbers. It thus follows that for any natural 
  number n, n is not in A. Hence A is empty. But this contradicts the 
  fact that A is nonempty, therefore A must have a least member.

Examine the proof carefully and try to get ideas from it for proving 
that mathematical induction follows from the well-ordering principle.  
The basic method is the same: assume a certain nonempty set exists, 
then derive the contradiction that this set is actually empty.  

HINTS: What nonempty set would exist if mathematical induction were 
false? How can one derive a contradiction about this set using the 
well-ordering principle? In other words, what would the well-ordering 
principle say of this set?

I hope this is enough to get you started. If you still need help, or 
if you have other questions, feel free to follow up on this e-mail.

- Doctor Jordi, The Math Forum
  http://mathforum.org/dr.math/