Galois connection

A Galois connection is rather weaker than an isomorphism between the involved posets, but every Galois connection gives rise to an isomorphism of certain sub-posets, as will be explained below.

Definition

Suppose (A, ≤) and (B, <=) are two partially ordered sets. A Galois connection between these posets consists of two monotone 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).

In this situation, F is called the lower adjoint of G and G is called the upper adjoint of F. This terminology relates to the connections to category theory discussed below.

Alternative Definition

The above definition is common in many applications today, and prominent in lattice and domain theory. However, a slightly different notion has originally been derived in Galois theory. In this alternative definition, a Galois connection is a pair of antitone, i.e. order-reversing, functions F : A → B and G : B → A between two posets A and B, such that

F(a) <= b if and only if G(b) ≤ a.

Both notions of a Galois connection are still present in the literature. In Wikipedia the term (monotone) Galois connection will always refer to a Galois connection in the former sense. If the alternative definition is applied, the term antitone Galois connection or order-reversing Galois connection is used.

The implications of both definitions are in fact very similar, since an antitone Galois connection between A and B is just a monotone Galois connection between A and the order dual B^op of B. All of the below statements on Galois connections can thus easily be converted into statements about antitone Galois connections.

Note however that for an antitone Galois connection, it does not make sense to talk about the lower and upper adjoint: the situation is completely symmetrical.

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 inclusoin ⊆. 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 an antitone Galois connection.

• For an order theoretic 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 monotone Galois connection, with F being the lower adjoint. A similar Galois connection whose lower adjoint is given by the meet (infimum) operation can be found in any Heyting algebra. Especially, it is present in any Boolean algebra, where the two mappings can be described by F(x) = a ∧ x and G(y) = y ∨ ¬ a = a ⇒ y. In logical terms: "implication" is the upper adjoint of "and".

• In algebraic geometry, the relation between sets of polynomials and their zero sets is an antitone 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] ordered by inclusion ⊆, and let B be the set of all subsets of Kⁿ 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 an antitone Galois connection.

• If f : X → Y is a function, then for any subset M of X we can form the image F(M) = f(M) = {f(m) : m in M} and for any subset N of Y we can form the inverse image G(N) = f ^-1(N) = {x in X : f(x) in N}. Then F and G form a monotone Galois connection between the power set of X and the power set of Y, both ordered by inclusion ⊆. Interestingly, there is another adjoint pair in this situation: for a subset M of X, define H(M) = {y in Y : f ^-1({y}) ⊆ M}. Then G and H form a monotone Galois connection between the power set of Y and the power set of X. In the first Galois connection, G is the upper adjoint, while in the second Galois connection it serves as the lower adjoint.

• Pick some mathematical object X that has an underlying set, for instance a group, ring, vector space, etc. For any subset S of X, let F(S) be the smallest subobject of X that contains S, i.e. the subgroup, subring or subspace generated by S. For any subobject U of X, let G(U) be the underlying set of U. (We can even take X to be a topological space, let F(S) the closure of S, and take as "subobjects of X" the closed subsets of X.) Now F and G form a monotone Galois connection if the sets and subobjects are ordered by inclusion. F is the lower adjoint.

• A very general comment of Martin Hyland is that syntax and semantics are adjoint: take A to be the set of all logical theories (axiomatizations), and B the power set of the set of all mathematical structures. For a theory T in A, let F(T) be the set of all structures that satisfy the axioms T; for a set of mathematical structures S, let G(S) be the minimal axiomatization of S. We can then say that F(T) is a subset of S if and only if T logically implies G(S): the "semantics functor" F and the "syntax functor" G form a monotone Galois connection, with semantics being the lower adjoint.

• 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 an antitone Galois connection between the power sets of X and Y, both ordered by inclusion ⊆.

Properties

Here we assume that F : A → B is the lower adjoint and G : B → A is the upper adjoint of a monotone Galois connection between (A,≤) and (B,<=).

The upper adjoint G preserves infima (meets) of arbitrary subsets of B, and the lower adjoint F preserves suprema (joins) of arbitrary subsets of A.

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 forms 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: it just picks out this largest element.

In particular, this shows that if A is a complete lattice, then a function F : A → B forms the lower adjoint of a Galois connection if and only if F transforms suprema into suprema.

Importantly, every Galois connection gives rise to a closure operator and a corresponding notion of "closed elements" in A and B. F and G induce inverse monotone bijections between these sets of closed elements. The details: We have FGF(a) = F(a) for every a in A and GFG(b) = G(b) for every b in B. We can use this to show that GF has the formal properties of a closure operator on A, and FG is a closure operator on 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. So F maps the closed elements of A to the closed elements of B, and G maps the closed elements of B to those of A. These two maps are monotone and inverse to each other.

Galois connection can be composed: if (F,G) is a Galois connection between the posets A and B, and (H,K) is a Galois connection between B and C, then (HoF,KoG) is a Galois connection between A and C (the lower adjoints are composed to yield the new lower adjoint, the upper adjoints are composed to yield the new upper adjoint).

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 that arise from partially ordered sets. In this context, the upper adjoint is the right adjoint while the lower adjoint is the left adjoint. However, this terminology is avoided for Galois connections, since there has been a time when posets where transformed into categories in a dual fashion, i.e. with arrows pointing in the opposite direction. This led to a complementary notation concering left and right adjoints, which today is ambiguous.

Applications in the theory of programming

still missing

References

• B. A. Davey and H. A. Priestley: Introduction to lattices and Order, Cambridge University Press, 2002.
• G. Gierz, K. H. Hoffmann, K. Keimel, J. D. Lawson, M. Mislove, D. S. Scott: Continuous Lattices and Domains, Cambridge University Press, 2003.
• 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

Referenced By