This article is part of a series on understanding different concepts in mathematics and computer science. In this post, we will explore the concept of order theory. The reason I started investigating this topic is because I watched a talk by Emily Riehl on A categorical view of computational effects, where she mentioned that “omega complete partial orders is a category relevant to computer science”. Also in another talk by Eugenia Cheng on Category Theory in Life, she mentioned that the factors of numbers like 30, 42, and 56 can be generalized and “fit together in the same cube structure which is otherwise known as a partially ordered set, but it’s also an example of a category with arrows as morphisms”. This intrigued me, and I wanted to learn more about order theory to be able to further understand more advanced topics.
Introduction#
Order theory is a branch of mathematics that studies the arrangement of elements in a certain order, defined by a binary relation that describes how elements compare to each other. It encompasses various types of orders, such as partial orders, total orders, well orders, lattices, etc. each defined by specific properties that the relations must satisfy. The relationships between elements of a set provides a framework for reasoning about the structure of ordered sets. Order theory is used in various fields, such as set theory, category theory, and computer science, to model data structures, algorithms, scheduling tasks, and computational effects in programming languages for example. It essentially lays the foundation for understanding more advanced topics in mathematics and computer science.12 This article provides a brief introduction and exploration of the key concepts and applications in order theory.
Fundamental Concepts#
To fully understand order theory, it is essential to grasp the fundamental concepts, terminologies and diagram notations that underpin the theory.
Partial Orders#
Partial orders are used to model relationships between elements of a set.
A partially ordered set (or poset for short) described an ordered pair \(P = (X, \leq)\) consisting of a set \(X\) (called the ground set of \(P\)) and a partial order relation \(\leq\) on \(X\).34 The names \(X\) and \(P\) where arbitrarily chosen, and the symbol \(\leq\) is commonly used to denote a partial order relation. Often there also exist a minimum element \(\exists m \in X\) such that: \(\forall a \in X\), \(m \leq a\).
There are two types of partial orders: weak partial orders and strong partial orders. In a weak, reflexive, non-strict partial order, or simply a regular partial order, the relation \(\leq\) is a binary relation on \(X\).34 In a strong, irreflexive, or strict partial order, the relation \(<\) is a binary relation on \(X\) that satisfying the properties:543
| \(\forall a, b \in X\) | Weak Partial Order | \(\forall a, b \in X\) | Strong Partial Order |
|---|---|---|---|
| Reflexivity | \(a \leq a\) | Irreflexivity | \(a \nless a\) |
| Antisymmetry | \(a \leq b \land b \leq a \newline \implies a = b\) | Asymmetry | \(a < b \newline \implies b \nless a\) |
| Transitivity | \(a \leq b \land b \leq c \newline \implies a \leq c\) | Transitivity | \(a < b \land b < c \newline \implies a < c\) |
Total Orders#
Preorders#
Complete Partial Orders#
Chains#
Lattices#
Cover Relations#
Hasse Diagrams#
Notation#
Examples#
Properties#
Applications#
Advanced Topics#
Conclusion#
“Order Theory”, https://en.wikipedia.org/wiki/Order_theory. ↩︎
“List of Order Theory Topics”, https://en.wikipedia.org/wiki/List_of_order_theory_topics. ↩︎
“Partially Ordered Set”, https://en.wikipedia.org/wiki/Partially_ordered_set. ↩︎ ↩︎ ↩︎
“Partial Order”, https://mathworld.wolfram.com/PartialOrder.html ↩︎ ↩︎ ↩︎
“Strict Partial Order”, https://en.wikipedia.org/wiki/Strict_partial_order. ↩︎