The Unapologetic Mathematician

Galois Connections

I want to mention a topic I thought I’d hit back when we talked about adjoint functors. We know that every poset is a category, with the elements as objects and a single arrow from $a$ to $b$ if $a\leq b$. Functors between such categories are monotone functions, preserving the order. Contravariant functors are so-called “antitone” functions, which reverse the order, but the same abstract nonsense as usual tells us this is just a monotone function to the “opposite” poset with the order reversed.

So let’s consider an adjoint pair $F\dashv G$ of such functors. This means there is a natural isomorphism between $\hom(F(a),b)$ and $\hom(a,G(b))$. But each of these hom-sets is either empty (if $a\not\leq b$) or a singleton (if $a\leq b$). So the adjunction between $F$ and $G$ means that $F(a)\leq b$ if and only if $a\leq G(b)$. The analogous condition for an antitone adjoint pair is that $b\leq F(a)$ if and only if $a\leq G(b)$.

There are some immediate consequences to having a Galois connection, which are connected to properties of adjoints. First off, we know that $a\leq G(F(a))$ and $F(G(b))\leq b$. This essentially expresses the unit and counit of the adjunction. For the antitone version, let’s show the analogous statement more directly: we know that $F(a)\leq F(a)$, so the adjoint condition says that $a\leq G(F(a))$. Similarly, $b\leq F(G(b))$. This second condition is backwards because we’re reversing the order on one of the posets.

Using the unit and the counit of an adjunction, we found a certain quasi-inverse relation between some natural transformations on functors. For our purposes, we observe that since $a\leq G(F(a))$ we have the special case $G(b)\leq G(F(G(b)))$. But $F(G(b))\leq b$, and $G$ preserves the order. Thus $G(F(G(b)))\leq G(b)$. So $G(b)=G(F(G(b)))$. Similarly, we find that $F(G(F(a)))=F(a)$, which holds for both monotone and antitone Galois connections.

Chasing special cases further, we find that $G(F(G(F(a))))=G(F(a))$, and that $F(G(F(G(b))))=F(G(b))$ for either kind of Galois connection. That is, $F\circ G$ and $G\circ F$ are idempotent functions. In general categories, the composition of two adjoint functors gives a monad, and this idempotence is just the analogue in our particular categories. In particular, these functions behave like closure operators, but for the fact that general posets don’t have joins or bottom elements to preserve in the third and fourth Kuratowski axioms.

And so elements left fixed by $G\circ F$ (or $F\circ G$) are called “closed” elements of the poset. The images of $F$ and $G$ consist of such closed elements

May 18, 2009