well-ordering principle

{{Short description|Statement that all non empty subsets of positive numbers contains a least element}}

In mathematics, the well-ordering principle states that every non-empty subset of nonnegative integers contains a least element.{{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 }} In other words, the set of nonnegative integers is well-ordered by its "natural" or "magnitude" order in which $x$ precedes $y$ if and only if $y$ is either $x$ or the sum of $x$ and some nonnegative integer (other orderings include the ordering $2, 4, 6, ...$ ; and $1, 3, 5, ...$ ).

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 $\{\ldots, -2, -1, 0, 1, 2, 3, \ldots \}$ contains a well-ordered 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 $A$ of natural numbers has an infimum, say $a^*$ . We can now find an integer $n^*$ such that $a^*$ lies in the half-open interval $(n^*-1,n^*]$ , and can then show that we must have $a^* = n^*$ , and $n^*$ in $A$ .
In axiomatic set theory, the natural numbers are defined as the smallest inductive set (i.e., set containing 0 and closed under the successor operation). One can (even without invoking the regularity axiom) show that the set of all natural numbers $n$ such that " $\{0,\ldots,n\}$ 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 $S$ , 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{{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}} and is similar in its nature to 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 Prime Factorization Theorem.

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

Assume for the sake of contradiction that $C$ is not empty. Then, by the well-ordering principle, there is a least element $n \in C$ ; $n$ cannot be prime since a prime number itself is considered a length-one product of primes. By the definition of non-prime numbers, $n$ has factors $a, b$ , where $a, b$ are integers greater than one and less than $n$ . Since $a, b < n$ , they are not in $C$ as $n$ is the smallest element of $C$ . So, $a, b$ can be factored as products of primes, where $a = p_1p_2...p_k$ and $b = q_1q_2...q_l$ , meaning that $n = p_1p_2...p_k \cdot q_1q_2...q_l$ , a product of primes. This contradicts the assumption that $n \in C$ , so the assumption that $C$ is nonempty must be false.{{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}}

=Integer summation=

Theorem: $1 + 2 + 3 + ... + n = \frac{n(n + 1)}{2}$ for all positive integers $n$ .

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

$\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}$ ,

which shows that the equation holds for $c$ , a contradiction. So, the equation must hold for all positive integers.

References

Category:Wellfoundedness

Category:Mathematical principles

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