Well-being
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 .
properties
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 well -ordered theorem says that any amount can be well-ordered. On the basis of the other set- theoretical axioms , this theorem is equivalent to the axiom of choice .
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.
Remarks
-
↑ 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 .
Examples
Simple examples and counterexamples
The normal arrangement of the natural numbers is already a well-order, but neither the normal order of the whole numbers nor that of the positive real numbers is a well-order.
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.
Well-ordered classes
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).
literature
- Oliver Deiser: Introduction to set theory , Springer, 2004, ISBN 978-3-540-20401-5 , pages 222-230
credentials
- ^ Thomas Jech : Set Theory . Ed .: Samuel Eilenberg and Hyman Bass. 1st edition. Academic Press Inc., 1978, ISBN 0-12-381950-4 , pp. 13-14 (English).
- ↑ Martin Ziegler: Lecture on set theory , University of Freiburg, 1992–2014, page 12