Mathematics.

order theory

Lattices

Discrete Mathematics25 minDifficulty3 out of 10

You should know: boolean algebra, relations

Overview

A lattice is a partially ordered set (poset) in which every pair of elements has both a least upper bound (join, ∨) and a greatest lower bound (meet, ∧). Equivalently, a lattice can be defined algebraically as a set with two commutative, associative, idempotent binary operations satisfying the absorption laws. Familiar examples include the power set of a set ordered by inclusion (join = union, meet = intersection), the positive integers ordered by divisibility (join = lcm, meet = gcd), and any totally ordered set (join = max, meet = min). Lattices generalize Boolean algebras — a Boolean algebra is precisely a complemented, distributive lattice — and appear throughout logic, computer science, and abstract algebra.

Intuition

Picture the divisibility order on positive integers drawn as a diagram with 1 at the bottom: any two numbers, no matter how unrelated, always have a well-defined 'meeting point' below them (their gcd, the largest number dividing both) and a 'joining point' above them (their lcm, the smallest number both divide into). A lattice is exactly a poset with this guarantee everywhere — no two elements are ever left without a canonical common ceiling and common floor — which is what makes lattices the right structure for combining information (like combining two approximations or two security clearance levels) in a principled way.

Formal Definition

Definition

A poset (L, ≤) is a lattice if for all a, b ∈ L both of the following exist:

a∨b=sup⁡{a,b}(join / least upper bound)a \vee b = \sup\{a,b\} \quad \text{(join / least upper bound)}
Join
a∧b=inf⁡{a,b}(meet / greatest lower bound)a \wedge b = \inf\{a,b\} \quad \text{(meet / greatest lower bound)}
Meet
a∨(b∧c) need not equal (a∨b)∧(a∨c) unless the lattice is distributivea \vee (b \wedge c) \text{ need not equal } (a \vee b) \wedge (a \vee c) \text{ unless the lattice is distributive}
Distributivity is an extra property
a∧(a∨b)=a,a∨(a∧b)=aa \wedge (a \vee b) = a, \qquad a \vee (a \wedge b) = a
Absorption laws (algebraic axioms)

Worked Examples

  1. Join under divisibility is the least common multiple.

    12∨18=lcm⁡(12,18)=3612 \vee 18 = \operatorname{lcm}(12,18) = 36

  2. Meet under divisibility is the greatest common divisor.

    12∧18=gcd⁡(12,18)=612 \wedge 18 = \gcd(12,18) = 6

Answer: 12 ∨ 18 = 36, 12 ∧ 18 = 6.

Practice Problems

Difficulty 2/10

In the divisibility lattice, compute 8 ∧ 12 and 8 ∨ 12.

Difficulty 3/10

Is the poset ({1,2,3,4}, ≤) with the usual numeric order a lattice? Explain.

Difficulty 5/10

Prove that in any lattice, the absorption law a ∧ (a ∨ b) = a holds.

Quiz

A lattice is a poset in which every pair of elements has:
In the divisibility lattice on positive integers, the meet operation corresponds to:
Every Boolean algebra is:

Summary

  • A lattice is a poset where every pair of elements has both a join (least upper bound) and meet (greatest lower bound).
  • Divisibility (join = lcm, meet = gcd) and subset inclusion (join = union, meet = intersection) are canonical examples.
  • Boolean algebras are precisely the distributive, complemented lattices, connecting lattice theory to logic and set theory.

References

  1. WebsiteWikipedia — Lattice (order)