Editing Well-ordering principle (section)

==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' />