Ordering Relations

Why study orderings as their own structure? Because the moment a set has an "is below" relation that is consistent (reflexive, antisymmetric, transitive), you can ask sorting-style questions: what is the smallest, the largest, the next-up, the next-down. Real systems are full of such orderings — the integers under $\leq$, the subsets of a set under $\subseteq$, software versions under "depends on," tasks under "must finish before," even git commits under "is ancestor of." Some of these are total (every pair is comparable, like real numbers) and some are partial (some pairs are incomparable, like ${1}$ and ${2}$ under $\subseteq$). Distinguishing the two is the heart of this section.

Partial orders

A relation $R$ on $A$ is a partial order if it is reflexive, antisymmetric, and transitive. We usually write $\leq$ or $\preceq$ for a partial order, and the pair $(A, \leq)$ is called a partially ordered set (or poset). Familiar examples: $(\mathbb{R}, \leq)$, $(\mathbb{Z}^+, \mid)$, $(\mathcal{P}(X), \subseteq)$.

Total orders

A partial order is a total order (or linear order) when every two elements are comparable: $\forall a, b \in A,, a \leq b \vee b \leq a$. The real line and the natural numbers under $\leq$ are total. The divisibility poset $(\mathbb{Z}^+, \mid)$ is not total because, for example, $2 \nmid 3$ and $3 \nmid 2$.

Special elements

Let $(A, \leq)$ be a poset and $a \in A$:

• Minimal: no element $b \neq a$ satisfies $b \leq a$. Nothing is strictly below $a$.
• Maximal: no element $b \neq a$ satisfies $a \leq b$. Nothing is strictly above $a$.
• Least: $a \leq b$ for every $b \in A$. (At most one.)
• Greatest: $b \leq a$ for every $b \in A$. (At most one.)

Every least element is minimal, but a minimal element need not be least. In $({2, 3}, \mid)$, both $2$ and $3$ are minimal — nothing in the set divides either of them — yet neither is least because they are incomparable.

Hasse diagrams

A Hasse diagram is a picture of a finite poset: draw an element $a$ above $b$ when $b \leq a$, and connect them with a line only when $a$ covers $b$ — meaning $b < a$ and no element $c$ exists with $b < c < a$ (nothing sits strictly between in the order). Reflexive self-loops and transitivity edges are omitted because they are implied. The result is a clean directed-up graph that exposes the order’s structure at a glance.

(Use the dropdown to switch posets: divisibility on ${1, 2, 3, 4, 6, 12}$, the subset lattice on $\mathcal{P}({a, b, c})$, divisibility on ${1, 2, 3, 5, 6, 10}$, or a total order on ${1, \ldots, 6}$. Click any node to highlight its strict predecessors (green) and successors (accent).)

Pause and think: In the divisibility poset on ${2, 3, 5, 30}$, what are the minimal elements? The maximal elements? Is there a least element? A greatest? Sketch the Hasse diagram on paper before answering.

Try it

• Verify that $(\mathcal{P}({a, b, c}), \subseteq)$ is a partial order. Is it total? If not, give two incomparable elements.
• Sketch the Hasse diagram for divisibility on ${1, 2, 3, 6, 12}$.
• Predict: in any finite poset with a unique minimal element, must that element be the least? Justify.
• Find two incomparable elements in $({1, 2, 3, 4, 6, 12}, \mid)$.
• Prove: in a total order, every nonempty finite subset has a least element. (Induction on the size of the subset.)

A trap to watch for

"Minimal" and "least" are not synonyms. A minimal element $a$ has nothing strictly below it — but other incomparable elements may exist at the same level. A least element is below everything — so it is the unique minimum. In a total order they coincide; in a partial order they may not. Same warning applies to maximal vs. greatest.

What you now know

You can recognise a partial order from its three defining properties, distinguish partial from total, locate minimal/maximal/least/greatest elements, and draw a Hasse diagram for any small finite poset. Section 4.5 swaps "antisymmetric" for "symmetric" and produces an entirely different (and equally fundamental) kind of relation: the equivalence relation.

References

• Velleman, D. J. (2019). How to Prove It (3rd ed.). Cambridge University Press, §4.4.
• Davey, B. A., Priestley, H. A. (2002). Introduction to Lattices and Order (2nd ed.). Cambridge University Press, ch. 1.
• Hammack, R. (2018). Book of Proof, ch. 11.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press, §22.4 (topological sort).