Skip to content
Tutorials Center
My learning

Topics

Lesson 25 of 37 ยท Cardinality and Orders

Partial Orders and Lattices

Learn partial and total orders, Hasse diagrams, minimal and maximal elements, bounds, topological sorting and lattices, with Python code on divisibility and subsets.

Some things can be ranked, and some can only be partly compared. The number 3 is less than 5, but is the set {1, 2} "less than" {2, 3}? Neither contains the other. A partial order captures this: a relation that is reflexive, antisymmetric and transitive (see relations and their properties). A set with such a relation is a poset (partially ordered set), written (P, โ‰ค).

Standard examples: (โ„•, โ‰ค); the divisibility order (โ„•โบ, |); and the subset order (P(A), โІ) of the power set. A total (linear) order is a partial order where any two elements are comparable. (โ„•, โ‰ค) is total; divisibility is not (2 and 3 are incomparable).

Hasse diagrams

Because a partial order is transitive and reflexive, we do not draw every pair. A Hasse diagram shows only the covering relations: a is covered by b if a < b and nothing lies strictly between. Draw smaller elements lower and omit arrows and loops.

flowchart BT
    one["1"] --> two["2"]
    one --> three["3"]
    two --> four["4"]
    two --> six["6"]
    three --> six
    four --> twelve["12"]
    six --> twelve

Hasse diagram of the divisors of 12 under divisibility, bottom to top.

Python Divisibility order and its covering pairs

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.

Special elements

In a poset (P, โ‰ค) and a subset S โІ P:

  • Minimal element: nothing below it. Maximal: nothing above it. There may be several.
  • Least element: below everything. Greatest: above everything. If it exists, it is unique.
  • Upper bound of S: an element โ‰ฅ every member of S. Lower bound similarly.
  • Supremum (least upper bound, sup S or join) and infimum (greatest lower bound, inf S or meet).

In divisibility on {2, 3, 4, 6, 12} the minimal elements are 2 and 3 (nothing divides them), there is no least element, and 12 is greatest. Minimal is not the same as least.

Python Minimal, maximal, bounds and sup/inf

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.

Lattices

A lattice is a poset in which every two elements have both a supremum (join, a โˆจ b) and an infimum (meet, a โˆง b). Examples:

  • Divisors of n with divisibility: join = lcm, meet = gcd.
  • Subsets of a set with โІ: join = โˆช, meet = โˆฉ.
  • Truth values {false, true} with false โ‰ค true: join = or, meet = and.

This is no coincidence: propositional logic and set algebra are both Boolean lattices (lattices that are distributive and complemented). We use that again in Boolean algebra and circuits. A lattice with a join and meet for every subset is complete; every finite lattice is, and P(A) is too. Complete lattices underlie fixed-point results (Knaster-Tarski) used in program analysis.

Python Divisor lattice: join is lcm, meet is gcd

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.

Linear extensions and topological sorting

Every finite poset can be extended to a total order that respects it. This is exactly topological sorting: schedule tasks so every prerequisite comes first. Build systems, course plans and spreadsheet recalculation all rely on it.

Python A topological sort (Kahn's algorithm)

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. Which set of properties defines a partial order?

    A partial order is reflexive, antisymmetric and transitive. Totality is extra and gives a total order.
  2. 2. In the divisibility poset on {2, 3, 4, 6, 12}, which is true?

    Nothing in the set divides 2 or 3, so both are minimal; neither is least. 12 is greatest.
  3. 3. In the lattice of divisors of 36 under divisibility, the join of 4 and 6 is

    The join is the least common multiple, lcm(4, 6) = 12.
  4. 4. What is a topological sort?

    It lists the elements so that whenever a < b, a appears before b.

Summary

  • A partial order is reflexive, antisymmetric and transitive; total orders compare every pair.
  • Hasse diagrams draw only covering relations; minimal, maximal, least, greatest, bounds, sup and inf describe structure.
  • A lattice has a join and a meet for every pair; divisors (lcm/gcd), subsets (โˆช/โˆฉ) and truth values (or/and) are examples.
  • Topological sorting is a linear extension of a partial order.

Next: Well-Orders, Induction and Ordinals