Some theory
Let and be two partially ordered sets (posets). Two functions and are said to form a Galois connection when the following is true for all and all : We say that is the lower (or left) adjoint, and is the upper (or right) adjoint. Oftentimes the lower adjoint is marked with a lower-star and the upper adjoint with an upper-star . We will see for instance that the direct and inverse image form such a connection, and this hopefully explains the usual notation for these concepts. The shorthand I’m going to use for saying two functions are in Galois connection is .
In some sense, this says is the best approximation of from above using objects of with respect to , and is the best approximation of from below using objects of with respect to . Don’t worry if this is unclear (it is I’m sure).
Some examples
Three-way connection: direct image, inverse image, image in fibers
Let be any set function. The direct image is the function defined as The inverse image is the function defined as These functions form a Galois connection . The direct image is left adjoint to the inverse image, and reciprocally the inverse image is the right adjoint to the direct image. The use of “the” in the previous sentence will be explained below, where I show that the left or right adjoint, if it exists, is uniquely determined.
Here’s a more interesting example! We now construct a right adjoint to the inverse image. That’s not something you see often! Given a set function , we define the image in fibers to be the function with the equation It’s the set of points such that their fiber is contained in . It’s an interesting construction. Notice for instance that any point that is not in the image of has an empty fiber, hence is an element of . Let’s prove that there is a connection . First, suppose . In this context we want to show that , so pick any element . We just have to show , which is the case because our hypothesis says every element of has its preimage contained in , so we’re done. Second, suppose , and let’s show that as a consequence . Pick any element , so . Hence by hypothesis. This means , and since is an element of we are done.
Linear algebra: span
Let be some vector space. Given a collection of vectors of , their span is the smallest vector space which contains all vectors in . It is denoted by . That’s a well-defined operation that produces a function , where is the set of subspaces of , partially ordered by inclusion. There’s also a “forgetful” function that goes the other way and produces the set of vectors underlying a given subspace of . These two functions are in Galois connection, with the span being left adjoint to the forgetful function.
Algebraic geometry: the vanishing set
Here’s another example which is close to my heart. Consider the ring of polynomials in the variables and , with coefficients in . Of course we could generalize the base field and the number of variables, but let’s keep it simple and fun since the generalization is obvious. For a set of polynomial, we define their vanishing set to be the subset of points of where they all vanish: Reciprocally, given a subset , we define the set consisting of the polynomials that vanish at all points of : If we order the subsets of by “reverse containement”, we obtain a connection , which formally expresses the idea that being “algebraically small” is the same as being “geometrically big”, and vice-versa. In other words, the smaller a geometric place is, the more constraints (that’s the algebra part) are needed to specify it.
Closure in topology
Now for a purely topological example. Consider a topological space, and partially order its closed subsets by containement. Name the set of closed subsets . The closure is the function that sends any subset of to , the smallest closed subset that contains . There’s also a “forgetful” function that sends a closed subset to itself. The claim here is that the closure is left adjoint to the forgetful function.
Do you see the similarity between this example and the one about the span in vector spaces? It’s this kind of abstract correspondence that a Galois connection expresses.
More theory
The composite is called the closure operator, and composition the other way around is called the kernel operator. A connection is called a Galois insertion if the kernel operator is the identity map. Consider the last example where we used the closure of a set in a topological space. Here the closure operator is literally the closure, while the kernel operator is the identity, so we have a Galois insertion. The span example is also a Galois insertion.
Because we always have , the condition (C) says we always have (just set ). Similarily, we always have . Also notice that if and are in connection, then and are necessarily monotone. For instance, take and two elements of with . Then , hence . For instance, this gives us for free that the direct and inverse image constructions are monotone, and we always have:
- for any
- for any
But also:
- for any
- for any
- for any (that’s actually part of the definition of the span)
- for any
- for any
While we’re at it, notice what happens if we replace by in the equation . (Here and are two general functions in connection, not necessarily the direct/inverse image pair). We get , and that’s true for every . On the other hand, it’s also true for every that , by what we said above. Because is monotone, we obtain . From antisymmetry of our order relation, we conclude In other words, for every the element is a fixed point for the closure operator. Similarily, for every the element is a fixed point for the kernel operator.
Even more theory
If you stare long enough at condition (C) above, after a while you’ll understand suddenly and all at once that it is precisely the data of two equations. First, it gives a definition of the upper adjoint in terms of the lower adjoint: Second, it gives a definition of the lower adjoint in terms of the upper adjoint:
A striking consequence of the previous equations is that two functions in connection mutually define each other. Hence an adjoint to some given function, if it exists, is unique. Another sizeable consequence: if a function is such that, for some , the set does not have a maximum element, then cannot have a right adjoint. A similar remark applies to a function , which would then have no left adjoint if no minimum exists for a given .
When we considered the direct image of a set function , we explicitely built a right adjoint for it: it was the inverse image . Now we can give a new characterization of the inverse image in terms of the direct image, using the previous formulas: for any , In other words, the inverse image of a set is the biggest subset of such that its image is contained in . That’s really nice. We can also play the same game and characterize the direct image in terms of the inverse image: the direct image of a set is the smallest subset of such that its inverse image contains . Hence it seems lower adjoints can be thought of as supremums, approximating from above, while upper adjoints behave as infimums, approximating from below.
Since we have a three-way connection , one could reasonably ask if it’s possible to extend it further. Let’s ask the first obvious question: is there a left adjoint to ? It would necessarily be given, for each , by the minimum of the set . Suppose is not surjective. Then there is some point which is not contained in the image of . For a left adjoint to to be defined, it would have to spit out, when evaluated at , the minimum of , but this set is empty since is not in the image of . Therefore the left adjoint cannot exist when is not surjective. Well, what if is surjective? After thinking about this for a while, I realized we need another disjunction here. Suppose is not injective. Take two distincts elements and in with . Set . If a left adjoint to were to exist, it would have to be defined at as the minimum of the set . Clearly both and are elements of this set; hence, if there was a minimum element, it would have to be contained in both and , which would make it the empty set. However, the empty set fails to verify . So the left adjoint cannot exist in this case either. Since it trivially exists when is bijective (it’s ), we conclude: the direct image admits a left adjoint if and only if is bijective.
The next obvious question on this matter is: does the image in fibers admit a right adjoint? From the previous paragraph our expectations are: if and only if is bijective. Let’s see if that’s really the case. In fact, when is bijective we have , so by unicity of right adjoints we already know that the right adjoint of , if it exists, has got to be , which it is. So imagine is not bijective. First case: suppose it is not surjective. Then contains all which are not contained in the image of , since their fibers are all empty. Hence by taking to be any subset of completely contained in the image of , we find that the set is empty; in particular it has no maximum element, so the right adjoint does not exist. Second case: suppose is not injective. Without loss of generality we may suppose is surjective, so that the fiber of any point in is never empty. Pick some point with at least two distinct preimages and partition into two disjoint non-empty subsets: . If the right adjoint were to exist, its value at the empty set would have to be the maximum element of the set . Quick scribling on napkin paper is able to show that both and are contained in this set, but their union is not. Hence it is necessary that be bijective for to admit a right adjoint.
We have seen that the inverse image is quite special because it is the only one having both a left and a right adjoint in general. This is reflected in the nice properties the inverse image admits, for instance it preserves unions and intersections of subsets. We will see momentarily that this fact is an instance of a general fact about Galois connections (and even more generally about adjunctions).
When will this theory ever end?
I want to end on the general note that left adjoints preserve joins and right adjoints preserve meets. This is a special case of a more general theorem that left adjoints (in a more general sense) preserve colimits while right adjoints preserve limits.
Suppose are functions in Galois connection, with . Suppose also that and are not only posets but also lattices (i.e. every pair of elements has an infimum and a supremum). Fix and two elements of . Because is necessarily monotone, we must have and . Hence is an upper bound for the pair , . Now we show that this is not only an upper bound, it’s actually the least upper bound. Let be any other upper bound, that is, and . By the Galois connection condition we must have and . Then is an upper bound for the pair , whence . But now by the connection condition again, we must have , which is what we wanted. Therefore . A dual argument shows that for any pair of elements , in .
Let’s return to our example of three-way connection between the direct image, the inverse image and the image in fibers for any set function . What we can conclude from the previous paragraph is: the inverse image is very special, for it preserves both unions and intersections, being a right and left adjoint at the same time. The direct image only preserves unions in general, while the image in fibers only preserves intersections.