Well-ordering principle

In mathematics, the well-ordering principle, also called the well-ordering property[1] or least natural number principle,[2][3] states that every non-empty subset of the nonnegative integers[4] contains a least element,[5] also called a smallest element.[6] In other words, if is a nonempty subset of the nonnegative integers, then there exists an element of which is less than, or equal to, any other element of .[1] Formally, .[7] Most sources state this as an axiom or theorem about the natural numbers, but the phrase "natural number" was avoided here due to ambiguity over the inclusion of zero. The statement is true about the set of natural numbers regardless whether it is defined as (nonnegative integers) or as (positive integers), since one of Peano's axioms for , the induction axiom (or principle of mathematical induction), is logically equivalent to the well-ordering principle.[8] Since and the subset relation is transitive, the statement about is implied by the statement about .

Experience with numbers favors this principle. For instance, the set T = {5, 8, 3, 11} has 3 as its least element, and 2 is the least element in the set of even positive numbers. It is a deceptively obvious principle because in many cases it is not clear what the least number actually is.

Lars Tuset, Abstract Algebra via Numbers[4]

The standard order on is well-ordered by the well-ordering principle, since it begins with a least element, regardless whether it is 1 or 0. By contrast, the standard order on (or on ) is not well-ordered by this principle, since there is no smallest negative number.[9] According to Deaconu and Pfaff,[10] the phrase "well-ordering principle" is used by some (unnamed) authors as a name for Zermelo's "well-ordering theorem" in set theory, according to which every set can be well-ordered. This theorem, which is not the subject of this article, implies that "in principle there is some other order on which is well-ordered, though there does not appear to be a concrete description of such an order."[9]

Equivalent to induction

[edit]

The well-ordering principle is logically equivalent to the principle of mathematical induction, according to which .[11][12][13] In other words, if one takes the principle of mathematical induction as an axiom, one can prove the well-ordering principle as a theorem (as done in [14][15][16]), and conversely, if one takes the well-ordering principle as an axiom, one can prove the principle of mathematical induction as a theorem (as done in [17][18][19]).[11][12] The former is more common due to tradition, since the principle of mathematical induction was one of Peano's axioms for the natural numbers, and Peano was an influential mathematician.

The principle of mathematical induction and the well-ordering principle are each also equivalent to the principle of strong induction (also called the principle of complete induction), according to which .[20] Accordingly, one can also use the principle of strong induction as an axiom to prove the well-ordering principle as a theorem (as done in [21][22][23][24]), or take the well-ordering principle as an axiom to prove the principle of strong induction as a theorem (as in [25][a]).

This also means that, in axiomatic set theory, the definition of the natural numbers as the smallest inductive set, , is equivalent to the statement that the well-ordering principle is true for it.[8]

Implied by completeness of the reals

[edit]

If one knows, as an axiom or theorem, that the real numbers are complete, then one can use this to prove the well-ordering principle for nonnegative integers.[28] This is because the completeness property implies that every bounded-from-below subset of has an infimum, which means that, since is a bounded-from-below subset of (and the subset relation is transitive), then also every set has an infimum , which implies that there exists an integer such that lies in the half-open interval , which implies that and .[29]

Nonalgebraic

[edit]

The well-ordering principle, like the least upper bound axiom for real numbers,[30][31] is non-algebraic, i.e., it cannot be deduced from the algebraic properties of the integers (which form an ordered integral domain).[32][33]

Used in proofs by minimal counterexample

[edit]

The well-ordering principle is used in proofs by minimal counterexample, also known light-heartedly as the "minimal criminal" method of proof,[34] in which to prove that every natural number belongs to a specified set , one assumes the contrary, which implies that the set of counterexamples is non-empty and thus (given the well-ordering principle) contains a smallest counterexample. One then shows that, for any counterexample, there is a still smaller counterexample, producing a contradiction. This mode of argument is the contrapositive of proof by complete induction, and is similar in its nature to Fermat's method of "infinite descent". The following are examples of this that have been found in the literature.

Example: no integer between 0 and 1

[edit]

Theorem: There is no integer between 0 and 1, so that 1 is the smallest positive integer.

Proof.[35][36] Assume, for contradiction, that there exists an integer such that . By the well-ordering principle, the set of positive integers less than 1 has a least element, say . Since , multiplying all parts of the inequality by gives . But if is an integer, then would also be an integer, which contradicts the initial assumption that was the least positive integer between 0 and 1. Therefore, this assumption is false, and there is no integer between 0 and 1.

Example: all decreasing nonnegative integer sequences finite

[edit]

Theorem: Every decreasing sequence of nonnegative integers is finite.

Proof.[37][38] Suppose that there exists a strictly decreasing sequence of nonnegative integers ; then by the well-ordering principle, has a least element for some . But must be the last in the sequence, otherwise , which contradicts the assumption that is the smallest member.

Example: prime factorization

[edit]

Theorem: Every integer greater than one is a product of finitely many primes. This theorem constitutes part of the Fundamental Theorem of Arithmetic.

Proof.[39][40][41] Let be the set of all integers greater than one that cannot be factored as a product of primes. We show that is empty: assume for the sake of contradiction that is not empty. Then, by the well-ordering principle, there is a least element ; cannot be prime since a prime number itself is considered a length-one product of primes. By the definition of non-prime numbers, has factors , where are integers greater than one and less than . Since , they are not in as is the smallest element of . So, can be factored as products of primes, where and , meaning that , a product of primes. This contradicts the assumption that , so the assumption that is nonempty must be false.

[edit]

Notes

[edit]
  1. ^ Gallier is the only source which explicitly uses the well-ordering principle to directly prove the principle of complete induction, although even Gallier does not take the well-ordering principle as an axiom, but rather proves it as a theorem from the principle of mathematical induction. See also [18], where strong induction is a corollary of the proof of strong induction from the well-ordering principle; or [26], where strong induction is proved equivalent to the well-ordering principle; or [27], where the equivalence of the three principles is proved by showing that the principle of induction implies the principle of strong induction, the principle of strong induction implies the well-ordering principle, and the well-ordering principle implies the principle of induction.

References

[edit]
  1. ^ a b Diedrichs, Danilo R.; Lovett, Stephen (2022-05-22). Transition to Advanced Mathematics. CRC Press. p. 128. ISBN 978-1-000-58166-9.
  2. ^ Katznelson, Yitzhak; Katznelson, Yonatan (2024-05-22). An Introduction to Real Analysis. American Mathematical Society. p. 3. ISBN 978-1-4704-7421-8.
  3. ^ Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics. PWS-KENT Publishing Company. p. 106. ISBN 978-0-534-98381-9.
  4. ^ a b Tuset, Lars (2024-12-02). Abstract Algebra via Numbers. Springer Nature. p. 7. ISBN 978-3-031-74623-9.
  5. ^ Apostol, Tom (1976). Introduction to Analytic Number Theory. New York: Springer-Verlag. pp. 13. ISBN 0-387-90163-9.
  6. ^ Humphreys, J. F.; Prest, M. Y. (2004-05-13). Numbers, Groups and Codes. Cambridge University Press. p. 2. ISBN 978-1-139-45116-1.
  7. ^ "II Logic and Set Theory - Well-orderings and ordinals". dec41.user.srcf.net. Retrieved 2025-07-10.
  8. ^ a b Ravichandran, V.; Razdan, Atul Kumar (2025-03-02). Fundamental Discrete Structures. Springer Nature. p. 678. ISBN 978-981-96-0069-4.
  9. ^ a b Bloch, Ethan D. (2011-02-15). Proofs and Fundamentals: A First Course in Abstract Mathematics. Springer Science & Business Media. p. 126. ISBN 978-1-4419-7127-2.
  10. ^ Deaconu, Valentin; Pfaff, Donald C. (2016-12-19). A Bridge to Higher Mathematics. CRC Press. p. 96. ISBN 978-1-4987-7526-7.
  11. ^ a b Gossett, Eric (2009-06-22). Discrete Mathematics with Proof. John Wiley & Sons. p. 146. ISBN 978-0-470-45793-1.
  12. ^ a b Silva, César Ernesto (2019). Invitation to Real Analysis. American Mathematical Soc. pp. 31–32. ISBN 978-1-4704-4928-5.
  13. ^ Takloo-Bighash, Ramin (2018-11-26). A Pythagorean Introduction to Number Theory: Right Triangles, Sums of Squares, and Arithmetic. Springer. p. 14. ISBN 978-3-030-02604-2.
  14. ^ Beck, Matthias; Geoghegan, Ross (2010-08-17). The Art of Proof: Basic Training for Deeper Mathematics. Springer Science & Business Media. p. 22. ISBN 978-1-4419-7023-7.
  15. ^ Beck, Matthias; Geoghegan, Ross (2010-08-17). The Art of Proof: Basic Training for Deeper Mathematics. Springer Science & Business Media. p. 22. ISBN 978-1-4419-7023-7.
  16. ^ Childs, Lindsay N. (2008-11-26). A Concrete Introduction to Higher Algebra. Springer Science & Business Media. p. 20. ISBN 978-0-387-74527-5.
  17. ^ Fioresi, Rita; Morigi, Marta (2021-09-01). Introduction to Linear Algebra. CRC Press. pp. 235–236. ISBN 978-1-000-42787-5.
  18. ^ a b Sohrab, Houshang H. (2014-11-15). Basic Real Analysis. Springer. p. 12. ISBN 978-1-4939-1841-6.
  19. ^ Daepp, Ulrich; Gorkin, Pamela (2006-04-18). Reading, Writing, and Proving: A Closer Look at Mathematics. Springer Science & Business Media. p. 208. ISBN 978-0-387-21560-0.
  20. ^ Sohrab, Houshang H. (2014-11-15). Basic Real Analysis. Springer. p. 11. ISBN 978-1-4939-1841-6.
  21. ^ Velleman, Daniel J. (2006-01-16). How to Prove It: A Structured Approach. Cambridge University Press. p. 294. ISBN 978-0-521-67599-4.
  22. ^ Rosenthal, Daniel; Rosenthal, David; Rosenthal, Peter (2019-04-02). A Readable Introduction to Real Mathematics. Springer. p. 11. ISBN 978-3-030-00632-7.
  23. ^ O'Regan, Gerard (2023-05-04). Mathematical Foundations of Software Engineering: A Practical Guide to Essentials. Springer Nature. p. 113. ISBN 978-3-031-26212-8.
  24. ^ Klappenecker, Andreas; Lee, Hyunyoung (2025-02-18). Discrete Structures. Springer Nature. p. 81. ISBN 978-3-031-73434-2.
  25. ^ Gallier, Jean (2011-02-01). Discrete Mathematics. Springer Science & Business Media. p. 271. ISBN 978-1-4419-8047-2.
  26. ^ Friend, Michèle; Goethe, Norma B.; Harizanov, Valentina S. (2007-08-21). Induction, Algorithmic Learning Theory, and Philosophy. Springer Science & Business Media. p. 147. ISBN 978-1-4020-6127-1.
  27. ^ Mynard, Frédéric (2018-11-24). An Introduction to the Language of Mathematics. Springer. ISBN 978-3-030-00641-9.
  28. ^ Dence, Joseph B.; Dence, Thomas P. (1999-01-20). Elements of the Theory of Numbers. Academic Press. p. 11. ISBN 978-0-12-209130-8.
  29. ^ Walschap, Gerard (2015-07-01). Multivariable Calculus and Differential Geometry. Walter de Gruyter GmbH & Co KG. p. 340. ISBN 978-3-11-036954-0.
  30. ^ Bloch, Ethan D. (2011-05-14). The Real Numbers and Real Analysis. Springer Science & Business Media. p. 64. ISBN 978-0-387-72177-4.
  31. ^ Bloch, Ethan D. (2011-02-15). Proofs and Fundamentals: A First Course in Abstract Mathematics. Springer Science & Business Media. p. 342. ISBN 978-1-4419-7127-2.
  32. ^ Korn, Granino A.; Korn, Theresa M. (2013-04-26). Mathematical Handbook for Scientists and Engineers: Definitions, Theorems, and Formulas for Reference and Review. Courier Corporation. p. 3. ISBN 978-0-486-32023-6.
  33. ^ LeVeque, William J. (2014-01-05). Fundamentals of Number Theory. Courier Corporation. p. 9. ISBN 978-0-486-14150-3.
  34. ^ Lovász, L.; Pelikán, J.; Vesztergombi, K. (2003). Discrete Mathematics: Elementary and Beyond. Undergraduate Texts in Mathematics. New York: Springer-Verlag. pp. 90–91. doi:10.1007/b97469. ISBN 0-387-95584-4. MR 1952453.
  35. ^ Bilodeau, Gerald; Thie, Paul; Keough, G. E. (2010). An Introduction to Analysis. Jones & Bartlett Learning. p. 18. ISBN 978-0-7637-7492-9.
  36. ^ Birkhoff, Garrett; Mac Lane, Saunders (1997). A survey of modern algebra. AKP classics. Wellesley, Mass: A.K. Peters. pp. 11–12. ISBN 978-1-56881-068-3.
  37. ^ Rosen, Kenneth H. (2017-10-19). Handbook of Discrete and Combinatorial Mathematics. CRC Press. p. 62. ISBN 978-1-58488-781-2.
  38. ^ Weintraub, Steven H. (2017-05-17). The Induction Book. Courier Dover Publications. pp. 11–12. ISBN 978-0-486-81199-4.
  39. ^ Beachy, John A.; Blair, William D. (2019-02-20). Abstract Algebra: Fourth Edition. Waveland Press. p. 20. ISBN 978-1-4786-3897-1.
  40. ^ Byer, Owen D.; Smeltzer, Deirdre L.; Wantz, Kenneth L. (2018-11-13). Journey into Discrete Mathematics. American Mathematical Soc. p. 136. ISBN 978-1-4704-4696-3.
  41. ^ Smith, Geoffrey C. (2012-12-06). Introductory Mathematics: Algebra and Analysis. Springer Science & Business Media. p. 48. ISBN 978-1-4471-0619-7.