Well-order

related topics
{math, number, function}
{language, word, form}

In mathematics, a well-order relation (or well-ordering) on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order. The set S together with the well-order relation is then called a well-ordered set.

Every element s, except a possible greatest element, has a unique successor (next element), namely the least element of the subset of all elements greater than s. Every subset which has an upper bound has a least upper bound. There may be elements (besides the least element) which have no predecessor.

If a set is well-ordered (or even if it merely admits a wellfounded relation), the proof technique of transfinite induction can be used to prove that a given statement is true for all elements of the set.

The observation that the natural numbers are well-ordered by the usual less-than relation is commonly called the well-ordering principle (for natural numbers).

The well-ordering theorem, which is equivalent to the axiom of choice, states that every set can be well-ordered. The well-ordering theorem is also equivalent to the Kuratowski-Zorn lemma.

Spelling note: The hyphen is frequently omitted in contemporary papers, yielding the spellings wellorder, wellordered, and wellordering.

Contents

Ordinal numbers

Every well-ordered set is uniquely order isomorphic to a unique ordinal number, called the order type of the well-ordered set. The position of each element within the ordered set is also given by an ordinal number. In the case of a finite set, the basic operation of counting, to find the ordinal number of a particular object, or to find the object with a particular ordinal number, corresponds to assigning ordinal numbers one by one to the objects. The size (number of elements, cardinal number) of a finite set is equal to the order type. Counting in the everyday sense typically starts from one, so it assigns to each object the size of the initial segment with that object as last element. Note that these numbers are one more than the formal ordinal numbers according to the isomorphic order, because these are equal to the number of earlier objects (which corresponds to counting from zero). Thus for finite n, the expression "n-th element" of a well-ordered set requires context to know whether this counts from zero or one. In a notation "β-th element" where β can also be an infinite ordinal, it will typically count from zero.

Full article ▸

related documents
Diophantine set
Kolmogorov space
Goodstein's theorem
Carmichael number
Laurent series
Group representation
Cartesian product
Local ring
Lebesgue measure
Convex set
Controllability
Axiom of regularity
Conjunctive normal form
Euler's totient function
Kruskal's algorithm
Generalized Riemann hypothesis
Monotonic function
Algebraic topology
Symmetric group
Diffeomorphism
Isomorphism theorem
Tree (data structure)
Differential topology
Mersenne twister
Knight's tour
Golomb coding
Analytic geometry
Automated theorem proving
Discriminant
Search algorithm