Lattice Theory Foundations
Closure Operators and Galois Connections
Generated subalgebra, generated congruence, deductive closure, topological closure and span are one construction wearing five hats. Closure operators are that construction.
- Define a closure operator and the associated closure system.
- Prove the correspondence between closure systems and complete lattices.
- Identify finitary closure operators and their link to algebraic lattices.
- Construct the closure operators induced by a Galois connection.
- Recognise the pattern in generated subuniverses and deductive closure.
01Closure operators and closure systems
A closure operator on a set A is a map C from subsets to subsets that is extensive, monotone and idempotent.
| Axiom | Statement | Reading |
|---|---|---|
| Extensive | X ⊆ C(X) | Closure never loses elements. |
| Monotone | X ⊆ Y ⟹ C(X) ⊆ C(Y) | More input, more output. |
| Idempotent | C(C(X)) = C(X) | Closing twice adds nothing. |
A closure system is a family of subsets of A containing A itself and closed under arbitrary intersections. The two notions are equivalent: given a closure operator, its closed sets form a closure system; given a closure system, the closure of X is the intersection of all members containing X.
Ordered by inclusion, a closure system is a complete lattice. Meets are intersections; joins are the closure of the union. The one-sided criterion supplies the joins, so no separate verification is needed. This is the cheapest route to completeness in the entire subject and it is used constantly.
02The finitary case
A closure operator is finitary (or algebraic) when the closure of a set is the union of the closures of its finite subsets.
This is the exact point at which the finitariness of algebraic operations enters the lattice theory. If an element belongs to the subuniverse generated by X, it is produced by a term applied to finitely many members of X, so it belongs to the subuniverse generated by those finitely many. Hence the subuniverse operator is finitary, hence Sub(A) is algebraic.
- input: finitary closure operator C on a set A
- form L = { X ⊆ A : C(X) = X }, ordered by inclusion
- L is a complete lattice: meets are ∩, joins are C(∪)
- the compact elements of L are exactly C(Y) for finite Y ⊆ A
- every closed set is the join of the compacts below it, by finitariness
- therefore L is algebraic
03Where closure operators actually appear
The topological example is the instructive outlier. Topological closure satisfies an extra axiom — preservation of finite unions — that the algebraic examples lack, and it fails the finitariness the algebraic examples possess. The two families of examples are genuinely different specialisations of the same definition.
04Galois connections
A Galois connection between two sets arises from any binary relation. Given R ⊆ A × B, map subsets of A to subsets of B by taking everything R-related to all of X, and symmetrically in the other direction. The two maps are order-reversing, and each composite is a closure operator.
- Start with a relationR ⊆ A × B. No structure is assumed on either side.
- Form the two polaritiesX* = { b ∈ B : ⟨a, b⟩ ∈ R for all a ∈ X } and dually for Y ⊆ B. Both are order-reversing.
- ComposeX ↦ X** is extensive, monotone and idempotent — a closure operator on A. Similarly on B.
- Read off the correspondenceThe closed sets on each side form complete lattices that are dually isomorphic to one another.
Taking R to be the satisfaction relation between algebras and equations gives the Galois connection underlying Birkhoff's HSP theorem: closed sets of equations are equational theories, closed classes of algebras are varieties. Taking R to be incidence between points and lines gives projective geometry. Taking R to be membership between elements and subsets gives the concept lattice of formal concept analysis.
05The equational Galois connection in detail
Fix a type. Let A range over algebras of that type and Σ over sets of equations, with the relation being satisfaction.
The two closure operators are Σ ↦ Id(M(Σ)), which is deductive closure, and K ↦ M(Id(K)), which is the variety generated by K. That the second equals HSP(K) is Birkhoff's theorem; that the first is captured by a finite set of inference rules is the completeness theorem for equational logic. Both live in the Equational stream of this collection.
Frequently asked
Is every complete lattice the lattice of closed sets of a closure operator?
Yes, and trivially so — represent the lattice by its principal ideals. The content is in the refinement: finitary closure operators correspond to algebraic lattices, which is a genuine restriction, since [0, 1] is complete but not algebraic.
What distinguishes topological closure from the algebraic examples?
Topological closure preserves finite unions, which the algebraic operators do not — the subuniverse generated by X ∪ Y is generally much larger than the union of the two generated subuniverses. Conversely the algebraic operators are finitary and topological closure is not. Neither family contains the other.
Do Galois connections always produce closure operators?
Yes, for the antitone form described here: both composites of the two polarities are always extensive, monotone and idempotent, and this requires no hypotheses on the relation. The monotone form, sometimes called an adjunction, produces a closure operator on one side and an interior operator on the other.
- 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.