Table of contents |
2 Examples 3 Properties 4 Category theoretic approach 5 References |
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[X1,...,Xn] and let B be the set of all subsets of Kn. Both A and B are naturally ordered by inclusion ⊆. If S is a set of polynomials, define F(S) = {x in Kn : f(x) = 0 for all f in S}, the set of common zeros of the polynomials in S. If T is a subset of Kn, define G(T) = {f in K[X1,...,Xn] : 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. a1 ≤ a2 implies F(a2) <= F(a1) and b1 <= b2 implies G(b2) ≤ G(b1).
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.Definition
Examples
Properties
Category theoretic approach