Lattices and Boolean Algebras

Tom Judson · GFDL · Abstract Algebra: Theory and Applications, Ch. 8

A lattice is a partially ordered set where every pair of elements has a least upper bound (join) and a greatest lower bound (meet). A Boolean algebra is a distributive, complemented lattice. Boolean algebras connect algebra to logic: meet is AND, join is OR, complement is NOT.

Partial orders

A partial order is a relation that is reflexive (a ≤ a), antisymmetric (a ≤ b and b ≤ a implies a = b), and transitive (a ≤ b and b ≤ c implies a ≤ c). Not every pair needs to be comparable. The divisibility relation on positive integers is a partial order: 2 | 6 but 2 and 3 are incomparable.

Scheme

; Divisibility as a partial order on divisors of 12
; a <= b means a divides b

(define (divides? a b) (= 0 (modulo b a)))

(define divs '(1 2 3 4 6 12))

(display "Divisibility on [1,2,3,4,6,12]:") (newline)
(for-each
  (lambda (a)
    (display "  ") (display a) (display " divides: ")
    (for-each
      (lambda (b)
        (when (and (not (= a b)) (divides? a b))
          (display b) (display " ")))
      divs)
    (newline))
  divs)
; 2 and 3 are incomparable: neither divides the other.

Meet and join

The meet (greatest lower bound) of a and b, written a ∧ b, is the largest element below both. The join (least upper bound), written a ∨ b, is the smallest element above both. In the divisibility lattice, meet is GCD and join is LCM.

Scheme

; Meet = GCD, Join = LCM in the divisibility lattice

(define (gcd a b)
  (if (= b 0) a (gcd b (modulo a b))))

(define (lcm a b)
  (/ (* a b) (gcd a b)))

(display "meet(4, 6) = gcd(4, 6) = ") (display (gcd 4 6)) (newline)
(display "join(4, 6) = lcm(4, 6) = ") (display (lcm 4 6)) (newline)

(display "meet(2, 3) = gcd(2, 3) = ") (display (gcd 2 3)) (newline)
(display "join(2, 3) = lcm(2, 3) = ") (display (lcm 2 3)) (newline)

; Properties: a ^ b <= a, a ^ b <= b
;             a <= a v b, b <= a v b
(display "4 ^ 6 = 2 divides both 4 and 6? ")
(display (and (= 0 (modulo 4 (gcd 4 6)))
              (= 0 (modulo 6 (gcd 4 6)))))

The diamond lattice

The divisors of 6 under divisibility form a diamond-shaped lattice. This is the simplest non-chain lattice: 2 and 3 are incomparable, but both sit between 1 and 6.

Boolean algebras

A Boolean algebra is a distributive lattice with complements: for every element a, there exists a' such that a ∧ a' = 0 and a ∨ a' = 1. The power set of any set, ordered by inclusion, is a Boolean algebra. So is the two-element set (0, 1) with AND, OR, and NOT.

Scheme

; Boolean algebra: power set of {a, b}
; ordered by subset inclusion
; Represent subsets as bitmasks: empty = 0, [a] = 1, [b] = 2, [a,b] = 3

(define (meet a b) (bitwise-and a b))  ; intersection
(define (join a b) (bitwise-ior a b))  ; union
(define (complement a) (bitwise-xor a 3))  ; flip within [a,b]

(define (name s)
  (cond ((= s 0) "[]")
        ((= s 1) "[a]")
        ((= s 2) "[b]")
        ((= s 3) "[a,b]")
        (else "?")))

(display "Meet and join in P([a,b]):") (newline)
(display "  [a] ^ [b]   = ") (display (name (meet 1 2))) (newline)
(display "  [a] v [b]   = ") (display (name (join 1 2))) (newline)
(display "  [a]'        = ") (display (name (complement 1))) (newline)
(display "  [a] ^ [a]'  = ") (display (name (meet 1 (complement 1)))) (newline)
(display "  [a] v [a]'  = ") (display (name (join 1 (complement 1))))

Notation reference

Math	Scheme	Python	Meaning
a ∧ b	(meet a b)	meet(a, b)	Greatest lower bound
a ∨ b	(join a b)	join(a, b)	Least upper bound
a'	(complement a)	comp(a)	Complement
a ≤ b	(divides? a b)	b % a == 0	Partial order
P(S)	bitmask ops	bitmask ops	Power set (Boolean algebra)

Neighbors

Algebra track

← Ch.7 Integral Domains and Fields — fields are complete in a different sense
🔑 Logic Ch.2 — Boolean algebra is the algebra of propositional logic
🔬 Boole 1854 — the historical origin of this whole chapter
🔢 Discrete Math Ch.3 — symbolic logic uses the same lattice operations

Category theory connections

Milewski Ch.3 — preorders are categories where hom-sets have at most one morphism; lattices are preorders with products and coproducts
Milewski Ch.23 — topoi have Heyting algebra structure on subobjects, generalizing Boolean algebras by dropping excluded middle

Translation notes

Judson covers lattices and Boolean algebras in Ch. 19. The power set Boolean algebra is the canonical example. The connection to logic (meet = AND, join = OR) makes Boolean algebras central to computer science. The Heyting algebra generalization (drop the complement axiom, keep distributivity) connects to intuitionistic logic and the internal logic of topoi. Every Boolean algebra is a Heyting algebra, but not conversely.

← Integral Domains and Fields by june.kim fin · 8 of 8