Natural Numbers:Well-Ordering

In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive 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 positive 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". On other occasions it is understood to be the proposition that the set of integers $\{...,-2,-1,0,1,2,3,...\}$ contains a well-ordered subset, called the natural numbers, in which every nonempty subset contains a least element.

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 Failed to parse (syntax error): {\displaystyle a^{*}}a^{*}} . We can now find an integer Failed to parse (syntax error): {\displaystyle n^{*}}n^{*}} such that Failed to parse (syntax error): {\displaystyle a^{*}}a^{*}} lies in the half-open interval $(n^{*}-1,n^{*}]$, and can then show that we must have $a^{*}=n^{*}$, and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^{*}}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 and is similar in its nature to Fermat's method of "infinite descent".

Resources

• Well-ordering principle, Wikipedia