|
In mathematics, a well-order (or
well-ordering) on a set S is a total order 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.
For example, the standard ordering of the natural numbers is a
well-ordering, but neither the standard ordering of the integers nor the standard
ordering of the positive real numbers is a well-ordering.
In a well-ordered set, there cannot exist any infinitely long descending chains. Using the axiom of choice, one can show that this property is in fact equivalent to the well-order property; it
is also clearly equivalent to the Kuratowski-Zorn
lemma.
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.
See also Ordinal number, Well-founded set, Well partial order
|