Lattice Theory Foundations

Equivalence Relations and the Partition Lattice

Eq(A) is the ambient lattice inside which every congruence lattice sits. Its joins are awkward, its meets are trivial, and that asymmetry propagates through the whole subject.

Engineering · Mathematics4 min readKV-MATH-0207

Learning objectives

Describe Eq(A) as a complete algebraic lattice and identify its bounds.
Compute meets and joins of equivalence relations correctly.
Explain why the join is an infinite alternating union in general.
Define permutability and show it collapses the join to a single composite.
Locate Con A as a complete sublattice of Eq(A).

01Eq(A) and the partition correspondence

Equivalence relations on a set A correspond exactly to partitions of A, and the correspondence is an order isomorphism when partitions are ordered by refinement. The relation Δ corresponds to the partition into singletons; ∇ corresponds to the one-block partition.

Two views of the same lattice
Relational view	Partition view	Note
θ ⊆ φ	the θ-partition refines the φ-partition	Refinement is the order.
Δ	all blocks singletons	Least element.
∇	a single block	Greatest element.
θ ∩ φ	blocks are pairwise intersections	Meet is easy.
θ ∨ φ	blocks generated by chaining	Join is not the union.

Eq(A) is a complete lattice: arbitrary intersections of equivalence relations are equivalence relations, so arbitrary meets exist, and by the one-sided criterion arbitrary joins follow. It is algebraic, with the compact elements being the equivalence relations generated by finitely many pairs.

02Meets are intersections; joins are not unions

The intersection of two equivalence relations is an equivalence relation, so the meet in Eq(A) is simply ∩. The union is almost never an equivalence relation, because transitivity fails: a related to b in θ and b related to c in φ gives no relation between a and c in θ ∪ φ.

θ ∨ φ = θ ∪ (θ ∘ φ) ∪ (θ ∘ φ ∘ θ) ∪ (θ ∘ φ ∘ θ ∘ φ) ∪ ⋯

The join is the union of all finite alternating composites. Two elements are related exactly when a finite chain connects them, alternating between θ-steps and φ-steps.

This is the transitive closure of the union, and the chain length is unbounded in general. That unboundedness is precisely what makes join computations in congruence lattices expensive and what makes the permutable case so much more tractable.

03Permutability

θ and φ permute when θ ∘ φ = φ ∘ θ. When they do, the alternating union collapses immediately: every longer composite equals θ ∘ φ.

ProcedureDeciding permutability and computing the join

in: θ, φ → out: θ ∨ φ, and whether the pair permutes

input: equivalence relations θ, φ on A
compute θ ∘ φ and φ ∘ θ
if θ ∘ φ = φ ∘ θ:
θ ∨ φ = θ ∘ φ (one composite suffices)
and θ ∘ φ is automatically an equivalence relation
otherwise:
θ ∨ φ = transitive closure of θ ∪ φ
computed as the union of alternating composites of unbounded length

Correctness: permutability makes θ ∘ φ symmetric and transitive, hence an equivalence relation containing both, hence the join. Caveat: permutability is a property of the pair, not of the lattice; an algebra is congruence-permutable when every pair of congruences permutes.

Key resultPermutability is a Mal'cev condition

A variety is congruence-permutable exactly when it has a ternary term p satisfying p(x, y, y) ≈ x and p(x, x, y) ≈ y. For groups, p(x, y, z) = x · y⁻¹ · z. For lattices no such term exists, which is why lattice congruence joins remain genuinely infinitary.

04Con A inside Eq(A)

The congruences of an algebra A form a subset of Eq(A) — those equivalence relations compatible with the operations. Con A is a complete sublattice of Eq(A): arbitrary intersections of congruences are congruences, and the join computed in Eq(A) of a family of congruences is again a congruence.

Meets agree
The meet of congruences in Con A is their intersection, exactly as computed in Eq(A). No discrepancy arises.
Joins agree too
The Eq(A) join of congruences is compatible with the operations, so it lies in Con A and is the join there. Con A is therefore a complete sublattice, not merely a complete lattice in its own right.
But the shape can differ wildly
Eq(A) is always geometric and, for |A| ≥ 4, non-modular. Con A may be distributive, modular or arbitrary depending on A, and constraining it is the central classification programme.

05The shape of Eq(A) itself

Eq(A) is a complemented, relatively complemented, algebraic lattice. For sets of size at least four it is non-modular, and the pentagon can be exhibited explicitly.

Eq(A) for |A| ≤ 3

Modular

Small enough that no pentagon fits. Eq of a three-element set is the five-element modular lattice M5.

Eq(A) for |A| ≥ 4

Non-modular

A pentagon appears, so Eq(A) is neither modular nor distributive. Any variety whose members have congruence lattices equal to full Eq(A) is therefore badly behaved.

That Eq of a three-element set is M5 is a pleasing coincidence: the diamond that witnesses non-distributivity in the previous page is itself a partition lattice.

Frequently asked

Is the union of two equivalence relations ever an equivalence relation?

Only when one contains the other. If neither contains the other, pick a pair in θ but not φ and a pair in φ but not θ sharing an element; transitivity then fails in the union. So the union coincides with the join precisely in the comparable case.

Does congruence-permutability imply congruence-modularity?

Yes. Permutable congruences give a modular congruence lattice — this is a classical result and explains why groups, rings and modules all have modular congruence lattices. The converse fails: there are congruence-modular varieties that are not permutable.

Why is Eq(A) non-modular for four-element sets?

Take A = {1, 2, 3, 4} and construct partitions pairing the elements in two different ways, with a third partition comparable to one of them. Chasing the definitions produces a pentagon among the resulting equivalence relations. The consequence is that congruence-modularity is a real restriction on an algebra rather than something inherited free from the ambient partition lattice.

Sources and further reading

S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Millennium Edition (a corrected re-typesetting of Springer GTM 78, 1981).
G. Grätzer, Universal Algebra, 2nd edition, Springer.
R. McKenzie, G. McNulty and W. Taylor, Algebras, Lattices, Varieties, Volume I.

Original KEVOS® explanatory article. Written from the topic map of the cited works; no text is reproduced from them.