The well-ordering principle states:

The well-ordering principle: Any nonempty set of nonnegative integers has a smallest element.

DUH, you don’t say! - seems obvious, doesn’t it? This principle is, nevertheless, a very important and fundamental tool for proving other basic principles of number theory.

Consider, for instance, the Division Algorithm:

The Division Algorithm: If m and n are integers with n > 0, then there exist integers q and r, with 0 <= r < n, such that .

Again, this is so basic that one may doubt whether it should even be proved. But the well-ordering principle allows us, in fact, to prove the division algorithm in a rigorous manner:

Let . It is obvious that W contains nonnegative integers. Let . By the well-ordering principle, V has a smallest element, which we’ll call r. , so for some q and r >= 0 (by the definition of sets W and V, correspondingly).

Now, what’s left to prove is that r < n. Let’s assume the opposite, namely that . Rearranging: . By the definition of V, (since it has the form for some integer t and is nonnegative). But recall that we called r the smallest element of V, and , so we have a contradiction.

Therefore, we see that r < n. This completes the proof. Q.E.D.

Related posts:

1. The GCD and linear combinations
2. Equivalence classes and group partitions
3. A group-theoretic proof of Euler’s theorem

This entry was posted on Thursday, July 9th, 2009 at 09:25 and is filed under Math. You can follow any responses to this entry through the RSS 2.0 feed. You can skip to the end and leave a response. Pinging is currently not allowed.