Editing Well-ordering principle

{{Short description|Statement that all non empty subsets of positive numbers contains a least element}}
{{distinguish|Well-ordering theorem}}
{{more citations needed|date=July 2008}}

In [[mathematics]], the '''well-ordering principle''' states that every non-empty subset of nonnegative integers contains a [[least element]].<ref>{{cite book |title=Introduction to Analytic Number Theory |last=Apostol |first=Tom |author-link=Tom M. Apostol |year=1976 |publisher=Springer-Verlag |location=New York |isbn=0-387-90163-9 |pages=[https://archive.org/details/introductiontoan00apos_0/page/13 13] |url-access=registration |url=https://archive.org/details/introductiontoan00apos_0/page/13 }}</ref> In other words, the set of nonnegative integers is [[well-order]]ed by its "natural" or "magnitude" order in which <math>x</math> precedes <math>y</math> if and only if <math>y</math> is either <math>x</math> or the sum of <math>x</math> and some nonnegative integer (other orderings include the ordering <math>2, 4, 6, ...</math>; and <math>1, 3, 5, ...</math>).

The phrase "well-ordering principle" is sometimes taken to be synonymous with the "[[well-ordering theorem]]", according to which every set can be well-ordered. On other occasions it is understood to be the proposition that the set of [[integers]] <math>\{\ldots, -2, -1, 0, 1, 2, 3, \ldots \}</math> contains a [[well-order]]ed subset, called the [[natural numbers]], in which every nonempty subset contains a least element.

==Properties==
Depending on the framework in which the natural numbers are introduced, this (second-order) property of the set of natural numbers is either an [[axiom]] or a provable theorem. For example:
* In [[Peano arithmetic]], [[second-order arithmetic]] and related systems, and indeed in most (not necessarily formal) mathematical treatments of the well-ordering principle, the principle is derived from the principle of [[mathematical induction]], which is itself taken as basic. 
* Considering the natural numbers as a subset of the real numbers, and assuming that we know already that the real numbers are complete (again, either as an axiom or a theorem about the [[real number]] system), i.e., every bounded (from below) set has an infimum, then also every set <math>A</math> of natural numbers has an infimum, say <math>a^*</math>. We can now find an integer <math>n^*</math> such that <math>a^*</math> lies in the half-open interval <math>(n^*-1,n^*]</math>, and can then show that we must have <math>a^* = n^*</math>, and <math>n^*</math> in ''<math>A</math>''.
* In [[axiomatic set theory]], the natural numbers are defined as the smallest [[Inductive set (axiom of infinity)|inductive set]] (i.e., set containing 0 and closed under the successor operation). One can (even without invoking the [[axiom of regularity|regularity axiom]]) show that the set of all natural numbers <math>n</math> such that "<math>\{0,\ldots,n\}</math> is well-ordered" is inductive, and must therefore contain all natural numbers; from this property one can conclude that the set of all natural numbers is also well-ordered.

In the second sense, this phrase is used when that proposition is relied on for the purpose of justifying proofs that take the following form: to prove that every natural number belongs to a specified set <math>S</math>, assume the contrary, which implies that the set of counterexamples is non-empty and thus contains a smallest [[counterexample]].  Then show 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]]. It is known light-heartedly as the "[[minimal criminal]]" method<ref>{{cite book
 | last1 = Lovász | first1 = L. | author1-link = László Lovász
 | last2 = Pelikán | first2 = J.
 | last3 = Vesztergombi | first3 = K. | author3-link = Katalin Vesztergombi
 | doi = 10.1007/b97469
 | isbn = 0-387-95584-4
 | mr = 1952453
 | pages = 90–91
 | publisher = Springer-Verlag | location = New York
 | series = Undergraduate Texts in Mathematics
 | title = Discrete Mathematics: Elementary and Beyond
 | url = https://books.google.com/books?id=Tn0pBAAAQBAJ&pg=PA90
 | year = 2003}}</ref> and is similar in its nature to [[Fermat|Fermat's]] method of "[[infinite descent]]".

[[Garrett Birkhoff]] and [[Saunders Mac Lane]] wrote in ''A Survey of Modern Algebra'' that this property, like the [[least upper bound axiom]] for real numbers, is non-algebraic; i.e., it cannot be deduced from the algebraic properties of the integers (which form an ordered [[integral domain]]).

==Example applications==
The well-ordering principle can be used in the following proofs.

===Prime factorization===
Theorem: ''Every integer greater than one can be factored as a product of primes.'' This theorem constitutes part of the [[Fundamental Theorem of Arithmetic|Prime Factorization Theorem]].

''Proof'' (by well-ordering principle). Let <math>C</math> be the set of all integers greater than one that ''cannot'' be factored as a product of primes. We show that <math>C</math> is empty.

Assume for the sake of contradiction that <math>C</math> is not empty. Then, by the well-ordering principle, there is a least element <math>n \in C</math>; <math>n</math> cannot be prime since a [[prime number]] itself is considered a length-one product of primes. By the definition of non-prime numbers, <math>n</math> has factors <math>a, b</math>, where <math>a, b</math> are integers greater than one and less than <math>n</math>. Since <math>a, b < n</math>, they are not in <math>C</math> as <math>n</math> is the smallest element of <math>C</math>. So, <math>a, b</math> can be factored as products of primes, where <math>a = p_1p_2...p_k</math> and <math>b = q_1q_2...q_l</math>, meaning that <math>n = p_1p_2...p_k \cdot q_1q_2...q_l</math>, a product of primes. This contradicts the assumption that <math>n \in C</math>, so the assumption that <math>C</math> is nonempty must be false.<ref name='mit' >{{cite book |last1=Lehman |first1=Eric |last2=Meyer |first2=Albert R |last3=Leighton |first3=F Tom |title=Mathematics for Computer Science |url=https://courses.csail.mit.edu/6.042/spring17/mcs.pdf |access-date=2 May 2023}}</ref>

===Integer summation===
Theorem: <math>1 + 2 + 3 + ... + n = \frac{n(n + 1)}{2}</math> for all positive integers <math>n</math>.

''Proof''. Suppose for the sake of contradiction that the above theorem is false. Then, there exists a non-empty set of positive integers <math>C = \{n \in \mathbb N \mid 1 + 2 + 3 + ... + n \neq \frac{n(n + 1)}{2}\}</math>. By the well-ordering principle, <math>C</math> has a minimum element <math>c</math> such that when <math>n = c</math>, the equation is false, but true for all positive integers less than <math>c</math>. The equation is true for <math>n = 1</math>, so <math>c > 1</math>; <math>c - 1</math> is a positive integer less than <math>c</math>, so the equation holds for <math>c - 1</math> as it is not in <math>C</math>. Therefore, 

<math display=middle>\begin{align}
1 + 2 + 3 + ... + (c - 1) &= \frac{(c - 1)c}{2} \\
1 + 2 + 3 + ... + (c - 1) + c &= \frac{(c - 1)c}{2} + c\\
&= \frac{c^2 - c}{2} + \frac{2c}{2}\\
&= \frac{c^2 + c}{2}\\
&= \frac{c(c + 1)}{2}
\end{align}</math>,

which shows that the equation holds for <math>c</math>, a contradiction. So, the equation must hold for all positive integers.<ref name='mit' />

==References==
{{reflist}}

[[Category:Wellfoundedness]]
[[Category:Mathematical principles]]

[[cs:Princip dobrého uspořádání]]