Order Theory

Idea

Order theory is the study of binary relations that capture notions of comparison, precedence, or hierarchy. It provides a common language for mathematics, logic, and computer science, unifying concepts such as divisibility, containment, implication, and reachability under a single framework.

Basic Definitions

The central notion is that of a relation $\le :A\to A\to \mathrm{Prop}$ on a set $A$. The main classes of ordered structures are defined by which combination of properties $\le$ satisfies:

Structure	Reflexive	Transitive	Anti-symmetric	Total
Preorder	✓	✓
Partial Order	✓	✓	✓
Total order	✓	✓	✓	✓
Well-Ordering	✓	✓	✓	✓ + well-founded

Strict variants replace reflexivity with irreflexivity and anti-symmetry with asymmetry, giving strict partial orders ($<$) and strict total orders.

Key Concepts

• Reflexive Relation: $\forall x.x\le x$
• Transitive Relation: $\forall x,y,z.x\le y\to y\le z\to x\le z$
• Anti-Symmetric Relation: $\forall x,y.x\le y\to y\le x\to x=y$
• Totality: $\forall x,y.x\le y\vee y\le x$
• Well-foundedness: every non-empty subset has a minimal element

Constructions

Upper and Lower Bounds

Given a subset $S\subseteq A$ of a poset $(A,\le )$:

• $u\in A$ is an upper bound of $S$ iff $\forall s\in S.s\le u$
• $l\in A$ is a lower bound of $S$ iff $\forall s\in S.l\le s$
• The supremum (least upper bound) $\sup S$ is the smallest upper bound, if it exists
• The infimum (greatest lower bound) $\inf S$ is the largest lower bound, if it exists

Lattices

A partial order in which every finite subset has a supremum and infimum is a lattice. If every subset (including infinite ones) has a supremum and infimum, it is a complete lattice.

Monotone Maps

A function $f:A\to B$ between preordered sets is monotone (or order-preserving) iff $x{\le }_{A}y\Rightarrow f(x){\le }_{B}f(y).$ Monotone maps are the morphisms in the category of preorders; they correspond to functors between the associated thin categories.

Galois Connections

A Galois connection between posets $(A,{\le }_A)$ and $(B,{\le }_B)$ is a pair of monotone maps $f:A\to B$ and $g:B\to A$ satisfying $f(a){\le }_{B}b⟺a{\le }_{A}g(b).$ This is an adjunction between the corresponding thin categories. Galois connections arise throughout algebra (e.g. between subgroups and fixed fields in Galois theory) and logic (e.g. between syntax and semantics).

Ordinals and Cardinals

Ordinals are canonical representatives of well-ordered sets: every well-ordered set is order-isomorphic to a unique ordinal. Cardinals measure size up to bijection and are themselves represented as initial ordinals.

Ordinal arithmetic ($+$, $\cdot$, exponentiation) is defined by transfinite recursion and is not commutative: $1+\omega =\omega \ne \omega +1$.

Categorical Perspective

Every preorder $(A,\le )$ corresponds to a thin category with objects $A$ and a unique morphism $x\to y$ iff $x\le y$. Under this correspondence:

• monotone maps are functors
• Galois connections are adjunctions
• complete lattices are categories with all small limits and colimits

This makes order theory a special case of category theory, and many order-theoretic results are instances of general categorical theorems.

Related Concepts

• Partial Order
• Preorder
• Total Ordering
• Well-Ordering
• Well-founded Relation
• Complete Lattice
• Ordinal
• Cardinality
• Thin Category
• Predicate