Lattices

Lattices appear as the load-bearing structure behind much of discrete mathematics and beyond. In combinatorics, the partition lattice $\Pi_n$ underlies the theory of set partitions and the Möbius function used in inclusion–exclusion and the combinatorics of species; the subspace lattice of a vector space over a finite field generalizes the Boolean lattice and drives $q$-analogues of counting identities. In abstract algebra, the lattice of subgroups of a group, the lattice of ideals of a ring, and the lattice of subfields of a field extension (via the Fundamental Theorem of Galois Theory) are all genuine lattices whose meet/join structure encodes deep algebraic relationships — the lattice of subfields is literally order-reversing-isomorphic to the lattice of subgroups of the Galois group. In logic and computer science, the lattice of truth values underlies Boolean Algebras and propositional logic, while the theory of domain theory in programming language semantics uses complete lattices (where arbitrary, not just pairwise, joins and meets exist) to model computation via fixed points of continuous functions, powering denotational semantics for recursive programs. Formal concept analysis, used in data mining and knowledge representation, builds a "concept lattice" directly from a binary relation between objects and attributes. In cryptography, geometric lattices in $\mathbb{R}^n$ (a different, but historically connected, use of the word "lattice," referring to discrete subgroups of $\mathbb{R}^n$) underlie lattice-based cryptographic schemes believed to resist quantum attacks, such as those standardized in post-quantum key exchange. In statistics and reliability theory, lattices of events and sigma-algebras structure the combinatorics of probability spaces, and in circuit design and hardware verification, lattices of Boolean functions under the implication order model logical dependency and simplification. The general theme uniting all of these: whenever two "combination" operations are dual to each other and compatible with a natural containment order, a lattice is quietly organizing the structure underneath.

Ask the tutor: Can you show me why the modular law is strictly weaker than the distributive law, using the subgroup lattice of a small non-abelian group as an example?

Think of a lattice as a landscape where every two points have a well-defined "meeting valley" below them and a well-defined "joining peak" above them, and these are the closest such valley and peak — not just any common bound, but the tightest one. The Hasse diagram of a finite lattice always lets you find, for any two nodes, a unique node directly reachable upward from both (their join) by the shortest possible detour, and similarly downward (their meet). The divisor lattice of $60 = 2^2 \cdot 3 \cdot 5$ is a clean example: divisors are ordered by "divides," meet is gcd, join is lcm, and the diagram is literally a 3-dimensional grid (a product of three chains) because $60$ has three distinct prime factors, with exponents $0$–$2$, $0$–$1$, $0$–$1$. Two divisors like $12 = 2^2\cdot3$ and $20 = 2^2\cdot 5$ meet at $4 = 2^2$ and join at $60 = 2^2\cdot3\cdot5$, and both of these are computed coordinatewise — the meet takes the coordinatewise minimum of exponents, the join the coordinatewise maximum.

Example 1: The divisor lattice of a non-squarefree, non-prime-power integer. Let $L = \{1,2,3,4,6,12,20,60\}$, the set of divisors of $60$, ordered by $a \le b \iff a \mid b$. This is a sub-poset of the full divisor lattice of $60$ shown in the figure, chosen with asymmetric elements to illustrate the mechanics concretely. Checking the poset axioms. Divisibility is reflexive ($a \mid a$), antisymmetric on positive integers (if $a\mid b$ and $b \mid a$ then $a=b$), and transitive ($a\mid b, b\mid c \Rightarrow a \mid c$). So $(L, \mid)$ is a poset. Computing a non-trivial meet and join. Take $a = 12 = 2^2\cdot 3$ and $b = 20 = 2^2 \cdot 5$. Writing each divisor of $60$ as $2^{e_1}3^{e_2}5^{e_3}$ with $e_1\in\{0,1,2\}, e_2\in\{0,1\}, e_3\in\{0,1\}$, divisibility corresponds to coordinatewise $\le$ on exponent vectors. So $12 = (2,1,0)$ and $20 = (2,0,1)$. The lower bounds of $\{12,20\}$ within $L$ are all $d \in L$ with $d \mid 12$ and $d\mid 20$: checking $L = \{1,2,3,4,6,12,20,60\}$, the common divisors present are $1, 2, 4$. Among these, $4$ is a multiple of both $1$ and $2$, so $4$ is the greatest: $12 \wedge 20 = 4$. In exponent-vector language, $4 = (2,0,0) = (\min(2,2), \min(1,0), \min(0,1))$, matching coordinatewise minimum. The upper bounds of $\{12,20\}$ within $L$ are elements divisible by both; checking the list, only $60$ qualifies (since $12 \cdot 20 = 240 \ne$ any smaller listed multiple, and $60 = 2^2\cdot3\cdot5$ is divisible by both $12$ and $20$). So $12 \vee 20 = 60 = (2,1,1)$, the coordinatewise maximum. Checking absorption directly, numerically. Absorption says $a \vee (a \wedge b) = a$. With $a=12, b=20$: $a \wedge b = 4$, and $12 \vee 4$: since $4 \mid 12$, $4$ is a lower bound of $\{12,4\}$ and $12$ is an upper bound of itself and of $4$; the least upper bound of $\{12,4\}$ is $12$ itself (as $12$ is already an upper bound and no proper divisor of $12$ can be an upper bound since it would need to be a multiple of $12$). So $12 \vee 4 = 12$, confirming $a \vee (a\wedge b) = a$ numerically.

Example 2: The partition lattice $\Pi_4$, a lattice not built from a linear order on values. Let $S = \{1,2,3,4\}$ and let $L = \Pi_4$ be the set of all partitions of $S$ into disjoint nonempty blocks, ordered by refinement: $\pi_1 \le \pi_2$ if every block of $\pi_1$ is contained in some block of $\pi_2$ (i.e. $\pi_1$ is finer, $\pi_2$ coarser). Take two specific, asymmetric partitions:

Meet. The meet of two partitions under refinement order is the common refinement: the partition whose blocks are the nonempty intersections of a block of $\pi_1$ with a block of $\pi_2$. Computing intersections:

Collecting the nonempty intersections: $\{1\},\{2\},\{3\},\{4\}$. So

the finest partition (all singletons). This is indeed a lower bound (it refines both $\pi_1$ and $\pi_2$, since each singleton sits inside the corresponding block), and one checks it is the greatest such common refinement because any common refinement of $\pi_1$ and $\pi_2$ must separate $1$ from $2$ (since $\pi_2$ separates them) and separate $2$ from $3$ (since $\pi_1$ separates them), forcing all four elements into distinct blocks. Join. The join is the finest partition coarser than both, obtained by merging blocks connected through a chain of overlaps. Since $\pi_1$ links $1,2$ together and $\pi_2$ links $2,3$ together, transitively $1,2,3$ must lie in one block in any common coarsening, while $4$ is isolated in both $\pi_1$ and $\pi_2$ and need not be merged. So

Check this is an upper bound: $\{1,2\}\subseteq\{1,2,3\}$ and $\{3\}\subseteq\{1,2,3\}$ and $\{4\}\subseteq\{4\}$, so it refines-from $\pi_1$; similarly it refines-from $\pi_2$. It is the least upper bound because any coarsening of both $\pi_1$ and $\pi_2$ must merge $1,2$ (forced by $\pi_1$) and merge $2,3$ (forced by $\pi_2$), hence merge $1,2,3$, and nothing forces merging in $4$. This example shows meet and join in $\Pi_4$ are computed by genuinely different combinatorial rules (intersection of blocks vs. transitive-closure merging) than the coordinatewise min/max of the divisor lattice, yet both satisfy exactly the same four algebraic axioms — the payoff of the abstract definition.