Well-order

A well-ordering of a set S is a total order in which each non-empty subset of S has a least element with respect to this order. The set S together with the well-ordering is called a well-ordered set. Both terms are from the set theory of Cantor.

For example, the normal arrangement of the natural numbers is a well-ordering, but neither the normal arrangement of the integers nor the positive real numbers is a well-ordering.

If a set S of well-ordered, so there is no infinite descending chain long, that is, no infinite sequence in S, such that for all. Using a weak version of the axiom of choice ( Axiom of Dependent Choice ) follows the converse: if there are no infinite descending chain, as is well-ordered.

In a well-ordered set, there is always an element without predecessors, namely the smallest element of S itself the successor of an element is always uniquely determined. There can be a greatest element which has no successor. Several elements without successors are not possible.

In contrast, there may be several ( even infinitely many ) be elements without predecessors.

As an example, the natural numbers are to be so arranged that every even number " greater " than any odd number. With each other to the even and odd numbers to be sorted, as usual, that is, in the following manner:

Apparently, this is a well-ordered set: Contains a subset of any odd numbers, then the minimum number of them also "smallest" number of subset ( all even numbers are " greater "); contains only even numbers, so is the smallest of these, the "smallest" in the sense of well-ordering, because odd numbers, the "small" would be, are not even available. The ordinal number of the well-ordering is usually denoted by. There is no greatest element, but two elements without predecessors: the One and the Two.

If a set is well-ordered, then the technique of transfinite induction can be used to show that a given statement is true for all elements of this set. The induction is a special case of transfinite induction.

The well-ordering theorem states that every set can be well ordered. Based on the rest of the set theoretic axioms of this sentence is equivalent to the axiom of choice.