Encyclopedia > Well-order

  Article Content

Well-order

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 need 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 principle, which is equivalent to the axiom of choice, states that every set can be well-ordered.


See also Ordinal number, Well-founded set



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Alexander Bain

... in logical and moral philosophy (1857-1862 and 1864-1869) to the university of London, and in moral science in the Indian Civil Service examinations. In 1860 he was ...