Well-ordering principle
Every non-empty subset of has a least element: if and , then there exists a least element .
Axiom 3.6 (Well-Ordering Principle)
Any non-empty subset of has a least element.
i.e. if holds for with , then there exists a least element such that holds.
Least-element argument
Any natural number can be written as a product of primes. Suppose not, and let . Assuming , the well-ordering principle gives a least element . Since is not prime, for some with . By minimality of , both and can be written as products of primes, and hence so can — a contradiction.
Related
Stated in
- Axiom 3.6 (Well-Ordering Principle)§3.2 Induction and Ordering