Information About

Well-ordering Principle
  CATEGORIES ABOUT WELL-ORDERING PRINCIPLE
   
wellfoundedness
   
SHOPPER'S DELIGHT
 
Shop For:  
Department
Price Minimum:
Price Maximum:
      



On other occasions the phrase is taken to mean the proposition that the set of Natural Numbers {0, 1, 2, 3, ....} is Well-ordered , i.e., each of its non-empty subsets has a smallest member.

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:
  • 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,..., n}'' is well-ordered" is inductive, and must therefore contain all natural numbers; from this property it is easy to conclude that the set of all natural numbers is also well-ordered.


In the second sense, the 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 and infer the existence of a (non-zero) smallest counterexample. Then show either that there must be a still smaller counterexample or that the smallest counterexample is not a counter example, producing a contradiction. This mode of argument bears the same relation to proof by Mathematical Induction that "If not B then not A" (the style of '' Modus Tollens '') bears to "If A then B" (the style of '' Modus Ponens ''). It is known light-heartedly as the " Minimal Criminal " method and is similar in its nature to Fermat's method of " Infinite Descent ".