Orderings

An ordering on a set is a binary relation that allows the comparison of elements in a way that reflects a notion of size or position. In many contexts this relation is denoted ≤ and is designed to be reflexive, antisymmetric, and transitive, making it a partial order. If, in addition, every pair of elements is comparable (for any a and b, either a ≤ b or b ≤ a), the order is total or linear. A well-order is a total order with the stronger property that every nonempty subset has a least element.

Key concepts include the distinction between partial orders and total orders. A poset is a set equipped with a partial order. Total orders enable straightforward ranking of all elements, while partial orders allow comparisons only for some pairs. A strict order, such as <, is irreflexive and transitive and relates to a non-strict order by a ≤ b if and only if a < b or a = b.

Examples illustrate these notions. The natural numbers with the usual ≤ form a total order. The real numbers with ≤ also form a total order. The power set of a given set, ordered by subset inclusion ⊆, forms a partial order but not a total order in general. The divisibility relation | on positive integers is another partial order.

Additional structure arises in lattices, where any two elements have a least upper bound (join) and a greatest lower bound (meet). Monotone functions preserve order, and order isomorphisms preserve the entire order structure between sets.

In set theory, the well-ordering theorem (equivalent to the axiom of choice) asserts that every set can be well-ordered. Orderings underpin sorting, data structures, scheduling, and the formal study of preferences and proofs.