In mathematics, a well-order relation (or well-ordering) on a set S is a 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 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, 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.
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 |
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.
For an infinite set the order type determines the cardinality, but not conversely: well-ordered sets of a particular cardinality can have many different order types. For a countably infinite set the set of possible order types is even uncountable.
The standard ordering ≤ of the natural numbers is a well-ordering and has the additional property that every nonzero natural number has a unique predecessor.
Another well-ordering of the natural numbers is given by defining that all even numbers are less than all odd numbers, and the usual ordering applies within the evens and the odds:
This is a well-ordered set of order type ω + ω. Every element has a successor (there is no largest element). Two elements lack a predecessor: 0 and 1.
Unlike the standard ordering ≤ of the natural numbers, the standard ordering ≤ of the integers is not a well-ordering, since, for example, the set of negative integers does not contain a least element.
The following relation R is an example of well-ordering of the integers: x R y if and only if one of the following conditions holds:
This relation R can be visualized as follows:
R is isomorphic to the ordinal number ω + ω.
Another relation for well-ordering the integers is the following definition: x ≤z y iff (|x| < |y| or (|x| = |y| and x ≤ y)). This well-order can be visualized as follows:
This has the order type ω.
The standard ordering ≤ of the positive real numbers is not a well-ordering, since, for example, the open interval (0, 1) does not contain a least element. From the ZFC axioms of set theory (including the axiom of choice) one can show that there is a well-order of the reals; it is also possible to show that the ZFC+GCH axioms alone are not sufficient to prove the existence of a definable (by a formula) well-order of the reals.[1] However it is consistent with ZFC that a definable well-ordering of the reals exists—for example, it is consistent with ZFC that V=L, and it follows from ZFC+V=L that a particular formula well-orders the reals, or indeed any set.
An uncountable subset of real numbers with the standard "≤" is not well-ordered because the real line can only contain countably many disjoint intervals. A countably infinite subset may or may not be a well-order with the standard "≤". Examples of well-orders:
If a set is totally ordered, then the following are equivalent to each other:
Every well-ordered set can be made into a topological space by endowing it with the order topology.
With respect to this topology there can be two kinds of elements:
For subsets we can distinguish:
A subset is cofinal in the whole set if and only if it is unbounded in the whole set or it has a maximum which is also maximum of the whole set.
A well-ordered set as topological space is a first-countable space if and only if it has order type less than or equal to ω1 (omega-one), that is, if and only if the set is countable or has the smallest uncountable order type.