Well-ordering principle

Well-ordering principle

In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a smallest element. [cite book |title=Introduction to Analytic Number Theory |last=Apostol |first=Tom |authorlink=Tom M. Apostol |year=1976 |publisher=Springer-Verlag |location=New York |isbn=0-387-90163-9 |pages=13 ]

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:
* 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".

Garrett Birkhoff and Saunders MacLane 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). It therefore characterizes integers among integral domains; every well-ordered integral domain is isomorphic to the integers.

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Well-ordering theorem — The well ordering theorem (not to be confused with the well ordering axiom) states that every set can be well ordered.This is important because it makes every set susceptible to the powerful technique of transfinite induction.Georg Cantor… …   Wikipedia

  • Well-founded relation — In mathematics, a binary relation, R, is well founded (or wellfounded) on a class X if and only if every non empty subset of X has a minimal element with respect to R; that is, for every non empty subset S of X, there is an element m of S such… …   Wikipedia

  • Transfer principle — In mathematics, the transfer principle is a concept in Abraham Robinson s non standard analysis of the hyperreal numbers. It states that any sentence expressible in a certain formal language that is true of real numbers is also true of hyperreal… …   Wikipedia

  • Commitment ordering — In concurrency control of databases, transaction processing (transaction management), and related applications, Commitment ordering (or Commit ordering; CO; (Raz 1990, 1992, 1994, 2009)) is a class of interoperable Serializability techniques …   Wikipedia

  • Axiom of choice — This article is about the mathematical concept. For the band named after it, see Axiom of Choice (band). In mathematics, the axiom of choice, or AC, is an axiom of set theory stating that for every family of nonempty sets there exists a family of …   Wikipedia

  • Structural induction — is a proof method that is used in mathematical logic (e.g., the proof of Łoś theorem), computer science, graph theory, and some other mathematical fields. It is a generalization of mathematical induction. Structural recursion is a recursion… …   Wikipedia

  • List of mathematics articles (W) — NOTOC Wad Wadge hierarchy Wagstaff prime Wald test Wald Wolfowitz runs test Wald s equation Waldhausen category Wall Sun Sun prime Wallenius noncentral hypergeometric distribution Wallis product Wallman compactification Wallpaper group Walrasian… …   Wikipedia

  • axiom of choice — Math. the axiom of set theory that given any collection of disjoint sets, a set can be so constructed that it contains one element from each of the given sets. Also called Zermelo s axiom; esp. Brit., multiplicative axiom. * * * ▪ set theory… …   Universalium

  • Zorn's lemma — /zawrnz/, Math. a theorem of set theory that if every totally ordered subset of a nonempty partially ordered set has an upper bound, then there is an element in the set such that the set contains no element greater than the specified given… …   Universalium

  • Berry paradox — The Berry paradox is a self referential paradox arising from the expression the smallest possible integer not definable by a given number of words. Bertrand Russell, the first to discuss the paradox in print, attributed it to G. G. Berry, a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”