JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Order, Lattices, and Boolean Algebras

Subalgebra lattices, congruence lattices, divisibility — order structure was underneath everything. Make it precise: posets and Hasse diagrams, lattices viewed two equivalent ways, the distributive/modular divide, and Boolean algebras as the algebra of logic.

Posets and two views of a lattice

A partially ordered set (poset) is a set P with a relation ≤ that is reflexive, antisymmetric and transitive. “Partial” means some pairs may be incomparable. You have used posets constantly: subgroups ordered by inclusion, ideals of a ring, natural numbers ordered by divisibility. A finite poset is drawn as a Hasse diagram — vertices for elements, an upward edge x — y whenever y *covers* x (x < y with nothing strictly between).

A lattice is a poset in which every pair {x, y} has a least upper bound x ∨ y (the join) and a greatest lower bound x ∧ y (the meet). This is the *order* view. There is an equivalent *algebraic* view: a lattice is an algebra (L, ∨, ∧) of two binary operations satisfying commutativity, associativity, idempotence, and the absorption laws x ∨ (x ∧ y) ≈ x and x ∧ (x ∨ y) ≈ x. The two views determine each other — define x ≤ y to mean x ∧ y = x — which is precisely why lattices sit inside universal algebra as an equational variety.

Distributive vs. modular

Among lattices, two strengthening identities matter most. A distributive lattice satisfies x ∧ (y ∨ z) ≈ (x ∧ y) ∨ (x ∧ z) (equivalently its dual). A modular lattice satisfies the weaker law: if x ≤ z then x ∨ (y ∧ z) ≈ (x ∨ y) ∧ z. Distributive ⟹ modular, never the reverse. The subgroup lattice of a group is generally only modular when normal — but the lattice of *normal* subgroups, and more generally Con(A) for any group, ring, or module, is always modular.

Two small lattices tell distributive and modular apart -- the classic test.

M3 (the 'diamond'): bottom 0, top 1, three incomparable middles a,b,c.
  Hasse:        1
             /  |  \
            a   b   c
             \  |  /
                0
  Modular? YES.   Distributive? NO. Check at x=a, y=b, z=c:
    a ^ (b v c) = a ^ 1 = a
    (a ^ b) v (a ^ c) = 0 v 0 = 0
    a =/= 0, so distributivity FAILS.

N5 (the 'pentagon'): 0 < a < c < 1 and 0 < b < 1, with a,c each incomparable to b.
  Hasse:        1
              /   \
             c     b
             |    /
             a   /
              \ /
               0
  Modular? NO. Take x=a, z=c (a <= c), y=b:
    a v (b ^ c) = a v 0 = a
    (a v b) ^ c = 1 ^ c = c
    a =/= c, so MODULARITY fails.

Theorem (Dedekind/Birkhoff): a lattice is modular iff it has no sublattice
isomorphic to N5; distributive iff it has no sublattice iso to N5 or M3.
M3 is modular but not distributive; N5 is not even modular. They are the two forbidden sublattices.

Boolean algebras

A Boolean algebra is a distributive lattice with a top 1 and bottom 0 in which every element x has a complement ¬x satisfying x ∨ ¬x = 1 and x ∧ ¬x = 0. The motivating examples are the power set 2^S (with ∪, ∩, complement) and the two-element algebra {0, 1} of classical truth values. Every finite Boolean algebra is isomorphic to some 2^S, hence has 2ⁿ elements — there is no Boolean algebra with exactly 3 or 5 elements.

Boolean algebras are again an equational variety (signature (∨, ∧, ¬, 0, 1)), so all the universal-algebra machinery applies: subalgebras, congruences, free Boolean algebras. The free Boolean algebra on n generators is the algebra of all Boolean functions of n inputs — it has 2^(2ⁿ) elements, matching the number of truth tables. This is the precise sense in which Boolean algebra *is* the algebra of propositional logic, and it closes the loop: order theory, equational classes, and free algebras meeting in one object.