|
In mathematics, a well-order relation (or well-ordering) on a set S is a linear order relation 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 linear ordering. The set S together with the well-order relation is then called a well-ordered set. Roughly speaking, a well-ordered set is ordered in such a way that its elements can be considered one at a time, in order, and any time you haven't examined all of the elements, there's always a unique next element to consider. Spelling note: The hyphen is frequently omitted in contemporary papers, yielding the spellings wellorder, wellordered, and wellordering.
Examples
R can be visualized as follows: 0 1 2 3 4 ..... -1 -2 -3 ..... R is isomorphic to the ordinal number ω + ω. 0 -1 1 -2 2 -3 3 -4 4 ... Properties In a well-ordered set, every element, unless it is the overall largest, has a unique successor: the smallest element that is larger than it. However, not every element needs to have a predecessor. As an example, consider an ordering of the natural numbers where all even numbers are less than all odd numbers, and the usual ordering applies within the evens and the odds. 0 2 4 6 8 ... 1 3 5 7 9 ... This is a well-ordered set and is denoted by ω + ω. Note that while every element has a successor (there is no largest element), two elements lack a predecessor: zero and one. 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 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. Equivalent formulations If a set is totally ordered, then the following are equivalent: (1) The set is well-ordered. That is, every nonempty subset has a least element. (2) Transfinite induction works for the entire ordered set. (3) Every strictly decreasing sequence of elements of the set must terminate after only finitely many steps (assuming the axiom of dependent choice). Ordinal numbers Every well-ordered set is uniquely order isomorphic to a unique ordinal number. In fact, this property is the motivation behind the definition of ordinal numbers. See also | ||||||||
|
| |||||||||
 |
|
| |