wellordered

Wellordered is an adjective used in order theory to describe a property of a set with a specific type of ordering. A totally ordered set is wellordered if every nonempty subset has a least element under the given order.

Formally, a set S with a relation < is well-ordered if it is a total order and for every nonempty subset T ⊆ S, there exists an element t ∈ T such that t ≤ s for all s ∈ T. The least element condition is what distinguishes well-ordered sets from arbitrary totally ordered sets.

Key implications and concepts include that every well-ordered set has an order type, which is an ordinal. In fact, a set is well-ordered iff there exists an ordinal α and a order isomorphism between α and the set. Conversely, every ordinal is equipped with a natural well-order, namely its membership relation, making ordinals canonical examples of well-ordered sets.

Examples: The natural numbers N with the usual order are well-ordered. Finite sets are well-ordered under any total order that has a least element for every nonempty subset. The set of all integers Z with the standard order is not well-ordered, since the subset of negative integers has no least element.

Related results: The well-ordering principle states that every set can be well-ordered. This principle is equivalent to the axiom of choice. The concept underpins transfinite induction and recursion and is fundamental to ordinal arithmetic and the study of order types.

Terminology note: a set that can be well-ordered is called well-orderable; in systems without the axiom of choice, not all sets are guaranteed to be well-ordered.