Galois connection

In mathematics, especially in order theory, a Galois connection is a particular correspondence between two partially ordered sets ("posets"). 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.

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 $subseteq$. 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 $subseteq$. 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 and G, where F(M) is the intersection of L and M, and G(N) is the union of N and (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 $wedge$ x) and G(y) = (y $eg$ a) = (a $Rightarrow$ y). In logical terms: "implication" is the upper adjoint of "conjunction".
• Further interesting examples for Galois connections are described in the article on completeness properties. It turns out that the usual functions and $wedge$ are adjoints in two suitable Galois connections. The same is true for the mappings from the one element set that point out the least and greatest elements of a partial order. Going further, even complete lattices can be characterized by the existence of suitable adjoints. These considerations give some impression of the ubiquity of Galois connections in order theory.
• 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 ordered by inclusion $subseteq$, and let B be the set of all subsets of Kⁿ ordered by inclusion $subseteq$. 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 : 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 $subseteq$. Interestingly, there is another adjoint pair in this situation: for a subset M of X, define H(M) = {y$in$Y : f ^-1({y}) $subseteq$ 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 $subseteq$.