
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
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 inclusion ⊆. 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.
In algebraic geometry, the relation between sets of polynomials and their zero sets is a Galois connection: fix a natural number n and a field K and let A be the set of all subsets of the polynomial ring K[X_{1},...,X_{n}] and let B be the set of all subsets of K^{n}. Both A and B are naturally ordered by inclusion ⊆. If S is a set of polynomials, define F(S) = {x in K^{n} : f(x) = 0 for all f in S}, the set of common zeros of the polynomials in S. If T is a subset of K^{n}, define G(T) = {f in K[X_{1},...,X_{n}] : f(x) = 0 for all x in T}. Then F and G form a Galois connection.
Finally, suppose X and Y are arbitrary 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 both of them are ordered by inclusion ⊆.
If F and G provide a Galois connection, then both F and G are order reversing functions, i.e. a_{1} ≤ a_{2} implies F(a_{2}) <= F(a_{1}) and b_{1} <= b_{2} implies G(b_{2}) ≤ G(b_{1}).
Furthermore, we have G(F(a)) ≤ a and F(G(b)) <= b for all a in A and b in B.
For every a, F(a) is the largest x such that G(x) ≤ a. Similarly, for every b, G(b) is the largest y such that F(y) <= b.
This latter statement shows that an order reversing function F : A → B forms part 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 "other half of the Galois connection" 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. An 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 order reversing bijections between the set of closed elements in A and the set of closed elements in B.
Every partially ordered set can be viewed as a category in a natural way: there's a unique morphism from x to y iff x ≤ y. A Galois connection is then nothing but a pair of adjoint functors between two categories, where the first category arises from a partially ordered set and the second category is the dual of one that arises from a partially ordered set.
Search Encyclopedia

Featured Article
