Chapter 14 of 30

Lattices

In Partial Orders & Hasse Diagrams we saw that two elements of a poset may have no least upper bound (the "bowtie") or no greatest lower bound. Many of the posets we actually use never have this problem. Any two subsets have a smallest common superset (their union) and a largest common subset (their intersection). Any two positive integers have an lcm and a gcd. Any two numbers have a max and a min.

Posets with this "always have a join and a meet" property are called lattices. They are the bridge between order theory and algebra: in a lattice the order can be described entirely by two operations, ∨ (join) and ∧ (meet), and when those operations distribute and every element has a complement, we get a Boolean algebra, the mathematics behind digital circuits and set operations.

A lattice is a poset in which every pair of elements a, b has a least upper bound a ∨ b (join) and a greatest lower bound a ∧ b (meet).

In this chapter we check whether a Hasse diagram is a lattice, learn the algebraic laws of ∨ and ∧, and study bounded, distributive, modular and complemented lattices, ending with Boolean algebras. Every lattice claim here (including the divisor-lattice theorem for all n ≤ 200) was verified by brute force.


Definition and Examples

Recall from the previous chapter: a ∨ b = lub{a, b} is the smallest element above both, and a ∧ b = glb{a, b} is the largest element below both. A poset is a lattice when these exist for every pair.

Lattice

a ∨ b

a ∧ b

(P(S), ⊆)

A ∪ B

A ∩ B

(ℤ+, |)

lcm(a, b)

gcd(a, b)

(Dn, |), the divisors of n

lcm(a, b)

gcd(a, b)

(ℤ, ≤) or any chain

max(a, b)

min(a, b)

({0, 1}, ≤)

a OR b

a AND b

Dn is closed under lcm and gcd: if a and b divide n, so do lcm(a, b) and gcd(a, b). That is why every Dn is a lattice.

Non-examples

  • The bowtie {a, b, c, d} with a, b below both c and d: {a, b} has two incomparable upper bounds c and d, so no join.

  • ({1, 2, 3, 4, 6}, |): 4 and 6 have no common multiple in the set (12 is missing), so no join.

  • ({2, 3, 6}, |): 2 and 3 have no common divisor in the set, so no meet. A missing top or bottom element is the quickest thing to look for when a finite poset fails to be a lattice.

How to test a Hasse diagram

  1. A finite lattice must have a unique bottom and a unique top (proved below). If the diagram has two minimal or two maximal elements, stop: not a lattice.

  2. For each pair of incomparable elements, list the common upper bounds. There must be exactly one lowest among them. Likewise for lower bounds.

  3. Watch for two incomparable elements that both lie above the same two incomparable elements, with nothing in between: that is a hidden bowtie.


The Algebra of ∨ and ∧

Connecting lemma. In any lattice, a ≼ b ⇔ a ∧ b = a ⇔ a ∨ b = b.

Proof. If a ≼ b, then a is a lower bound of {a, b}, and every lower bound of {a, b} is ≼ a, so a is the greatest lower bound: a ∧ b = a. Conversely, if a ∧ b = a, then a = a ∧ b ≼ b. The statement for ∨ is the mirror image. ∎

From this lemma all the familiar laws follow:

Law

Join form

Meet form

Idempotent

a ∨ a = a

a ∧ a = a

Commutative

a ∨ b = b ∨ a

a ∧ b = b ∧ a

Associative

(a ∨ b) ∨ c = a ∨ (b ∨ c)

(a ∧ b) ∧ c = a ∧ (b ∧ c)

Absorption

a ∨ (a ∧ b) = a

a ∧ (a ∨ b) = a

Absorption, for example: a ∧ b ≼ a, so by the lemma a ∨ (a ∧ b) = a. Associativity holds because both sides equal the lub of the three-element set {a, b, c}.

These laws can also be taken as the definition: a set with two binary operations that are commutative, associative and satisfy the absorption laws is a lattice, with the order defined by a ≼ b ⇔ a ∧ b = a. The order view and the algebra view describe exactly the same objects.

Duality principle

Turning a Hasse diagram upside down gives another lattice, with ∨ and ∧ swapped (and 0 and 1 swapped). Therefore any statement proved for all lattices remains true when you swap ∨ ↔ ∧, ≼ ↔ ≽ and 0 ↔ 1. That is why every law above comes in pairs, and why we only need to prove one of each pair.


Bounded Lattices and Sublattices

A lattice is bounded if it has a least element 0 (bottom) and a greatest element 1 (top). Then a ∨ 0 = a, a ∧ 1 = a, a ∨ 1 = 1 and a ∧ 0 = 0 for every a.

Every finite lattice is bounded. If L = {a1, …, an}, then a1 ∨ a2 ∨ … ∨ an (well defined by associativity) is above every ai, so it is the top; dually for the bottom. Infinite lattices need not be bounded: (ℤ, ≤) is a lattice with no top and no bottom.

A sublattice of L is a non-empty subset closed under the same ∨ and ∧ as L. This is stricter than "a subset that happens to be a lattice in the inherited order":

  • In D12, the subset {1, 2, 4, 12} is a sublattice (it is a chain, and joins and meets of its elements stay inside).

  • The subset {1, 2, 3, 12} is a lattice under divisibility on its own (there 2 ∨ 3 = 12), but it is not a sublattice of D12, because in D12, 2 ∨ 3 = lcm(2, 3) = 6, which is missing.


Distributive and Modular Lattices

A lattice is distributive if for all a, b, c:
a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c), and equivalently
a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c).

(In any lattice each of these two laws implies the other, so checking one is enough.) Distributive lattices: every chain, every power set (∩ distributes over ∪), every Dn (gcd distributes over lcm, verified by brute force for n ≤ 200 and true in general because it reduces to min and max of prime exponents).

Two small lattices are not distributive, and they turn out to be the only obstacles:

   M3 (diamond)              N5 (pentagon)

        1                         1
      / | \                      / \
     x  y  z                    c   \
      \ | /                     |    b
        0                       a   /
                                 \ /
                                  0
  • M3: x ∧ (y ∨ z) = x ∧ 1 = x, but (x ∧ y) ∨ (x ∧ z) = 0 ∨ 0 = 0.

  • N5 (with a ≺ c): c ∧ (a ∨ b) = c ∧ 1 = c, but (c ∧ a) ∨ (c ∧ b) = a ∨ 0 = a.

A weaker law is modularity: L is modular if a ≼ c implies a ∨ (b ∧ c) = (a ∨ b) ∧ c. Every distributive lattice is modular. M3 is modular but not distributive. N5 is not even modular: with a ≼ c, a ∨ (b ∧ c) = a ∨ 0 = a, but (a ∨ b) ∧ c = 1 ∧ c = c.

Theorem (Dedekind, Birkhoff). A lattice is modular if and only if it has no sublattice isomorphic to N5. It is distributive if and only if it has no sublattice isomorphic to N5 or M3.

So to show a lattice is not distributive, find a copy of the diamond or the pentagon inside it.


Complements and Complemented Lattices

In a bounded lattice, b is a complement of a if a ∨ b = 1 and a ∧ b = 0. A lattice is complemented if every element has at least one complement.

Complements need not exist, and need not be unique:

  • In M3, x has two complements, y and z (x ∨ y = 1, x ∧ y = 0, and the same with z).

  • In N5, b has two complements, a and c. Elements a and c each have only b.

  • In a chain with more than 2 elements, a middle element a (0 ≺ a ≺ 1) has no complement: for any b, either b ≼ a, and then a ∨ b = a ≠ 1, or a ≼ b, and then a ∧ b = a ≠ 0.

Theorem. In a bounded distributive lattice, every element has at most one complement.

Proof. Suppose b and c are both complements of a. Then

b = b ∧ 1 = b ∧ (a ∨ c) = (b ∧ a) ∨ (b ∧ c) = 0 ∨ (b ∧ c) = b ∧ c

and by the same steps with b and c swapped, c = c ∧ b. Hence b = b ∧ c = c. ∎

This explains the M3 and N5 examples: elements with two complements can only exist in non-distributive lattices.

Complements in Dn

In Dn the bottom is 1 and the top is n. So b is a complement of a exactly when gcd(a, b) = 1 and lcm(a, b) = n, i.e. ab = n with gcd(a, b) = 1. The only candidate is b = n/a, and it works exactly when gcd(a, n/a) = 1.

Dn is complemented if and only if n is square-free (no prime appears twice in its factorisation). If p2 | n, then a = p has n/p still divisible by p, so p has no complement. If n is square-free, every divisor a shares no prime with n/a. (Checked by program for all n ≤ 200.)

Code: testing lattices

from itertools import product

def analyse(E, leq):
    """Check whether the finite poset (E, leq) is a lattice, and if so whether
    it is distributive and which elements have complements."""
    def join(a, b):
        ub = [x for x in E if leq(a, x) and leq(b, x)]
        least = [u for u in ub if all(leq(u, v) for v in ub)]
        return least[0] if least else None

    def meet(a, b):
        lb = [x for x in E if leq(x, a) and leq(x, b)]
        greatest = [g for g in lb if all(leq(v, g) for v in lb)]
        return greatest[0] if greatest else None

    for a, b in product(E, repeat=2):
        if join(a, b) is None or meet(a, b) is None:
            return f"not a lattice: {a} and {b} have no join or no meet"

    bottom = next(x for x in E if all(leq(x, y) for y in E))
    top = next(x for x in E if all(leq(y, x) for y in E))
    distributive = all(meet(a, join(b, c)) == join(meet(a, b), meet(a, c))
                       for a, b, c in product(E, repeat=3))
    complements = {a: [b for b in E if join(a, b) == top and meet(a, b) == bottom]
                   for a in E}
    return f"lattice, distributive={distributive}, complements={complements}"

divides = lambda a, b: b % a == 0
divisors = lambda n: [d for d in range(1, n + 1) if n % d == 0]

print("D12 :", analyse(divisors(12), divides))
print("D30 :", analyse(divisors(30), divides))

# N5 (pentagon): 0 < a < c < 1 and 0 < b < 1
N5 = {("0", x) for x in "0abc1"} | {(x, "1") for x in "0abc1"} | {(x, x) for x in "0abc1"} | {("a", "c")}
print("N5  :", analyse(list("0abc1"), lambda x, y: (x, y) in N5))

# Bowtie: a, b both below c and d
bowtie = {(x, x) for x in "abcd"} | {("a", "c"), ("a", "d"), ("b", "c"), ("b", "d")}
print("Bow :", analyse(list("abcd"), lambda x, y: (x, y) in bowtie))

Output:

D12 : lattice, distributive=True, complements={1: [12], 2: [], 3: [4], 4: [3], 6: [], 12: [1]}
D30 : lattice, distributive=True, complements={1: [30], 2: [15], 3: [10], 5: [6], 6: [5], 10: [3], 15: [2], 30: [1]}
N5  : lattice, distributive=False, complements={'0': ['1'], 'a': ['b'], 'b': ['a', 'c'], 'c': ['b'], '1': ['0']}
Bow : not a lattice: a and b have no join or no meet

D12 (12 = 22 · 3) is distributive but 2 and 6 have no complement. D30 (30 = 2 · 3 · 5) is distributive and complemented: each divisor a has the unique complement 30/a.


Boolean Algebras

A Boolean algebra is a complemented distributive lattice. By the theorem above, each element a has exactly one complement, written a′ (or ā, ¬a).

The three standard Boolean algebras are the same structure in different clothes:

Abstract

Sets P(S)

Logic / circuits {0, 1}

Dn, n square-free

a ∨ b

A ∪ B

a OR b

lcm(a, b)

a ∧ b

A ∩ B

a AND b

gcd(a, b)

a′

S − A

NOT a

n / a

0, 1

∅, S

0, 1

1, n

In every Boolean algebra De Morgan's laws hold: (a ∨ b)′ = a′ ∧ b′ and (a ∧ b)′ = a′ ∨ b′, along with a ∨ a′ = 1, a ∧ a′ = 0 and (a′)′ = a.

A key structural fact: every finite Boolean algebra is isomorphic to the power set P(S) of some finite set S, so it has exactly 2k elements, where k is the number of atoms (elements that cover 0). For example D30 has atoms 2, 3, 5 and is a copy of P({2, 3, 5}): its Hasse diagram is the same cube as P({a, b, c}) in the previous chapter.

                 30
              /   |   \
            6    10    15
            |  \ /  \ /  |
            |   X    X   |
            |  / \  / \  |
            2     3     5
              \   |   /
                  1

Consequence for exams: a lattice with 6 (or any non-power-of-2 number of) elements can never be a Boolean algebra. And Dn is a Boolean algebra exactly when n is square-free.


Lattice Types at a Glance

Lattice

Distributive

Modular

Complemented

Boolean

Chain with 2 elements

Yes

Yes

Yes

Yes

Chain with ≥ 3 elements

Yes

Yes

No

No

P(S)

Yes

Yes

Yes

Yes

D30

Yes

Yes

Yes

Yes

D12, D36, D8

Yes

Yes

No

No

M3 (diamond)

No

Yes

Yes (not uniquely)

No

N5 (pentagon)

No

No

Yes (not uniquely)

No


Common Mistakes

  • Using lcm and gcd in a subset of ℤ+ that does not contain them. Joins and meets must be elements of the poset.

  • Declaring a diagram a lattice because it has a top and a bottom. Necessary for finite lattices, not sufficient: check every incomparable pair (a top-and-bottom diagram can still hide a bowtie in the middle).

  • Calling M3 or N5 "not complemented". They are complemented; they fail distributivity, and their complements are not unique.

  • Confusing "lattice in the inherited order" with "sublattice". {1, 2, 3, 12} ⊆ D12 is the first but not the second.

  • Saying Dn is Boolean whenever it has 2k elements. D8 has 4 elements but is a chain 1 | 2 | 4 | 8, not Boolean. The right test is "n square-free".


Practice and GATE-Style Questions

Q1. Is ({1, 2, 3, 4, 6, 12}, |) a lattice? Is it distributive? Complemented?

It is D12: a lattice (lcm and gcd stay inside), distributive (every Dn is), but not complemented: 2 and 6 have no complement because 12 is not square-free.

Q2. In D36, which elements have complements?

a has a complement iff gcd(a, 36/a) = 1. Checking the divisors 1, 2, 3, 4, 6, 9, 12, 18, 36: only 1, 4, 9, 36 qualify (complement pairs 1–36 and 4–9).

Q3. In the lattice M3, how many complements does each atom have?

Two: each atom's join with either other atom is 1 and the meet is 0.

Q4. Can a lattice with 6 elements be a Boolean algebra?

No. A finite Boolean algebra is isomorphic to a power set, so its size is a power of 2.

Q5. Prove that every chain is a distributive lattice.

In a chain, ∨ = max and ∧ = min. Check a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c) by cases. If a ≽ b and a ≽ c, both sides equal max(b, c). If a ≼ b or a ≼ c, then a ≼ max(b, c), so the left side is a; and one of a ∧ b, a ∧ c equals a while the other is ≼ a, so the right side is also a. ∎

Q6. Interview: where do lattices appear in software?

Static analysis and compiler data-flow analysis work over lattices of abstract values (for constant propagation: "undefined" ⊑ a specific constant ⊑ "not a constant") and iterate joins until a fixed point. Type systems use a lattice of types (join = least common supertype). Distributed systems use join-semilattices for CRDTs: merging replicas with ∨ is commutative, associative and idempotent, so the order and duplication of messages do not matter.


Summary

  • A lattice is a poset where every pair has a join (lub) and a meet (glb).

  • ∨ and ∧ are idempotent, commutative, associative and absorptive; a ≼ b ⇔ a ∧ b = a ⇔ a ∨ b = b.

  • Every finite lattice is bounded. A sublattice must be closed under the original ∨ and ∧.

  • Distributive ⇔ no M3 or N5 inside; modular ⇔ no N5 inside.

  • In a distributive lattice complements are unique when they exist.

  • Boolean algebra = complemented distributive lattice; finite ones have 2k elements. Dn is Boolean iff n is square-free.

Check for a top, a bottom and a unique lowest common upper bound for every pair; then look for a diamond or a pentagon. That sequence answers almost every lattice question.