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 . ${\ displaystyle S}$ ${\ displaystyle S}$ ${\ displaystyle (S, <)}$ ${\ displaystyle S}$ ${\ displaystyle {<}}$ ${\ displaystyle S}$

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. ${\ displaystyle (S, <)}$ ${\ displaystyle (a_ {i}) _ {i \ in \ mathbb {N}}}$ ${\ displaystyle S}$ ${\ displaystyle i}$ ${\ displaystyle a_ {i + 1} <a_ {i}}$ ${\ displaystyle S}$ ${\ displaystyle {<}}$ ${\ displaystyle (S, <)}$

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. ${\ displaystyle a <b}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle b}$ ${\ displaystyle a}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle S}$

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. ${\ displaystyle \ {x_ {1}, \ dots, x_ {n} \}}$ ${\ displaystyle x_ {i} <x_ {i + 1}}$ ${\ displaystyle x_ {n} <x_ {1}}$

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:

{\ displaystyle 1 <3 <5 <\ cdots \; <\; 2 <4 <6 <\ cdots}

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. ${\ displaystyle \ omega + \ omega}$ ${\ displaystyle \ omega \ cdot 2}$

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). ${\ displaystyle S}$ ${\ displaystyle S}$ ${\ displaystyle b \ in S}$ ${\ displaystyle \ {a \ in S | a <b \}}$ ${\ displaystyle b}$

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

[1] 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 .

[2] 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).

[3] Martin Ziegler: Lecture on set theory , University of Freiburg, 1992–2014, page 12