Partial Orders

Reflexive, antisymmetric, transitive — comparability and Hasse diagrams.

The idea

A partial order is an ordering that need not compare every pair of elements. The relation $\le$ on the real numbers settles any two numbers one way or the other, but divisibility does not: one integer may divide another, or neither may divide the other. A partial order keeps the structural rules of an ordering while allowing such unsettled pairs.

A relation $\preceq$ on a set is a partial order when it is

- reflexive: $a \preceq a$ for every $a$; - antisymmetric: if $a \preceq b$ and $b \preceq a$ then $a = b$; - transitive: if $a \preceq b$ and $b \preceq c$ then $a \preceq c$.

A set carrying such an order is a poset. Two elements are comparable when one is $\preceq$ the other and incomparable when neither is; an order with no incomparable pairs is a total order.

A Hasse diagram pictures a poset. Draw $b$ above $a$ and join them when $b$ covers $a$ — that is, $a \preceq b$, the two are distinct, and nothing sits strictly between them. The pairs forced by reflexivity and transitivity are left off the page: $a \preceq b$ exactly when some upward path runs from $a$ to $b$.

Ways to work on it

• Walkthrough. Divisibility as a partial order; comparable vs incomparable.
• Practice. Decide whether two divisors are comparable.
• Hardest. Longest chain and largest antichain in a divisor poset.

Not sure where to start? Take the ten-question placement test.