View source for Well-order

{{short description|Class of mathematical orderings}}
{{stack|{{Binary relations}}}}

In [[mathematics]], a '''well-order''' (or '''well-ordering''' or '''well-order relation''') on a [[Set (mathematics)|set]] {{mvar|S}} is a [[total ordering]] on {{mvar|S}} with the property that every [[non-empty]] [[subset]] of {{mvar|S}} has a [[least element]] in this ordering. The set {{mvar|S}} together with the ordering is then called a '''well-ordered set''' (or '''woset''').<ref name="woset">{{cite conference|vauthors=Manolios P, Vroon D|title=Algorithms for Ordinal Arithmetic|conference=International Conference on Automated Deduction|url=https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=5267829dccc30bfc98ad4844e5555cb86955c8b4|access-date=2025-01-16}}</ref> In some academic articles and textbooks these terms are instead written as '''wellorder''', '''wellordered''', and '''wellordering''' or '''well order''', '''well ordered''', and '''well ordering'''.

Every non-empty well-ordered set has a least element. Every element {{mvar|s}} of a well-ordered set, except a possible [[greatest element]], has a unique successor (next element), namely the least element of the subset of all elements greater than {{mvar|s}}. There may be elements, besides the least element, that have no predecessor (see {{slink||Natural numbers}} below for an example). A well-ordered set {{mvar|S}} contains for every subset {{mvar|T}} with an [[upper bound]] a [[least upper bound]], namely the least element of the subset of all upper bounds of {{mvar|T}} in {{mvar|S}}.

If ≤ is a [[non-strict order|non-strict]] well ordering, then < is a strict well ordering. A relation is a strict well ordering if and only if it is a [[well-founded relation|well-founded]] [[strict total order]]. The distinction between strict and non-strict well orders is often ignored since they are easily interconvertible.

Every well-ordered set is uniquely [[order isomorphic]] to a unique [[ordinal number]], called the [[order type]] of the well-ordered set. The [[well-ordering theorem]], which is equivalent to the [[axiom of choice]], states that every set can be well ordered. If a set is well ordered (or even if it merely admits a [[well-founded relation]]), the proof technique of [[transfinite induction]] can be used to prove that a given statement is true for all elements of the set.

The observation that the [[natural numbers]] are well ordered by the usual less-than relation is commonly called the [[well-ordering principle]] (for natural numbers).

== Examples and counterexamples ==

=== Natural numbers ===
The standard ordering ≤ of the [[natural number]]s is a well ordering:

:<math>\begin{matrix}
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots
\end{matrix}</math>

This well ordering has the additional property that every non-zero natural number has a unique predecessor. Its [[order type]] is [[Omega (ordinal)|{{math|''ω''}}]], the first infinite ordinal.

Another well ordering of the natural numbers is given by defining that all even numbers are less than all odd numbers, and the usual ordering applies within the evens and the odds:

:<math>\begin{matrix}
0 & 2 & 4 & 6 & 8 & \dots & 1 & 3 & 5 & 7 & 9 & \dots
\end{matrix}</math>

This is a well-ordered set of order type {{math|''ω'' + ''ω''}}. Every element has a successor (there is no largest element).  Two elements lack a predecessor: 0 and 1.

=== Integers ===
Unlike the standard ordering ≤ of the [[natural number]]s, the standard ordering ≤ of the [[integer]]s is not a well ordering, since, for example, the set of [[negative number|negative]] integers does not contain a least element.

The following [[binary relation]] {{mvar|R}} is an example of well ordering of the integers: {{mvar|x R y}} [[if and only if]] one of the following conditions holds:
# {{math|1=''x'' = 0}}
# {{mvar|x}} is positive, and {{mvar|y}} is negative
# {{mvar|x}} and {{mvar|y}} are both positive, and {{math|''x'' ≤ ''y''}}
# {{mvar|x}} and {{mvar|y}} are both negative, and {{math|{{abs|''x''}} ≤ {{abs|''y''}}}}
This relation {{mvar|R}} can be visualized as follows: 
:<math>\begin{matrix}
0 & 1 & 2 & 3 & 4 & \dots & -1 & -2 & -3 & \dots
\end{matrix}</math>
{{mvar|R}} is isomorphic to the [[ordinal number]] {{math|''ω'' + ''ω''}}.

Another relation for well ordering the integers is the following definition: <math>x \leq_z y</math> [[if and only if]] 
:<math>|x| < |y| \qquad \text{or}  \qquad |x| = |y| \text{ and } x \leq y.</math>
This well order can be visualized as follows: 
:<math>\begin{matrix}
0 & -1 & 1 & -2 & 2 & -3 & 3 & -4 & 4 & \dots
\end{matrix}</math>

This has the [[order type]] {{mvar|ω}}.

=== Rational numbers ===
The standard ordering ≤ of the [[rational number]]s is not a well ordering, and unlike with the integers, this remains true for the non-negative rational numbers, since, for example, the set <math>\{1/n \,|\, n=1,2,3,\dots\}</math> has no least element. However, since the set of rational numbers {{mathbb|Q}} is [[countable]], there exists a well ordering of {{mathbb|Q}} that is [[order isomorphic]] to the standard ordering of the natural numbers, and thus has the order type {{mvar|ω}}.

There exists many subsets of {{mathbb|Q}} that are well-ordered under the standard ordering ≤ (the set of natural numbers is a trivial example). Other examples include:
*The set of numbers <math>\{-2^{-n} \,|\, 0 \leq n < \omega\}</math> is a ''bounded'' subset of {{mathbb|Q}} with order type {{mvar|ω}} under the standard ordering:
::<math>\begin{matrix}
-1 & -1/2 & -1/4 & -1/8 & -1/16 & \dots
\end{matrix}</math>
*The set of numbers <math>\{-2^{-n} - 2^{-m-n} \,|\, 0 \leq m,n < \omega \}</math> has order type {{math|''ω''<sup>2</sup>}}:
::<math>\begin{matrix}
-1-1 & -1-1/2 & -1-1/4 & \dots \\
-1 = -1/2-1/2 & -1/2-1/4 & -1/2-1/8 & \dots \\
-1/2 = -1/4-1/4 & -1/4-1/8 & -1/4-1/16 & \dots \\
\dots & \dots & \dots & \dots
\end{matrix}</math>
:The previous set is the set of [[limit 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 <math>\{-2^{-n} \,|\, 0 \leq n < \omega\} \cup \{1\}</math> has order type {{math|''ω'' + 1}}:
::<math>\begin{matrix}
-1 & -1/2 & -1/4 & -1/8 & -1/16 & \dots & 1
\end{matrix}</math>
:With the [[order topology]] of this set, 1 is a limit point of the set, despite being separated from the only limit point 0 under the ordinary topology of the real numbers.

In fact, for every countable ordinal {{mvar|α}}, there exists a subset of {{mathbb|Q}} with order type {{mvar|α}} under the standard ordering. This is a special case of the theorem that every countable [[linear ordering]] {{mvar|A}} can be embedded order-preservingly into {{math|({{mathbb|Q}}, ≤)}}, which can be proved by enumerating the elements of {{mvar|A}} as a sequence {{tmath|a_1, a_2, a_3, \ldots}}, and sequentially assigning a number {{tmath|x_n \in \Q}} to every {{tmath|a_n}} such that the ordering between the finitely many elements {{tmath|a_1, a_2, \ldots, a_n}} is preserved.<ref>{{cite arXiv|last1=Smith |first1=Trey |last2=Ozer |first2=Aksel |title=Linear Orders and the Real Line |date=2025 |class=math.NT |eprint=2508.15644}}</ref>

=== Reals ===
The standard ordering ≤ of any [[Interval_(mathematics)|real interval]] is not a well ordering, since, for example, the [[open interval]] {{tmath|(0, 1) \subseteq [0, 1]}} does not contain a least element. In fact, although the [[well-ordering theorem]] (equivalent to the [[axiom of choice]]) implies that there is a well order of the reals, the [[ZFC]] axioms are not sufficient to prove the existence of a definable (by a formula) well order of the reals, even if the [[generalized continuum hypothesis]] is assumed to be true.<ref>{{cite journal |author-link=Solomon Feferman |first=S. |last=Feferman |title=Some Applications of the Notions of Forcing and Generic Sets |journal=[[Fundamenta Mathematicae]] |volume=56 |issue=3 |year=1964 |pages=325–345 |doi=10.4064/fm-56-3-325-345 |url=https://eudml.org/doc/213821|doi-access=free }}</ref> However it is consistent with ZFC that a definable well ordering of the reals exists—for example, it is consistent with ZFC that [[V=L]], and it follows from ZFC+V=L that a particular formula well orders the reals, or indeed any set.

An uncountable subset of the real numbers with the standard ordering ≤ cannot be a well order: Suppose {{mvar|X}} is a subset of {{tmath|\R}} well ordered by {{char|≤}}. For each {{mvar|x}} in {{mvar|X}}, let {{math|''s''(''x'')}} be the successor of {{mvar|x}} in {{char|≤}} ordering on {{mvar|X}} (unless {{mvar|x}} is the largest element of {{mvar|X}}). All intervals of the form {{math|(''x'', ''s''(''x''))}} are non-empty and disjoint. Since every such open interval contains a rational number, and {{mathbb|Q}} is countable, there can only be countably many such intervals. And since {{math|(''x'', ''s''(''x''))}} is defined for all {{math|''x'' ∈ ''X''}} except possibly for a largest element, {{mvar|X}} must be countable.

== Equivalent formulations ==
If a set is [[Total order|totally ordered]], then the following are equivalent to each other:

# 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 the [[axiom of dependent choice]]).
# Every subordering is isomorphic to an initial segment (see {{section link||initial segments}} below).

== Initial segments ==
An '''initial segment''', determined by an element <math>x</math> of a [[poset]] <math> X </math>, is a subset of form <math>\{ y \in X \mid y < x \}</math>.<ref name="Halmos_14">{{harvnb|Halmos|1960|loc=§ 14}}</ref> By convention, <math>X</math> itself is also counted as an (improper) initial segment.

For a well-ordered set <math>X</math>, a subset <math>S \subset X</math> is an initial segment (either <math>X</math> or an initial segment by some element) if and only if it contains
:<math>\{ y \in X \mid y < x \}</math>
for each <math>x</math> in <math>S</math>.<ref>{{cite book |last1=松坂 (Matsuzaka) |first1=和夫 (Kazuo)|title=集合・位相入門 |date=1968 |publisher=岩波書店 |language=Japanese |url=https://cir.nii.ac.jp/crid/1971149384867694882|location=Ch. 3., § 2., (B) Lemma 1.}}</ref><ref>{{harvnb|Tao|2009|loc=Well-ordered sets, Exercise 5.}}</ref> In other words, an initial segment is the same thing as a [[lower set]] in [[order theory]] and this characterization is sometimes also taken as a definition of an initial segment.<ref>{{harvnb|Tao|2009|loc=Well-ordered sets, Definition 2.}}</ref>

Initial segments are often used in the study of well-ordered sets and [[well-founded set]]s. For example, an [[ordinal number]] is a well-ordered set <math>\alpha</math> whose elements are all initial segments determined by themselves; i.e., for each element <math>x</math> in <math>\alpha</math>, we have:
:<math>x = \{ y \in \alpha \mid y < x \}.</math><ref name="Halmos_19">{{harvnb|Halmos|1960|loc=§ 19}}</ref>
See also {{section link||Ordinal numbers}} below. Initial segments are also used in the statement of the [[transfinite recursion theorem]].

Properties of initial segments include:
* A well-ordered set is never isomorphic to a proper initial segment of itself.<ref name="Halmos_18">{{harvnb|Halmos|1960|loc=§ 18}}</ref> Also, given two well-ordered sets <math>X, Y</math>, either <math>X</math> is isomorphic to an initial segment of <math>Y</math> or <math>Y</math> is isomorphic to an initial segment of <math>X</math>.
* A morphism between well-ordered sets sends initial segments to initial segments, where a morphism is an injective order-preserving map whose image is an initial segment.<ref>{{harvnb|Tao|2009|loc=Well-ordered sets, Exercise 7.}}</ref>
* Initial segments give an ordering <math>\trianglelefteq</math> on the class <math>\operatorname{Well}</math> of well-ordered sets; namely, <math>A \trianglelefteq B</math> if and only if <math>A \subset B</math> is a subset with the ordering restricted from <math>B</math> and <math>A</math> is an initial segment of <math>B</math>.<ref name="Halmos">{{harvnb|Halmos|1960|loc=§ 17}}</ref> The union of a chain of well-ordered sets is then well-ordered, where a chain is with respect to <math>\trianglelefteq</math>.<ref name="Halmos" /> For ordinals, this ordering given by initial segments coincides with set inclusion.<ref>{{harvnb|Halmos|1960|loc=§ 20.}}</ref>
* A set with a binary relation is well-founded if and only if it is covered by well-founded initial segments.<ref>{{harvnb|Taylor|1999|loc=Propositon 2.6,6,}}</ref>

== Order topology==
Every well-ordered set can be made into a [[topological space]] by endowing it with the [[order 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 {{mvar|ω}}, for example the [[natural numbers]] {{tmath|\N.}}

For subsets we can distinguish:
*Subsets with a maximum (that is, subsets that are [[Bounded set#Boundedness in order theory|bounded]] by themselves); 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 that are unbounded by themselves 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 that are unbounded in the whole set.

A subset is [[Cofinal (mathematics)|cofinal]] in the whole set if and only if it is unbounded in the whole set or it has a maximum that 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 ω<sub>1</sub> ([[first uncountable ordinal|omega-one]]), that is, if and only if the set is [[countable]] or has the smallest [[uncountable]] order type.

== Ordinal numbers ==
{{main|Ordinal number}}

Every well-ordered set is uniquely [[order isomorphic]] to a unique [[ordinal number]], called the [[order 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 of [[counting]], 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.<ref>{{cite journal
 | last1 = Bonnet | first1 = Rémi
 | last2 = Finkel | first2 = Alain
 | last3 = Haddad | first3 = Serge
 | last4 = Rosa-Velardo | first4 = Fernando
 | doi = 10.1016/j.ic.2012.11.003
 | journal = Information and Computation
 | mr = 3016456
 | pages = 1–22
 | title = Ordinal theory for expressiveness of well-structured transition systems
 | volume = 224
 | year = 2013}}</ref> 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 isomorphic order, because these are equal to the number of earlier objects (which corresponds to counting from zero). Thus for finite {{mvar|n}}, the expression "{{mvar|n}}-th element" of a well-ordered set requires context to know whether this counts from zero or one. In an expression "{{mvar|β}}-th element" where {{mvar|β}} 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: sets of a particular infinite cardinality can have well-orders of many different types (see {{slink||Natural numbers}}, below, for an example). For a [[countably infinite]] set, the set of possible order types is uncountable.

== See also ==
*[[Tree (set theory)]], generalization
*[[Ordinal number]]
*[[Well-founded set]]
*[[Well partial order]]
*[[Prewellordering]]
*[[Directed set]]

==References==

<references/>

{{refbegin}}
* {{cite book | last = Folland | first = Gerald B. | author-link = Gerald Folland
  | title = Real Analysis: Modern Techniques and Their Applications | edition = 2nd
  | publisher = [[John Wiley & Sons|Wiley]] | series = Pure and applied mathematics | year = 1999
  | isbn = 978-0-471-31716-6
  | pages = 4–6,&nbsp;9 |url=https://books.google.com/books?id=wI4fAwAAQBAJpg=PT18 <!-- Link from new edition -->}}
{{refend}}
* {{cite web |last1=Tao |first1=T |title=245B, Notes 7: Well-ordered sets, ordinals, and Zorn's lemma (optional) |url=https://terrytao.wordpress.com/2009/01/28/245b-notes-7-well-ordered-sets-ordinals-and-zorns-lemma-optional/ |website=What's new |language=en |date=28 January 2009}}
* {{cite book|first=Paul|last=Halmos|author-link=Paul Halmos|title=Naive set theory|location=Princeton, NJ|publisher=D. Van Nostrand Company|year=1960}}. Reprinted by Springer-Verlag, New York, 1974. {{ISBN|0-387-90092-6}} (Springer-Verlag edition).
* {{cite book |last1=Taylor |first1=Paul |title=Practical Foundations of Mathematics |date=13 May 1999 |publisher=Cambridge University Press |isbn=978-0-521-63107-5 |url=https://books.google.com/books?id=iSCqyNgzamcC&dq=Taylor+practical+foundations+of+mathematics+&pg=PR8 |language=en}} [https://ncatlab.org/nlab/show/Practical+Foundations+of+Mathematics]

== Further reading ==
* Paul Taylor, Towards a unified treatment of induction, I: the general recursion theorem (1996).
* Remark 2.5. in https://ncatlab.org/nlab/show/Zorn's+lemma

{{Order theory}}

[[Category:Order theory]]
[[Category:Ordinal numbers]]
[[Category:Wellfoundedness]]