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 investigated in Galois theory. They find applications in various mathematical theories as well as in the theory of programming.

Table of contents 1 Definition 2 Examples 3 Properties 4 Category theoretic approach 5 References

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 G(b) ≤ a.

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 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₁,...,X_n] and let B be the set of all subsets of Kⁿ. Both A and B are naturally ordered by inclusion ⊆. If S is a set of polynomials, define F(S) = {x in Kⁿ : 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ⁿ, define G(T) = {f in K[X₁,...,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 ⊆.

Properties

If F and G provide a Galois connection, then both F and G are order reversing functions, i.e. a₁ ≤ a₂ implies F(a₂) <= F(a₁) and b₁ <= b₂ implies G(b₂) ≤ G(b₁).

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.

Category theoretic approach

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.

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