Lattice Theory Foundations
Equivalence Relations and the Partition Lattice Eq(A)
Equivalence relations on a set, their equivalent description as partitions, and the complete lattice Eq(A) they form — the ambient lattice inside which every congruence lattice sits.
Learning objectives
- Move between equivalence relations and partitions fluently
- Compute joins and meets in Eq(A)
- Explain why the join is not the union and what it is instead
Equivalence relations and partitions
A binary relation θ on A that is reflexive, symmetric and transitive. The class of a is written a/θ, and the set of all classes is A/θ.
Each equivalence relation partitions A into disjoint non-empty classes covering A; each such partition arises from exactly one equivalence relation. The two notions are interchangeable, and the source writes Π(A) for the set of partitions and θ(π) for the equivalence relation induced by a partition π.
- Eq(<em>A</em>)
- the set — and lattice — of equivalence relations on A
- Δ
- the identity relation; all classes singletons
- ∇
- the all-pairs relation; one class
- <em>a</em>/θ
- the class of a
- <em>A</em>/θ
- the quotient set
The lattice structure
The equivalence relations on A, ordered by inclusion as sets of pairs, form a complete lattice with least element Δ and greatest element ∇.
Meets are easy and joins are not:
Meet — intersection
An arbitrary intersection of equivalence relations is again reflexive, symmetric and transitive. So ⋀i θi is simply the intersection.
Join — transitive closure
The union of two equivalence relations is reflexive and symmetric but almost never transitive. The join is the transitive closure of the union.
Concretely, ⟨a, b⟩ lies in θ ∨ φ exactly when there is a finite chain a = c0, c1, …, cn = b in which consecutive terms are related alternately by θ and φ. Writing ∘ for relational product, this says the join is the union of θ∘φ, θ∘φ∘θ, and so on.
Permutability
Two equivalence relations θ and φ permute if θ ∘ φ = φ ∘ θ.
When θ and φ permute, the alternating chains stabilise immediately and θ ∨ φ = θ ∘ φ. The join becomes a single relational product rather than an infinite union, which is a dramatic simplification.
Groups and rings have the property that all congruences permute. This is why the isomorphism theorems are so clean in those settings, and it is what Mal'cev conditions characterise in general.
Eq(A) as the ambient lattice
Every congruence on an algebra A is in particular an equivalence relation on the universe A. So Con(A) is a subset of Eq(A) — and in fact a complete sublattice with respect to meets, since intersections of congruences are congruences.
Meets in Con(A) agree with meets in Eq(A) — both are intersection. Joins need not agree: the join of two congruences in Con(A) is the smallest congruence containing both, which can be strictly larger than their join as equivalence relations. In practice the two do coincide for many familiar algebras, but the distinction must be kept in mind.
Eq(A) itself is not modular in general. For |A| ≥ 4 it contains copies of N5, which is why congruence lattices of arbitrary algebras can be badly behaved — and why congruence-modular and congruence-distributive varieties are singled out for special treatment.
Frequently asked questions
Which lattices arise as Eq(A) for some set A?
Only the partition lattices themselves. A far more interesting question is which lattices arise as Con(A) for some algebra A — and the answer, by a theorem of Grätzer and Schmidt, is every algebraic lattice.
Is Eq(A) distributive?
No, once A has at least three elements. Partition lattices on larger sets contain both M5 and N5, so they are neither distributive nor modular in general.
Source. S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, The Millennium Edition — a corrected re-typesetting of Springer-Verlag Graduate Texts in Mathematics 78 (1981). Section I.4, book pages 18-19.
This page is an original exposition prepared for the KEVOS® knowledge library. It restates and reorganises mathematical results; it is not a reproduction of the source text.