Posets#
A partially ordered set [Pin14], often abbreviated as poset, is a mathematical structure that captures the idea of ordering elements in a way that some pairs of elements can be compared, but not necessarily all. Think of it like organizing items where some can be clearly ranked, but others might not be directly comparable.
Partial orders#
A partial order is a binary relation that captures the intuitive notion of one element being less than or equal to another element in a set. It is defined mathematically using specific properties.
Definition
Let \(P\) be a set and \(\leq\) be a endo-relation on \(P\). The relation \(\leq\) is a partial order on \(P\) if it satisfies the following properties:
- Reflexivity
Every element is related to itself.
- Antisymmetry
There are no distinct elements that relate to each other in both directions unless they are the same element.
- Transitivity
The relation is preserved across connected elements.
Properties
In a partial order, not all elements need to be comparable. There may exist elements \(a\) and \(b\) such that neither \(a \leq b\) nor \(b \leq a\).
If every pair of elements in the set is comparable, the partial order is called a total order or linear order.
A set equipped with a partial order is called a partially ordered set (poset).
Covering relations#
In the context of partially ordered sets (posets), the covering relation is an endo-relation that describes a direct or immediate predecessorship between elements.
Definition
Let \(\left\langle P, \leq\right\rangle\) be a poset, where \(P\) is a set and \(\leq\) is a partial order on \(P\).
An element \(a\) is said to be covered by another element \(b\) if:
Properties
If \(a\prec b\), then \(a\) is an immediate predecessor of \(b\), meaning there are no intermediate elements between \(a\) and \(b\) in the partial order.
In a Hasse diagram, which visually represents a poset, an edge directly connects \(a\) to \(b\) if and only if \(a\prec b\).
The covering relation helps identify minimal and maximal elements in a poset, as these elements do not have any elements covering them or being covered by them, respectively.