Well-order
From Exampleproblems
In mathematics, a well-order (or well-ordering) on a set S is an order relation on S with the property that every non-empty subset of S has a least element in this ordering. The set S together with the well-order is then called a well-ordered set. A well-order is necessarily a total order.
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. In a well-ordered set an infinite decreasing sequence cannot exist.
Spelling note: The hyphen is frequently omitted in contemporary papers, yielding the spellings wellorder, wellordered, 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 two copies of the natural numbers, ordered in such a way that every element of the second copy is bigger than every element of the first copy. Within each copy, the normal order is used. This is a well-ordered set and is usually denoted by ω + ω. Note that while every element has a successor (there is no largest element), two elements lack a predecessor: the zero from copy number one (the overall smallest element) and the zero from copy number two.
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.
