Skip to content
Tutorials Center
My learning

Topics

Lesson 17 of 38 ยท Equivalence and Order

Partial Orders and Hasse Diagrams

Learn partial and total orders, posets, comparable elements and Hasse diagrams, with examples from divisibility and subsets, plus Python code.

Equivalence relations say "same as". Order relations say "comes before" or "is at most". You already know the usual order of numbers, where any two numbers can be compared. But many real orderings are less complete: a folder is inside another folder, one task must be done before another, one set is contained in another. For these situations mathematics uses partial orders.

Definition

A relation โ‰ผ on a set A is a partial order if it is

  1. reflexive: a โ‰ผ a,
  2. antisymmetric: a โ‰ผ b and b โ‰ผ a imply a = b,
  3. transitive: a โ‰ผ b and b โ‰ผ c imply a โ‰ผ c.

A set together with a partial order is called a partially ordered set, or poset, written (A, โ‰ผ). Compare with equivalence relations: the only change is that symmetry is replaced by antisymmetry.

Examples

Poset Order
(โ„, โ‰ค) the usual order of numbers
(โ„•โบ, |) a | b means "a divides b"
(P(X), โІ) subset inclusion on the power set of X
words in a dictionary lexicographic (alphabetical) order
tasks "must be finished before" (after taking reflexive closure)

(The vertical bar \| above is the "divides" symbol.)

Comparable and incomparable

Two elements a and b are comparable if a โ‰ผ b or b โ‰ผ a. Otherwise they are incomparable. In (โ„•โบ, |), 2 and 3 are incomparable since neither divides the other, while 2 and 6 are comparable. In (P({1, 2}), โІ), the sets and are incomparable.

A partial order in which every two elements are comparable is a total order (or linear order or chain). (โ„, โ‰ค) is total. The divisibility order is not.

Strict orders

Given โ‰ผ, the strict order is a โ‰บ b meaning a โ‰ผ b and a โ‰  b. It is irreflexive and transitive. For โ‰ค we get <; for โІ, proper subset โŠŠ.

Hasse diagrams

A partial order on a finite set can contain many pairs, and most are consequences of others by transitivity and reflexivity. A Hasse diagram draws only the essential information:

  • Each element is a point.
  • Draw a line from a up to b when a โ‰บ b and there is no element strictly between them (we say b covers a).
  • Do not draw loops, and do not draw lines implied by transitivity.
  • Smaller elements go lower on the page, so arrows are not needed.

For divisibility on {1, 2, 3, 4, 6, 12}:

flowchart BT
    n1["1"] --> n2["2"]
    n1 --> n3["3"]
    n2 --> n4["4"]
    n2 --> n6["6"]
    n3 --> n6
    n4 --> n12["12"]
    n6 --> n12

Hasse diagram of divisibility on the divisors of 12. Read upward: 1 divides 2, 2 divides 6, and so on. The line from 1 to 4 is not drawn because 2 sits between them.

For the subsets of {a, b} ordered by โІ, the Hasse diagram is a diamond: โˆ… at the bottom, and side by side, and {a, b} on top. For three elements, it is a cube.

Python Check a poset and compute its Hasse diagram

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Drawing your own Hasse diagram

Here is a procedure that always works:

  1. List all pairs a โ‰บ b.
  2. Remove any pair that is implied by a chain a โ‰บ c โ‰บ b.
  3. Arrange elements in levels: minimal elements at the bottom, and every cover line going upward.

Linear extensions (topological sorting)

A partial order can be extended to a total order that respects it. If tasks have prerequisites, a topological sort produces a valid order to carry them out. For example, "wake up โ‰บ breakfast", "breakfast โ‰บ brush teeth", "wake up โ‰บ shower" admits several valid sequences, because "breakfast" and "shower" are incomparable.

Python A topological sort of a poset

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. A partial order is reflexive, transitive and:

    Replacing symmetry by antisymmetry turns the equivalence-relation recipe into the partial-order recipe.
  2. 2. In (โ„•โบ, divides), which pair is incomparable?

    4 does not divide 6, and 6 does not divide 4.
  3. 3. In the Hasse diagram of divisibility on {1, 2, 3, 4, 6, 12}, which lines start at 1?

    1 is covered only by 2 and 3. The lines to 4, 6 and 12 are implied by longer chains.
  4. 4. A total order is a partial order where:

    In a chain, for any a and b, a โ‰ผ b or b โ‰ผ a.

Summary

  • A partial order is reflexive, antisymmetric and transitive; a set with one is a poset.
  • Elements may be incomparable; if all pairs are comparable the order is total.
  • A Hasse diagram shows only covering pairs, drawn upward, with no loops.
  • (P(X), โІ) and (โ„•โบ, divides) are the standard examples.
  • Any finite poset can be extended to a total order (topological sort).

Next: Extremal Elements, Bounds and Lattices