flowchart TB
a o--o c
a o--o e
b o--o c
b o--o d
b o--o e
d o--o eflowchart TB
a o--o c
a o--o e
b o--o c
b o--o d
b o--o e
d o--o e
Fundamentals
This section provides an overview of some fundamental concepts in order theory.
Essential Definitions and Examples
Definition
A partial order is a pair \((X, \leq)\) composed of a set \(X\) called the ground set and \(\leq\) is a binary relation with the following properties: - reflexivity: \(x \leq x\ \forall x \in X\) - transitivity: \(x \leq y \land y \leq z \implies x \leq z\ \forall x,y,z \in X\) - antisymmetry: \(x \leq y \land y \leq x \implies x = y\ \forall x,y \in X\)
Let us consider an example of a partial order and some of the ways we can represent them.
Example
Let \(X = \{a, b, c, d, e \}\), then we might have a partial order \(\\{(a,a), (a,c), (a,e), (b,b), (b,c), (b,d), (b,e), (c,c), (d,d), (d,e), (e,e)\\}\). This partial order can be represented as a matrix.
\[\begin{array}{c c} & \begin{array}{c c c c c} a & b & c & d & e \\ \end{array} \\ \begin{array}{c c c c c} a \\ b \\ c \\ d \\ e \\ \end{array} & \left[ \begin{array}{c c c c c} 1 & 0 & 1 & 0 & 1 \\ & 1 & 1 & 1 & 1 \\ & & 1 & 0 & 0 \\ & \huge 0 & & 1 & 1 \\ & & & & 1 \\ \end{array} \right] \end{array} \]
Another representation is a directed graph (AKA a digraph):
"""The example partial order from the notes and its digraph representation.
The ground set is ``X = {a, b, c, d, e}`` and the relation is
{(a, a), (a, c), (a, e), (b, b), (b, c), (b, d), (b, e),
(c, c), (d, d), (d, e), (e, e)}.
Because the relation is reflexive it includes the five self-pairs, which the
digraph draws as self-loops.
"""
from __future__ import annotations
import warnings
from pathlib import Path
import matplotlib.pyplot as plt
import networkx as nx
EXAMPLE_ORDER: list[str] = [
"aa",
"ac",
"ae",
"bb",
"bc",
"bd",
"be",
"cc",
"dd",
"de",
"ee",
]
"""The example relation, with each ordered pair written as a two-character string."""
def build_digraph(order: list[str] | None = None) -> nx.DiGraph:
"""Build the directed-graph representation of a partial order.
``order`` is a list of two-character strings, each the head and tail of an
ordered pair. It defaults to :data:`EXAMPLE_ORDER`.
"""
graph = nx.DiGraph()
for pair in order if order is not None else EXAMPLE_ORDER:
graph.add_edge(pair[0], pair[1])
return graph
def plot_example_partial_order(
output: str | Path = "figures/example_partial_order.png",
) -> Path:
"""Draw the digraph of the example partial order and save it.
Parameters
----------
output : str or pathlib.Path
Destination of the rendered PNG. Parent directories are created.
Returns
-------
pathlib.Path
The path that was written.
"""
graph = build_digraph()
pos = nx.spring_layout(graph, seed=2018)
fig, ax = plt.subplots()
with warnings.catch_warnings():
warnings.filterwarnings("ignore")
nx.draw(
graph,
pos=pos,
labels={node: node for node in graph.nodes()},
node_color=(0.5,) * 3,
with_labels=True,
arrows=True,
ax=ax,
)
output_path = Path(output)
output_path.parent.mkdir(parents=True, exist_ok=True)
fig.savefig(output_path, dpi=300, bbox_inches="tight")
plt.close(fig)
return output_path
def main() -> None:
"""Console-script entry point: draw the example digraph."""
plot_example_partial_order()
if __name__ == "__main__":
main()
Tip
The previous example only required a relatively small subset of the Cartesian product \(X \times X\). When you have too many elements in \(X\) to deal with by hand, one quick Python script to make the pairs in a format suitable for \(\LaTeX\) is the following:
"""Format every ordered pair of a finite set for use in LaTeX.
For a ground set ``X`` the full Cartesian product ``X x X`` has ``|X|**2``
ordered pairs, which is tedious to write out by hand. This module generates
them and renders the set in LaTeX set-builder syntax.
"""
from __future__ import annotations
from collections.abc import Iterable
from itertools import product
def latex_pairs(elements: Iterable[str]) -> str:
"""Return the LaTeX source for every ordered pair of ``elements``.
The result is a single line such as
``\\{(a, a), (a, b), ..., (e, e)\\}`` with the escape sequences needed to
typeset the curly braces in LaTeX.
Parameters
----------
elements : iterable of str
The ground set, e.g. ``("a", "b", "c", "d", "e")``.
Returns
-------
str
LaTeX set notation for ``X x X``.
"""
pairs = ["(" + ", ".join(pair) + ")" for pair in product(elements, elements)]
pairs = sorted(pairs)
text = str(pairs).replace("'", "")
text = text.replace("[", "\\\\{")
text = text.replace("]", "\\\\}")
return text
def main() -> None:
"""Console-script entry point: print the pairs for ``{a, b, c, d, e}``."""
print(latex_pairs(("a", "b", "c", "d", "e")))
if __name__ == "__main__":
main()\\{(a, a), (a, b), (a, c), (a, d), (a, e), (b, a), (b, b), (b, c), (b, d), (b, e), (c, a), (c, b), (c, c), (c, d), (c, e), (d, a), (d, b), (d, c), (d, d), (d, e), (e, a), (e, b), (e, c), (e, d), (e, e)\\}Definition
A strict partial order is a pair \((X, <)\) composed of a set \(X\) called the ground set and \(<\) is a binary relation with the following properties: - transitivity: \(x < y \land y < z \implies x < z\ \forall x,y,z \in X\) - asymmetry: \(\lnot (x < y \land y < x) \ \forall x,y \in X\)
Proposition
The digraph representation of a strict order is a directed acyclic graph (DAG).
Often we can start with a strict order and derive similar results for a corresponding (non-strict) partial order.
Definition
\(\{x, y\}\) are a comparable pair if \(x < y \lor y > x\), denoted \(x \sim y\).
Definition
A graph \(G = (V, E)\) whose edge set \(E\) is the set of comparable pairs of a partial order is called the comparability graph.
Example
Suppose we have the strict partial order \(\\{(a,c), (a,e), (b,c), (b,d), (b,e), (d,e)\\}\), then its comparability graph would look like:
Definition
\(\{x, y\}\) are an incomparable pair if \(\lnot (x < y \lor y > x)\), denoted \(x \parallel y\).
Definition
A graph \(G = (V, E)\) whose edge set \(E\) is the set of incomparable pairs of a partial order is called the incomparability graph.
Example Suppose we have the strict partial order \(\\{(a,c), (a,e), (b,c), (b,d), (b,e), (d,e)\\}\), then its incomparability graph (AKA cocomparability graph) would look like:
flowchart TB
a o--o b
a o--o d
c o--o d
c o--o eflowchart TB
a o--o b
a o--o d
c o--o d
c o--o e
Proposition
The edge set of an incomparability graph is the complement of the edge set of the comparability graph.
Definition
A cover relation \(x \prec y\) is satisfied when \(x < y\) and there does not exist \(z\) such that \(x < z < y\).
Definition
A graph \(G = (V, E)\) is a cover graph when its edge set \(E\) is a collection of pairs satisfying a cover relation.
Example Suppose we have the strict partial order \(\\{(a,c), (a,e), (b,c), (b,d), (b,e), (d,e)\\}\), then its cover graph would look like:
flowchart TB
a o--o c
a o--o e
b o--o c
b o--o d
d o--o eflowchart TB
a o--o c
a o--o e
b o--o c
b o--o d
d o--o e
Definition
A directed graph \(D = (V, E)\) is a directed cover graph when its edge set \(E\) is a collection of pairs satisfying a cover relation and the order of the pairs is represented with arcs.
Example
Suppose we have the strict partial order \(\\{(a,c), (a,e), (b,c), (b,d), (b,e), (d,e)\\}\), then its directed cover graph would look like:
flowchart TB
e --> a
e --> d
c --> a
c --> b
d --> bflowchart TB
e --> a
e --> d
c --> a
c --> b
d --> b
Definition
A cover diagram is a drawing of the directed graph representing a cover relation such that the edges are cover pairs \((x,y)\). Edges are drawn in such a way that \(x\) is below \(y\) (in the graph embedding) and the edge is \(y\)-monotone.
Example
Suppose we have the strict partial order \(\\{(a,c), (a,e), (b,c), (b,d), (b,e), (d,e)\\}\), then its cover diagram would look like:
"""The cover diagram of the example strict partial order.
The strict partial order is
{(a, c), (a, e), (b, c), (b, d), (b, e), (d, e)}.
Its cover relation drops ``(b, e)`` because ``b < d < e``, leaving the edges
``a-c``, ``a-e``, ``b-c``, ``b-d`` and ``d-e``. The nodes are laid out so that
each cover edge goes upward, which is what makes the drawing a cover diagram.
"""
from __future__ import annotations
import warnings
from pathlib import Path
import matplotlib.pyplot as plt
import networkx as nx
COVER_POSITIONS: dict[str, tuple[float, float]] = {
"a": (0.0, 1.0),
"b": (1.0, 0.0),
"c": (0.0, 3.0),
"d": (2.0, 2.0),
"e": (1.0, 4.0),
}
"""Fixed node positions: drawing an edge moves strictly upwards."""
COVER_EDGES: list[tuple[str, str]] = [
("a", "c"),
("a", "e"),
("b", "c"),
("b", "d"),
("d", "e"),
]
"""The cover pairs of the example strict partial order."""
def build_cover_graph(edges: list[tuple[str, str]] | None = None) -> nx.Graph:
"""Build the (undirected) cover graph of the example partial order."""
graph = nx.Graph()
graph.add_edges_from(edges if edges is not None else COVER_EDGES)
return graph
def plot_cover_diagram(
output: str | Path = "figures/cover_diagram.png",
) -> Path:
"""Draw the cover diagram of the example partial order and save it.
Parameters
----------
output : str or pathlib.Path
Destination of the rendered PNG. Parent directories are created.
Returns
-------
pathlib.Path
The path that was written.
"""
graph = build_cover_graph()
fig, ax = plt.subplots()
with warnings.catch_warnings():
warnings.filterwarnings("ignore")
nx.draw(
graph,
pos=COVER_POSITIONS,
labels={node: node for node in graph.nodes()},
node_color=(0.5,) * 3,
with_labels=True,
ax=ax,
)
output_path = Path(output)
output_path.parent.mkdir(parents=True, exist_ok=True)
fig.savefig(output_path, dpi=300, bbox_inches="tight")
plt.close(fig)
return output_path
def main() -> None:
"""Console-script entry point: draw the cover diagram."""
plot_cover_diagram()
if __name__ == "__main__":
main()
Special Classes of Orders
- linear orders (aka total orders, aka chains).
- Important in computer science problems such as sorting.
- Important in mathematics for defining sets of numbers such as \(\mathbb{N}\), \(\mathbb{Z}\), \(\mathbb{R}\) and others.
- Boolean lattices
- \(B_n = (2^{[n]}, \subseteq )\) where \[[n] = \{ 1, \ldots, n \}\]
- Looks at subsets of \(n\) ordered by inclusion
Proposition
The subset relation on any family of sets is an order relation.
Example
Intervals, discs, balls, subtrees, subgraphs, subgroups are all included sets under the order relation of set inclusion.
Definition
A containment relation is […]
Definition
For \(A \subseteq X\) we have the down-set of \(A\) being \[D[A] = \bigcup_{a \in A} D[a] = \{ x | \exists a \in A\ \text{s.t.}\ x \leq a \}\].
Proposition
Every finite order is the containment order of a family of sets.
Proof Let \(P = (X, \leq)\) be an order relation.
For \(a \in X\) let \(D[a] = \{ x : x \leq a \}\) be the down-set of a.
Let \[y = \{ D[a] : a \in X \}\].
Now we claim that \(P \cong (y, \subseteq )\) where \(\cong\) is an order-preserving isomorphism.
Since isomorphisms are bijections, we take the bijection in this case to \(D : x \mapsto D[x]\).
We need to verify that \(D\) as we have just defined it is actually a bijection.
If a mapping is a bijection, then it is both injective and surjective.
Considering the injective case, let take two elements \(x\) and \(y\) such that \(x \neq y\) then there are three possibilities: - \(x < y \implies y \not\in D[x]\) - \(x > y \implies x \not\in D[y]\) - \(x \parallel y\) (i.e. \(x\) and \(y\) are not comparable in the order) which implies \((y \not\in D[x]) \land (x \not\in D[y])\)
Surjectivity is given by definition of \(D\).
And we have that \(D\) is order-preserving in the sense that \(x \leq y \iff D[x] \subseteq D[y]\). \[\blacksquare\]
Definition
A lower bound of a subset \(S\) of partially ordered set \((P, \leq)\) is an element \(a \in P\) such that \(a \leq x \forall x \in S\).
Definition
A lower bound \(a \in S\) is called an infimum (or greatest lower bound, or meet) of \(S\) if for all lower bounds \(y \in S\) we have \(y \leq a\).
Definition
An upper bound of a subset \(S\) of partially ordered set \((P, \leq)\) is an element \(b \in P\) such that \(b \geq x \forall x \in S\).
Definition
An upper bound \(b\) of \(S\) is called a supremum (or least upper bound, or join) of \(S\) if for all upper bounds \(z \in S\) we have \(z \leq b\).
Definition
A finite poset on \(S\) is a lattice if every subset of \(S\) has a unique least upper bound (aka join or supremum) denoted \(\lor\) and a unique greatest lower bound (aka meet or infimum) denoted \(\land\).
Definition
The down-set lattice of \(P\) given by \[D(P) = (\{ D[A] : A \subset X \}, \subseteq)\].
Definition
A lattice \((L, \lor, \land)\) is distributive if the following identity holds for all \(x,y,z \in L\):
\[x \land (y \lor z) = (x \land y) \lor (x \land z)\]
where \(\land\) and \(\lor\) are the meet and join operations.
Proposition
The down-set lattice of \(P\) is a distributive lattice.
Proof (Hint) Take \(\lor\) to be \(\cup\) and \(\land\) to be \(\cap\).
Definition
\(Q = (Y, \leq_Q )\) is a subposet of \(P = (X, \leq_P)\) if \(Y \subseteq X\) and \((\leq_Q) = (\leq_P) \cap (Y \times Y)\).