Galois connection
In mathematics, a Galois connection is a particular correspondence between two partially ordered sets. Galois connections generalize the correspondence between subgroups and subfields established by the fundamental theorem of Galois theory. They find applications in various mathematical theories as well as in the theory of programming.
Definition
Suppose (A, ≤) and (B, <=) are two partially ordered sets. A Galois connection between these posets consists of two functions: F : A → B and G : B → A, such that for all a in A and b in B, we have
- F(a) <= b if and only if a ≤ G(b).
F is also called the left or lower adjoint and G is called the right or upper adjoint of the connection.
Examples
The motivating example comes from Galois theory: suppose L/K is a field extension. Let A be the set of all subfields of L that contain K, ordered by inclusion ⊆. If E is such a subfield, write Gal(L/E) for the group of field automorphisms of L that hold E fixed. Let B be the set of subgroups of Gal(L/K), ordered by containment ⊇. For such a subgroup G, define Fix(G) to be the field consisting of all elements of L that are held fixed by all elements of G. Then the maps E |-> Gal(L/E) and G |-> Fix(G) form a Galois connection.
For the second example, let U be some set, and let A and B be the power set of U, ordered by inclusion. Pick a fixed subset L of U. Then the maps F(M) = L ∩ M and G(N) = N ∪ (U \ L) form a Galois connection.
Now suppose X and Y are sets and a binary relation R over X and Y is given. For any subset M of X, we define F(M) = { y in Y : mRy for all m in M}. Similarly, for any subset N of Y, define G(N) = { x in X : xRn for all n in N}. Then F and G yield a Galois connection between the power sets of X and Y, if the power set of X is ordered by inclusion ⊆ and the power set of Y is ordered by containment ⊇.
Properties
If F and G provide a Galois connection, then both F and G are monotonic functions, i.e. a1 ≤ a2 implies F(a1) <= F(a2) and b1 <= b2 implies G(b1) ≤ G(b2).
Furthermore, we have a≤G(F(a)) and F(G(b)) <= b for all a in A and b in B.
For every a, F(a) is the least x such that a≤G(x). For every b, G(b) is the largest y such that F(y) <= b.
This latter statement shows that a monotonic function F : A → B is the lower adjoint of a Galois connection if and only if for every b in B, the set {y in A : F(y) <= b} has a largest element. If this is the case, then the upper adjoint G is uniquely determined by F.
If F and G form a Galois connection, we have FGF(a) = F(a) for every a in A and GFG(b) = G(b) for every b in B. Ab element a in A is called closed if a = G(F(a)), or equivalently, if a is in the range of G. Closed elements of B are defined analogously. F and G induce inverse monotonic bijections between the sets of closed elements in A and the set of closed elements in B.
Category theoretic approach
Every partially ordered set can be viewed as a category in a natural way. A Galois connection is then nothing but a pair of adjoint functors between categories arising from partially ordered sets.
References
- Garrett Birkhoff: Lattice Theory, Amer. Math. Soc. Coll. Pub., Vol 25, 1940
- Oystein Ore: Galois
Connexions, Transactions of the American Mathematical Society 55 (1944), pp. 493-513