A well-order on a set is a total order in which every non-empty subset of has a smallest element with respect to this order, i.e. a total well-founded order . The pair of the set together with the well-order is then called a well-ordered structure or, imprecisely, a well-ordered set, where the order is implicit. The terms come from Cantor's set theory .
In a well-ordered structure there is no infinitely long descending chain; H. no infinite sequence in such that for all true . Using the axiom of dependent choice , the converse also follows: if there is no infinite descending sequence (re ) in, then there is a well-ordered structure.
In the context of a well-order, there are the terms of (direct / immediate) predecessor and (direct / immediate) successor . For is the predecessor of and the equivalent of the successor of if there are no elements between and . In a well-ordered set there is always at least one element without a predecessor, including the smallest element by itself. The successor of an element is always clearly defined: if it exists, it is the unambiguous minimum of the set of elements that are larger. At most there can be one largest element that has no successor. Multiple elements without a successor are not possible. In contrast, there can be any number of elements without a direct predecessor.
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 that set. The induction is a special case of transfinite induction.
The only isomorphism of a well-order to itself is identity , and a well-order is never isomorphic to a real starting segment of itself. Two well-orders are either isomorphic , or exactly one is isomorphic to a real starting segment of the other. The respective isomorphisms are then unambiguous. If you now consider the equivalence classes with regard to isomorphism, each has a canonical representative, the associated ordinal number . Every well-order is isomorphic to exactly one ordinal number. The class of ordinal numbers itself is also well ordered.
Sometimes all elements that are smaller than the element under consideration are referred to as their predecessors , including the indirect ones ; analog for successors. See order relation §Predecessor and successor .
Wiebke Petersen: Mathematical Foundations of Computational Linguistics - Order Relations, 4th set of slides, Heinrich-Heine-Universität Düsseldorf, Institute of Language and Information, PDF: WS 2011/12 p. 93 WS 2013/14 p. 90 , accessed on April 21, 2018 .
Simple examples and counterexamples
A well-order is defined on a finite set with . But if it still applies , there is a cycle and there is no longer any well-being.
Multiple items with no predecessor
The natural numbers should be ordered in such a way that every even number is greater than every odd number. The even and odd numbers should be arranged below one another as usual, i.e. in the following way:
Obviously this is a well-ordered set: If a subset contains any odd numbers, the smallest of them is also the smallest number of the subset (all even numbers are larger ); If it contains only even numbers, the smallest of these is also the smallest in the sense of well-order, because odd numbers that would be smaller are not available. The ordinal number for this well-order is usually denoted by or . There is no largest element here, but two elements without a predecessor: the one and the two.
The above definition can be extended to classes as follows :
A well-ordered class is a class with a well-founded linear order <on which is preceded by small . This means that for all the class is the ancestor of a set (i.e. not an actual class).
- Oliver Deiser: Introduction to set theory , Springer, 2004, ISBN 978-3-540-20401-5 , pages 222-230