Editing Well-ordering principle (section)

==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]]).