- Well-order
In

mathematics , a**well-order**relation (or**well-ordering**) on a set "S" is atotal order on "S" with the property that everynon-empty subset of "S" has aleast element in this ordering.Equivalently, a well-ordering is a well-founded total order.The set "S" together with the well-order relation is then called a**well-ordered set**.Every element, except a possible

greatest element , has a unique successor (next element). Every subset which has an upper bound has a least upper bound. There may be elements (besides theleast element ) which have no predecessor.Spelling note: The hyphen is frequently omitted in contemporary papers, yielding the spellings

**wellorder**,**wellordered**, and**wellordering**.**Ordinal numbers**Every well-ordered set is uniquely

order isomorphic to a uniqueordinal number , called theorder type of the well-ordered set. The position of each element within the ordered set is also given by an ordinal number. In the case of a finite set, the basic operation ofcounting , to find the ordinal number of a particular object, or to find the object with a particular ordinal number, corresponds to assigning ordinal numbers one by one to the objects. The size (number of elements,cardinal number ) of a finite set is equal to the order type. Counting in the everyday sense typically starts from one, so it assigns to each object the size of the initial segment with that object as last element. Note that these numbers are one more than the formal ordinal numbers according to the order isomorphy, because these are equal to the number of earlier objects (which corresponds to counting from zero). Thus for finite "n", the expression "n"-th element" of a well-ordered set requires context to know whether this counts from zero or one. In a notation "β-th element" where β can also be an infinite ordinal, it will typically count from zero.For an infinite set the order type determines the

cardinality , but not conversely: well-ordered sets of a particular cardinality can have many different order types. For a countably infinite set the set of possible order types is even uncountable.**Examples***The standard ordering ≤ of the

natural number s is a well-ordering.

*The standard ordering ≤ of theinteger s is not a well-ordering, since, for example, the set of negative integers does not contain a least element.

* The following relation "R" is an example of 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 theordinal 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 number s is not a well-ordering, since, for example, the open interval (0, 1) does not contain a least element. From theZFC axioms of set theory (including theaxiom of choice ) one can show that there is a well-order of the reals; it is also possible to show that the ZFC axioms alone are not sufficient to prove the existence of a definable (by a formula) well-order of the reals. However it is consistent with ZFC that a definable well-ordering of the reals exists—for example, it is consistent with ZFC thatV=L , and it follows from ZFC+V=L that a particular formula well-orders the reals, or indeed any set.*An uncountable subset of real numbers with the standard "≤" is not well-ordered because the real line can only contain countably many disjoint intervals. A countably infinite subset may or may not be a well-order with the standard "≤". Examples of well-orders:

**The set of numbers { - 2^{-"n"}| 0 ≤ "n" < ω } has order type ω.

**The set of numbers { - 2^{-"n"}- 2^{-"m"-"n"}| 0 ≤ "m","n" < ω } has order type ω². The previous set is the set oflimit point s within the set. Within the set of real numbers, either with the ordinary topology or the order topology, 0 is also a limit point of the set. It is also a limit point of the set of limit points.

**The set of numbers { - 2^{-"n"}| 0 ≤ "n" < ω } ∪ { 1 } has order type ω + 1. With theorder topology of this set, 1 is a limit point of the set. With the ordinary topology (or equivalently, the order topology) of the real numbers it is not.**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 of order type ω + ω. Note that while every element has a successor (there is no largest element), two elements lack a predecessor: 0 and 1.

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 theaxiom of choice , states that every set can be well-ordered. The well-ordering theorem is also equivalent to theKuratowski-Zorn lemma .In a well-ordered set, every subset with an upper bound has a

supremum .**Equivalent formulations**If a set is totally ordered, then the following are equivalent:

# The set is well-ordered. That is, every nonempty subset has a least element.

#Transfinite induction works for the entire ordered set.

# Every strictly decreasing sequence of elements of the set must terminate after only finitely many steps (assuming theaxiom of dependent choice ).**Order topology**Every well-ordered set can be made into a

topological space by endowing it with theorder topology .With respect to this topology there can be two kinds of elements:

*isolated point s - these are the minimum and the elements with a predecessor

*limit point s - this type does not occur in finite sets, and may or may not occur in an infinite set; the infinite sets without limit point are the sets of order type ω, for example**N**.For subsets we can distinguish:

*Subsets with a maximum (that is, subsets which are ml|Bounded_set|Boundedness_in_order_theory|bounded by itself); this can be an isolated point or a limit point of the whole set; in the latter case it may or may not be also a limit point of the subset.

*Subsets which are unbounded by itself but bounded in the whole set; they have no maximum, but a supremum outside the subset; if the subset is non-empty this supremum is a limit point of the subset and hence also of the whole set; if the subset is empty this supremum is the minimum of the whole set.

*Subsets which are unbounded in the whole set.A subset is cofinal in the whole set if and only if it is unbounded in the whole set or it has a maximum which is also maximum of the whole set.

A well-ordered set as topological space is a

first-countable space if and only if it has order type less than or equal to ω_{1}(ml|Ordinal_number|Initial ordinal of a cardinal|omega-one), that is, if and only if the set iscountable or has the smallestuncountable order type.**See also***

Ordinal number

*Well-founded set

*Well partial order

*Prewellordering

*Directed set

*Wikimedia Foundation.
2010.*