Well-Ordering Principle
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 p1 be the least of these divisors. Notice that p1 must be prime, otherwise there is an integer k with 1 < k < p1, and k divides p1, so k divides n, which contradicts the choice of p1! So n = p1n1 where p1 is prime and n > n1.This factorization is also unique (up to the order of the factors), see the Fundamental Theorem of Arithmetic.Now we repeat this argument with n1 to find out that it is either prime (and we are done with n = p1n1), or n1 = p2n2, where p2 is prime and n1 > n2.
Now again repeat the argument with n2, ... This process can not continue indefinitely because by the Well-Ordering Principle, the set of positive integers
n > n1 > n2 > n3 . . .has a least element, say pk. Then n = p1p2. ... .pk. ∎