Well Ordering

Week 3 : Well ordering

To me, this is a topic that was not really clear for me. I did not understand why this was distinctly recognized from all the other proofs because it basically followed the steps that mathematical induction took. But, after some readings, I realize that proof by well ordering uses the fact that there is a smallest element in a set (I know this was already said in lecture, but I did not understand the significance!). Most of the time, we are trying to prove that there is no value for which a predicate is false, by using the principle of well ordering. 

I found an exam question related to this topic on the December 2009 examination.

Use the principle of well ordering to write a proof that for all n ≥ 1,

This statement will be proved by Contradiction. 

Let P(n) be: For all natural numbers n ≥ 1, the above statement is True

Assume that P(n) is false for at least one positive integer in n. Let S be the set of all possible integers for which P(n) is false. Using these two assumptions we can come to the conclusion that s is non empty and by the Well ordering principle S must contain a smallest element. Suppose that k is the smallest element:

=> We know that k cannot be 1 since for n=1, P(1) is true. 

=> Therefore, k > 1. This also implies that k-1 > 0. Since k -1  ≥ 1, and k is the smallest value for which P(n) is true, we can assume that 

=> Then P(k-1) is true since Since k -1  ≥ 1, k is the smallest value for which P(n) is false and k -1 < k

=> Therefore:

Knowing what P(n-1) is, now, we will compute P(k) :

=> CONTRADICTION! 

=> The last statement contradicts our assumption that k is the smallest value for which P(n) is not true since we proved that if P(n-1) is true, then P(k) is true as well. 

=> So, a smallest value k does not exist in set S and S is empty.

Therefore, there are no values bigger than 1 for which P(n) is not true. 

Since P(1) is true, then the statement that for all natural numbers n ≥ 1