Not all problem statements are amenable to translation via Galois connections or adjunctions. A reasonable characterization of those that are suitable is the *optimization problems*—finding the *least or greatest solution* satisfying a given collection of constraints, according to some ordering.

## Least and greatest solutions

For example, the Galois connection determining integer division that we considered a couple of posts ago

defines to be the greatest solution to the equation . It does so in a very pithy way: reading the equivalence as an implication from left to right, instantiating to (and exploiting the reflexivity of the ordering ), we get that , so is indeed a solution to the equation on the right; reading the equivalence from right to left, we get that for any solution , so is in fact the greatest solution.

Similarly, the characterization of the floor function from reals to integers

defines as the greatest integer for which , and the Galois connection involving and

characterizes as the greatest set (under the usual subset ordering) for which .

## Limits and colimits

The characterization of greatest solutions might be equivalently expressed in terms of *greatest lower bounds*. Given a preordered set , and a subset of , an element is a *lower bound* of in if for every ; in addition, is a *greatest lower bound* of if for any other lower bound . (Note “a” rather than “the”, as there may be multiple such. But they are all related by ; if the ordering is a partial order, the is unique when it exists. Note also that need not be in itself, even when it does exist.)

This construction can be phrased in terms of Galois connections as follows. The two ordered sets are and , where is the set of *nonempty* subsets of , with ordering defined pointwise: iff for all . The mappings in either direction are the singleton set former and greatest lower bound , related by the Galois connection . Here’s how it looks with and :

The categorical perspective on greatest lower bounds is the notion of *limit*; it’s just the generalization of the diagram above to an arbitrary category. Here is a very brief outline. The fragment of the diagram consisting of is called a *cone*, from vertex to base (and so is ). The cone is called a *limit* when, for any other cone from vertex to the same base, there is a unique arrow making the diagram commute.

Commutativity of the diagram above isn’t very interesting—because the category is a partial order, but also because the base is degenerate: just three discrete objects. In general, the base will also contain arrows; then a cone consists of a vertex ( in the diagram below) with arrows to each of the objects in the base () making the diagram commute (, etc). As before, the cone from vertex is a limit if any other cone factors uniquely through it.

Of course, it all dualizes beautifully. The categorical perspective on least upper bounds is expressed in terms of cones *from* a base ( below) to a vertex (), being a *colimit* if allowing unique factorization for any other cone from the same base to another vertex ().

## Initial algebras and final coalgebras

Recall that, for a functor , an *-algebra* is a pair consisting of an object and an arrow . A *homomorphism* between -algebras and is an arrow such that:

The -algebra is *initial* if there is a unique such for each . We usually write for the “carrier” of this initial algebra (because it is the “least fixed point” of , as we shall see below), and for the “constructor” (and indeed, it is an isomorphism, so a constructed piece of data can be deconstructed again); we write for the unique such that .

As you might expect, “initial” things are extreme solutions too, albeit not in a very interesting way. An *initial object* in a category is an object from which there is a unique arrow (often written ““) to any other object. An initial object is a colimit of the diagram generated from the empty category—which has no objects, and hence no arrows either. (Any object forms the vertex of a (trivial) cone, so the colimiting vertex is simply one from which there is a unique arrow to any other vertex, with no additional constraints.) In particular, an initial -algebra is an initial object in the category of -algebras, whose objects are -algebras and whose arrows are homomorphisms between them.

And of course, it all dualizes nicely, to final coalgebras, which are in some sense “greatest fixed points” of functors; final objects are the vertices of limiting cones *to* the empty base.

## Extreme (co-)algebras as (co-)limits

Here is a more illuminating presentation of initial algebras as extreme solutions, explaining rather better in what way they correspond to “least fixed points” of functors. (The construction is well known; I’ve based this presentation on a manuscript by François Métayer.) Initial algebras can be constructed as an instance of the colimit construction above, in which the base consists of a *countable chain* of objects and arrows:

In the category , every such a chain has a colimit (categories with this property are called *-categories*).

If the category has an *initial object* , then any endofunctor induces such a countable chain:

Under mild assumptions, the colimit of this chain is (the carrier of) an initial -algebra. (Besides assuming an -category with an initial object, we have to assume that is *-cocontinuous*—that is, that it transforms the colimit of the countable chain into a colimit of the countable chain . One can show that any *polynomial functor*—one built from constants using sum and product—is -cocontinuous.)

The construction goes as follows. By assumption, the countable chain has a colimit; let’s suggestively call the vertex , so that the edges satisfy for each .

Since is -cocontinuous, it transforms this diagram into another colimiting cone, with base shifted one place to the right and vertex . But is the vertex of another cone over the same shifted base; and since is the colimit, there is a unique arrow—let’s suggestively call it —making the diagram below commute ( etc).

All we have to do now is to show that is indeed the initial -algebra, as claimed. Suppose we are given another -algebra ; we will (i)~construct an arrow , (ii)~show that it is a homomorphism between the algebras, , and (iii)~show that it is the only such.

For (i), given the target -algebra , we can construct a square as follows:

which commutes by virtue of the initiality of . Applying to this square yields another, which can be pasted alongside; and this can be repeated indefinitely, yielding the following ladder:

Then we can pick out arrows . Moreover, these s commute with the base of the colimit diagram (, etc) to yield another cone to vertex ; we therefore conclude that there is a unique such that for each .

Now for (ii). Note that and the also form a cone over the shifted base starting from ; and because is the colimit from this shifted base, we also get a unique mediating arrow such that for each .

Moreover, both and are also such mediating arrows:

so both must equal and hence also each other: .

Finally, for (iii), suppose we have another for which ; we have to show that . By the uniqueness of the mediating arrow, it suffices to show that for each , which is easily done by induction.

That is, given -algebra , there exists a unique (for which we write ““) such that . If you squint at this in the right way, you can see the inductive definition of the recursive datatype, and of the folds over it. Each is an approximation to , cut off at depth ; they all embed into , and indeed, is the least extension—the colimit—of them all. Each is an approximation to , again restricted to data structures cut off at depth , and is the completion of all the .

Naturally, it all dualizes for final coalgebras: then we need “cochains” to a terminal object ; an -category is one in which all such countable cochains have a limit; -continuous functors preserve limits of countable cochains. (It is a bit unfortunate that the interesting extreme algebra, namely the initial algebra, is a *co*limit, whereas the final *co*algebra is a limit, but sometimes life is like that.)

## (Co-)limits as adjunctions

The definition of limits can be made more concise and precise by noting that the base corresponds to the image of some functor , where is the category of interest, and *index category* determines the shape of the base—for each object of , there is an object of in the base ( in the diagram below), and for each arrow of , an arrow of in the base ( below).

(In the diagram, the index category is the discrete category on three objects—with no arrows other than identity arrows. In the diagram above, is , with three objects and two generating arrows. In the construction of initial algebras, the index category is , equivalent to the usual ordering on the natural numbers, whereas for final coalgebras it is , equivalent to on natural numbers.)

The vertex too can be seen as the image of under a particular, degenerate functor—the diagonal functor , defined by for each object of , and for each arrow . Then “the cone from vertex to base ” corresponds to a natural transformation : naturality is exactly the condition that the cone commutes. We write “” for the limiting object, ; its universal property is that, for any cone from to , there exists a unique such that for each . In other words, there is a (natural) isomorphism between the natural transformations and the arrows ; that is, an adjunction , with limit being right adjoint to the diagonal.

Dually, of course, colimits turn out to be left adjoints: the whole construction is encapsulated in three symbols, .

The last image (extreme-adjn.png) doesn’t show up: 404.

Oops – you’re right, thanks. Fixed now.

I’ve mulled limits and colimits multiple times; your perspicuous, sinewy exposition has finally nailed them for me. Much obliged.

That’s very kind of you – you’re most welcome.

I’ve been really enjoying this series of posts so far (although I’m going to have to print this one out and pore over it while scribbling notes to myself!). I’ve seen some of this before in various forms but, like rich, this is making it gel for me in a new way. I look forward to reading more.

Pingback: Morality and temptation | Patterns in Functional Programming