Order theory
Order theory studies how elements are arranged by a relation such as “less than,” “more general than,” or “is a subtype of.”
Specialization Orders and Subsumption
Lattices, Meet, Join, and Disjointness
Subtyping, Description Logic, and OWL
Partial Orders
A partial order on a set $P$ is a relation $\leq$ that is:
- Reflexive: $a \leq a$
- Antisymmetric: $a \leq b$ and $b \leq a$ implies $a = b$
- Transitive: $a \leq b$ and $b \leq c$ implies $a \leq c$
The pair $(P,\leq)$ is called a poset.
Core Concepts
- Comparable: $a \leq b$ or $b \leq a$
- Incomparable: neither $a \leq b$ nor $b \leq a$
- Top element $\top$: every element is below it
- Bottom element $\bot$: it is below every element
- Strict order: $a < b$ means $a \leq b$ and $a \neq b$
- Cover relation: $a$ covers $b$ if $b < a$ with nothing strictly between
Lattices
A lattice is a poset where every pair $(a,b)$ has:
- Meet $a \wedge b$ (greatest lower bound)
- Join $a \vee b$ (least upper bound)
Common use:
- meet for compatibility/intersection
- join for common abstraction/generalization
Hasse Diagrams
A Hasse diagram draws only cover relations and omits transitive edges, making order structure easier to read.
Connection to Category Theory
Every poset defines a category:
- objects are elements of the poset
- there is one morphism $a \to b$ exactly when $a \leq b$
So order theory provides one of the most important classes of categories.
See: