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.

This is not for a homework assignment, but instead for my own study and understanding... and because it may be on a future test.

I was shown in my elementary number theory class that you can prove the Well Ordering Principle by using strong mathematical induction. I was a bit confused by this because I thought that induction uses the well ordering principle as its whole basis; how could you use one thing to prove the thing it is based upon? But the prof says that regular induction, strong induction, and the well ordering principle can be shown to be equivalent by using one to prove another.

All I have right now is proof of the well-ordering principle, as follows:

Assume there exists a non-empty set $A\subseteq\mathbb{N}$ that does not contain a least element. Let $S=\mathbb{N}\setminus A$.

$1\in S$, because if $1$ were in $A$, then $1$ would be the least element in $A$. Assume $1,2,3,\dots,n\in S$. Since they do not belong to $A$. Then $n+1\in S$, because otherwise, $n+1\in A$ and would be the least element in $A$ (since $1,2,3,\dots,n\in S$). Therefore, $S=N$ by strong mathematical induction, and $A=\emptyset$ which is a contradiction.

How could proofs in the other direction work, assuming my prof was correct in what he said? Every search I've done on Google yields basic documents about how induction works, instead of showing proof that these are equal.

share|improve this question
    
To be honest, if you are studying mathematics, it will be in a ton of future tests. So good for you. –  Patrick Da Silva Sep 19 '13 at 19:07
    
Note that well-ordering only implies regular induction because we are working with $\mathbb{N}$. In general, one can do induction on any well-ordered set, but one needs to do strong induction (or regular induction with possibly an infinite number of base cases). –  Tobias Kildetoft Sep 19 '13 at 19:13

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.