Editing Well-order (section)

{{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).