Partial Orders

What this lesson covers

This lesson introduces partial orders: the mathematical structure that captures the idea of “this thing is at least as much as that thing” in a consistent way. By the end, you will be able to identify when a relation is a partial order, draw its Hasse diagram, and explain why partial orders matter for the structures that follow (lattices, Heyting algebras, closure operators).

Why it matters

Suppose you are organizing a library. You could sort books alphabetically — a total order where every pair of books has a definite ranking. But suppose instead you want to organize by topic. Introduction to Logic is more specific than Mathematics, and Modal Logic is more specific than Introduction to Logic. But how does Modal Logic compare to Set Theory? They are both more specific than Mathematics, but neither is more specific than the other. They are incomparable.

This is the situation partial orders handle. Unlike total orders (where everything is comparable), partial orders allow incomparability. The set of topics forms a partial order under “is more specific than,” and some pairs simply have no ranking. This turns out to be exactly the right structure for organizing knowledge — and for the mathematical frameworks (Heyting algebras, closure operators) that formalize reasoning about meaning and structure.

Prerequisites

None. This lesson assumes familiarity with sets and basic logical notation ($\forall$, $\Rightarrow$) but no prior exposure to order theory.

Core concepts

Relations on a set

A relation $R$ on a set $S$ is a collection of ordered pairs from $S$. We write $aRb$ (or $aRb$) to mean the pair $(a,b)$ is in the relation. For order relations, we write $a\le b$.

Example. Let $S=\{1,2,3\}$ and let $\le$ be the usual “less than or equal to” on numbers. Then $1\le 2$ and $2\le 3$ and $1\le 1$, but $3\le 1$ does not hold.

The three axioms

A relation $\le$ on a set $S$ is a partial order when it satisfies three properties:

1. Reflexive: $a\le a$ for every $a\in S$. Every element is related to itself. This is the minimum requirement for the relation to be consistent — a thing is at least as much as itself.

2. Antisymmetric: if $a\le b$ and $b\le a$, then $a=b$. The only way two elements can be mutually related is if they are the same element. This prevents cycles (other than self-loops).

3. Transitive: if $a\le b$ and $b\le c$, then $a\le c$. Chains of comparisons compose. If $a$ is below $b$ and $b$ is below $c$, then $a$ is below $c$.

A set $S$ together with a partial order $\le$ on it is called a partially ordered set, or poset, written $(S,\le )$.

Preorders: the weaker cousin

If you drop antisymmetry but keep reflexivity and transitivity, you get a preorder. In a preorder, two distinct elements can satisfy $a\le b$ and $b\le a$ without being equal. Preorders arise when you have a notion of “at least as good as” where ties are possible — like ranking restaurants where two can be equivalently good.

Every partial order is a preorder, but not every preorder is a partial order. The distinction matters: partial orders give clean hierarchies; preorders allow equivalence classes.

Comparability and incomparability

Two elements $a,b$ in a poset are comparable if $a\le b$ or $b\le a$. They are incomparable otherwise.

A total order (or linear order) is a partial order where every pair is comparable. The integers under $\le$ form a total order. The subsets of $\{x,y\}$ under inclusion do not: $\{x\}$ and $\{y\}$ are incomparable.

Hasse diagrams

A Hasse diagram is a visual representation of a poset. Elements are drawn as dots. If $a<b$ and there is no element $c$ with $a<c<b$ (that is, $b$ covers $a$), you draw a line from $a$ up to $b$. The diagram shows the “skeleton” of the order — all other comparisons can be deduced from transitivity.

Example. The divisibility order on $\{1,2,3,6\}$ (where $a\le b$ means $a$ divides $b$):

    6
   / \
  2   3
   \ /
    1

From this diagram you can read off: $1\le 2$, $1\le 3$, $1\le 6$, $2\le 6$, $3\le 6$. And $2$ and $3$ are incomparable — neither divides the other.

Worked example: the power set

Let $X=\{a,b\}$. The power set $\mathcal{P}(X)=\{\varnothing ,\{a\},\{b\},\{a,b\}\}$ is the set of all subsets of $X$. Define $A\le B$ iff $A\subseteq B$ (every element of $A$ is also in $B$).

Check the axioms:

1. Reflexive: $A\subseteq A$ for every set $A$. ✓
2. Antisymmetric: If $A\subseteq B$ and $B\subseteq A$, then $A=B$. ✓
3. Transitive: If $A\subseteq B$ and $B\subseteq C$, then $A\subseteq C$. ✓

So $(\mathcal{P}(X),\subseteq )$ is a poset. Its Hasse diagram:

   {a,b}
   /   \
 {a}   {b}
   \   /
    ∅

Note that $\{a\}$ and $\{b\}$ are incomparable — neither is a subset of the other. This is what makes it a partial order rather than a total order.

This poset will reappear in the next lesson as a lattice, and then again as a Heyting algebra. The power set is the running example throughout this sequence.

Check your understanding

1. Is the "is ancestor of" relation on people a partial order?

It is reflexive (everyone is their own ancestor, by convention) and transitive (an ancestor of an ancestor is an ancestor). Is it antisymmetric? If person A is an ancestor of person B and B is an ancestor of A, are they the same person? Yes — ancestry cannot cycle (setting aside the reflexive case). So it is a partial order. But it is not total: two cousins are incomparable.

2. Let $S = \{1, 2, 3, 4, 5, 6\}$ with the divisibility order ($a \leq b$ iff $a$ divides $b$). Are 2 and 3 comparable? Are 4 and 6 comparable?

$2$ and $3$ are incomparable: $2$ does not divide $3$, and $3$ does not divide $2$. $4$ and $6$ are also incomparable: $4$ does not divide $6$, and $6$ does not divide $4$. (This surprises people who expect the divisibility order to be total — it is not.)

3. What goes wrong if you try to define a "preference" order where Alice prefers coffee to tea, tea to juice, and juice to coffee?

This is not a partial order because it violates transitivity (or rather, transitivity combined with antisymmetry produces a contradiction). We have coffee $\le$ tea $\le$ juice $\le$ coffee, which by transitivity gives coffee $\le$ coffee (fine, reflexivity), but also coffee $\le$ tea and tea $\le$ juice $\le$ coffee, so tea $\le$ coffee and coffee $\le$ tea, which by antisymmetry means coffee = tea. The cycle collapses the order. This is why partial orders cannot have cycles — and why cyclic preferences require a different mathematical structure.

Common mistakes

• Assuming every order is total. The most common error. In a poset, two elements may simply be incomparable — this is not a defect, it is the point.
• Confusing antisymmetry with asymmetry. Antisymmetry says: if $a\le b$ and $b\le a$, then $a=b$. It does not say that $a\le b$ implies $b\nleqq a$. (That would be asymmetry, which holds for strict orders like $<$ but not for $\le$.)
• Forgetting reflexivity. The relation $<$ (strict less than) on numbers is transitive and antisymmetric, but not reflexive. It is a strict partial order, not a partial order. To get a partial order, use $\le$.

What comes next

The next lesson, Lattices, adds structure to partial orders by requiring that every pair of elements has a meet (greatest lower bound) and a join (least upper bound). The power set example already has this structure — intersection is the meet and union is the join. Lattices are the foundation for Heyting Algebras, which add implication, and for closure operators, which formalize the idea of completing or stabilizing a structure.