Well-order From Wikipedia, the free encyclopedia. Printable version | Pages that link here |
66.28.98.2 Log in | Help |
|
Main Page | Recent Changes | Edit this page | History | Random Page | Special Pages |
A well-order (or well-ordering) on a set S is a total order on S with the property that every nonempty 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. 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, Well-founded set
/Talk | Main Page
Recent Changes Watch page links Edit this page History Upload files Statistics New pages Orphans Most wanted Most popular All pages Random Page Stub articles Long articles List users Bug reports Talk |
Main Page | Recent Changes | Edit this page | History | Random Page | Special Pages |