Skip to content
Tutorials Center
My learning

Topics

Lesson 16 of 68 ยท Sets, Relations and Functions

Partial Orders, Hasse Diagrams and Lattices

Go deeper into partially ordered sets: upper and lower bounds, least upper bound and greatest lower bound, lattice tests, distributive and Boolean lattices.

Equivalence Relations and Partial Orders introduced partial orders and drew their Hasse diagrams. This lesson goes one level deeper. It asks which elements are biggest or smallest, how to find the "best common bound" of two elements, and when a partial order is rich enough to be called a lattice. These ideas power version-control merge bases, type hierarchies, access-control levels and the structure of Boolean algebra.

Maximal, minimal, greatest and least

A poset is a set with a relation that is reflexive, antisymmetric and transitive. Because some pairs are incomparable, "biggest" has two meanings.

  • A maximal element has nothing strictly above it. A poset can have several.
  • The greatest element is above every element. If it exists, it is unique and also maximal.
  • Minimal and least are the mirror images.

Take the divisors of 12 ordered by divisibility. The least element is 1 (it divides everything) and the greatest is 12. Now remove 1 and 12 and keep {2, 3, 4, 6}: the minimal elements are 2 and 3 (nothing divides them inside the set), the maximal elements are 4 and 6, and there is no greatest or least element.

Python Maximal, minimal, greatest and least

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.

Bounds, lub and glb

Let S be a subset of a poset. An upper bound of S is an element above every member of S. A lower bound is below every member. Among the upper bounds, the least upper bound (lub), also called the supremum or join, is the one below all other upper bounds. The greatest lower bound (glb), the infimum or meet, is defined the other way.

For two elements a and b we write a โˆจ b for lub{a, b} and a โˆง b for glb{a, b}. In the divisibility order these are the least common multiple and greatest common divisor, as in GCD and the Euclidean Algorithm. In the subset order they are union and intersection.

Python Computing the join and meet

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.

Without 12, the elements 4 and 6 have no upper bound at all, so lub returns None. Elements 2 and 3 do have upper bounds (6), and 6 is the least one.

Lattices

A poset is a lattice when every pair of elements has both a lub and a glb. The divisors of 12 form one. The poset {1, 2, 3, 4, 6} is not a lattice, because lub(4, 6) does not exist.

Order vocabulary

Maximal Nothing strictly above it.
Greatest Above every element.
Minimal Nothing strictly below it.
Least Below every element.
1 / 2

Lattices satisfy algebraic laws that look like the ones for logic: commutativity, associativity, idempotence (a โˆจ a = a) and absorption (a โˆจ (a โˆง b) = a). Because of them, a lattice can be defined purely by the two operations instead of by the order.

Extra properties give special families:

  • Bounded: has a greatest element 1 and a least element 0 (every finite lattice is bounded).
  • Distributive: a โˆง (b โˆจ c) = (a โˆง b) โˆจ (a โˆง c) for all a, b, c. The divisor lattice and subset lattices are distributive.
  • Complemented: every element a has a complement a' with a โˆจ a' = 1 and a โˆง a' = 0.

A bounded, distributive and complemented lattice is a Boolean lattice, the structure behind Boolean Algebra and Logic Circuits. The subsets of a set, ordered by inclusion, are the model example, with complement as set complement.

Python Testing lattice properties

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.

The divisors of 12 are distributive but not complemented: a complement of 2 would need lcm = 12 and gcd = 1, and no divisor does that (the same holds for 6). 4 and 3 are complements of each other. The divisors of 30 and the subsets of a three-element set are both Boolean: 30 is squarefree, so its divisors mirror subsets of its prime factors {2, 3, 5}.

Lattice types in detail

The three families above are only the start. Here is the fuller picture, from weakest to strongest condition.

  • Lattice: every pair has a join and a meet.
  • Bounded lattice: it has a least element 0 and a greatest element 1. Every finite lattice is bounded (join all elements, meet all elements).
  • Complete lattice: every subset, not only pairs, has a join and meet. Every finite lattice is complete. The distinction matters for infinite ones: the rationals ordered by โ‰ค are a lattice but not complete, since the set of rationals below โˆš2 has no least upper bound among rationals, while the reals with ยฑโˆž added are complete.
  • Modular lattice: if a โ‰ค c, then a โˆจ (b โˆง c) = (a โˆจ b) โˆง c. It is a weakened form of distributivity.
  • Distributive lattice: a โˆง (b โˆจ c) = (a โˆง b) โˆจ (a โˆง c). Every distributive lattice is modular.
  • Complemented lattice: every element has at least one complement.
  • Boolean lattice: bounded, distributive and complemented. A finite Boolean lattice always has 2^n elements and is the subset lattice of an n-element set. In a distributive lattice complements are unique when they exist.

A lattice is distributive exactly when it contains no copy of two small forbidden sublattices: the diamond M3 (a bottom, a top and three incomparable middle elements) and the pentagon N5 (a bottom and a top with a chain of two elements a < b next to a third element c). M3 is modular but not distributive; N5 is not even modular. A sublattice is a subset closed under both join and meet.

Python Diamond M3 and pentagon N5: modular, distributive, complemented?

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.

In the diamond every middle element has two complements (the other two middle elements), which is impossible in a distributive lattice. In the pentagon, c has two complements as well (a and b), and the modular law fails at a โ‰ค b. The chain of three has no complement for its middle element. Only the subset lattice passes everything and has unique complements.

Why lattices matter

Version control finds a merge base as the glb (nearest common ancestor) of two commits in the history. A compiler's type system joins int and float to float. Security systems use lattices of clearance levels so that information may only flow upward. In every case the lub and glb give a unique, well-defined "best common thing" for any two elements.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the poset {2, 3, 4, 6} ordered by divisibility, which elements are maximal?

    Nothing in the set is a proper multiple of 4 or of 6, but 2 divides 4 and 6, and 3 divides 6.
  2. 2. In the divisor lattice of 12, what is 4 join 6 (their lub)?

    The lub under divisibility is the least common multiple, lcm(4, 6) = 12.
  3. 3. Which condition makes a poset a lattice?

    Existence of joins and meets for every pair is the definition.
  4. 4. A bounded, distributive, complemented lattice is called what?

    Boolean lattices are exactly the structures modeled by subsets of a set, with union, intersection and complement.

Summary

  • Maximal and minimal elements have nothing strictly above or below them; greatest and least elements are above or below everything.
  • The lub (join, โˆจ) and glb (meet, โˆง) of a pair are its best common bounds; they may fail to exist.
  • A lattice has a join and a meet for every pair; divisibility and subset orders are examples.
  • Bounded, distributive and complemented lattices are Boolean, the algebra behind logic and circuits.

Continue with Functions and Cardinality.