Well-order
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
- The standard ordering ≤ of the natural numbers is a well-ordering.
- The standard ordering ≤ of the integers is not a well-ordering, since, for example, the set of negative integers does not contain a least element.
- The following relation R is a well-ordering of the integers: x R y if and only if one of the following conditions holds:
- x = 0
- x is positive, and y is negative
- x and y are both positive, and x ≤ y
- x and y are both negative, and y ≤ x
- R can be visualized as follows:
0 1 2 3 4 ..... -1 -2 -3 .....
- R is isomorphic to the ordinal number ω + ω.
- Another relation for well-ordering the integers is the following definition: x <z y iff |x| < |y| or (|x| = |y| and x ≤ y).
This well-order can be visualized as follows:
0 -1 1 -2 2 -3 3 -4 4 ...
- The standard ordering ≤ of the positive real numbers is not a well-ordering, since, for example, the open interval (0, 1) does not contain a least element. There exist proofs depending on the axiom of choice that it is possible to well order the real numbers, but these proofs are non-constructive and no one has yet shown a method to well order the real numbers.
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) Every nonempty subset has a least element.
(2) Transfinite induction works for the entire ordered set.
(3) Every strictly decreasing sequence must terminate after only finitely many steps (assuming the axiom of dependent choices).
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.