Definition. Well-order (well ordering) [002k]

November 26, 2025

Given a poset \((X, \leq )\), we say that the relation \(\leq \) is a well-order and that \(X\) is well-ordered by \(\leq \) iff. every non-empty subset \(S \subseteq X\) has a least element; that is, there exists an element \(m \in S\) such that for all \(s \in S\), \(m \leq s\). So, formally we have: (1)

\[ \forall (S : \mathcal {P}(X)).\ S \ \mathrlap {\,/}{=}\ \emptyset \implies (\exists m \in S.\ \forall s \in S.\ m \leq s) \]

When X is nonempty, if we pick out any two-element subset, \(\{a, b\}\) of \(X\), since the subset must have a least element, either \(a \leq b\) or \(b \leq a\). Thus, a well-order is a total order.

References

Reference. Chapter 5: Partial Orders, Lattices, Well-Founded Orderings, Equivalence Relations, Distributive Lattices, Boolean Algebras, Heyting Algebras [gallier-cis160-chapter5]

Gallier, Jean
University of Pennsylvania
https://www.seas.upenn.edu/~jean/cis160/cis260slides7.pdf

Definition. Partial order [002d]

November 25, 2025

Remarks

November 25, 2025


    some piece of code

A partial order is just a preorder with an additional property called antisymmetry. A partial order on a set \(P\) is a binary relation \(\leq \) that satisfies the following three properties for all elements \(a, b, c \in P\):

\(a \leq a\) (Reflexivity): Every element is related to itself.
\(a \leq b \land b \leq c \to a \leq c\) (Transitivity): If an element \(a\) is related to \(b\), and \(b\) is related to \(c\), then \(a\) is also related to \(c\).
\(a \leq b \land b \leq a \to a = b\) (Antisymmetry): If an element \(a\) is related to \(b\), and \(b\) is related to \(a\), then \(a\) and \(b\) must be the same element.

More accurately a partial order is a reflexive, weak, non-strict partial order. Also known as skeletal preorder. [0]