The Prime Glossary: Well-Ordering Principle

Well-Ordering Principle
(another Prime Pages' Glossary entries)

Glossary:

Prime Pages:

Top 5000:

When we seek to develop the integers axiomatically (from a short list of basic assumptions), we usually include the Well-Ordering Principle as one of these assumptions:

Well-Ordering Principle
Every nonempty set S of positive integers contains a least element; that is, there is some element a of S such that a < b for all elements b of S.

Notice that the positive real numbers do not have this property. For example, there is no smallest positive real number r, because r/2 is a smaller positive real number! The negative integers also lack this property because if r is a negative integer, then r-1 is a smaller negative integer.

This simple principle of positive integers has many consequences. Let us demonstrate one by proving the following:

Theorem: Every integer n greater than one can be written as a product of primes.

Proof: Either n is prime (in which case we are done because it is the product of the one prime n), or it has a positive divisor other than one and itself. Let p₁ be the least of these divisors. Notice that p₁ must be prime, otherwise there is an integer k with 1 < k < p₁, and k divides p₁, so k divides n, which contradicts the choice of p₁! So n = p₁n₁ where p₁ is prime and n > n₁.
Now we repeat this argument with n₁ to find out that it is either prime (and we are done with n = p₁n₁), or n₁ = p₂n₂, where p₂ is prime and n₁ > n₂.
Now again repeat the argument with n₂, ... This process can not continue indefinitely because by the Well-Ordering Principle, the set of positive integers
n > n₁ > n₂ > n₃ . . .
has a least element, say p_k. Then n = p₁p₂^. ... ^.p_k.

This factorization is also unique (up to the order of the factors), see the Fundamental Theorem of Arithmetic.