Extreme solutions

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

$\displaystyle n \div k \ge m \Leftrightarrow n \ge m \times k$

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

Similarly, the characterization of the floor function ${\lfloor\cdot\rfloor}$ from reals to integers

$\displaystyle \mathit{inj}(n) \le_R x \Leftrightarrow n \le_I \lfloor x \rfloor$

defines ${\lfloor x \rfloor}$ as the greatest integer ${n}$ for which ${\mathit{inj}(n) \le_R x}$ , and the Galois connection involving ${\cap}$ and ${\cup}$

$\displaystyle A \cap X \subseteq B \Leftrightarrow A \subseteq B \cup \overline{X}$

characterizes ${B \cup \overline{X}}$ as the greatest set ${A}$ (under the usual subset ordering) for which ${A \cap X \subseteq B}$ .

Limits and colimits

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

This construction can be phrased in terms of Galois connections as follows. The two ordered sets are ${(X,\le)}$ and ${(\mathsf{P}^+(X),\le^\ast)}$ , where ${\mathsf{P}^+(X)}$ is the set of nonempty subsets of ${X}$ , with ordering ${\le^\ast}$ defined pointwise: ${Y \le^\ast Z}$ iff ${x \le x'}$ for all ${x \in Y, x' \in Z}$ . The mappings in either direction are the singleton set former ${\{\cdot\} : X \rightarrow \mathsf{P}^+(X)}$ and greatest lower bound ${\mathrm{inf} : \mathsf{P}^+(X) \rightarrow X}$ , related by the Galois connection ${x \le \mathrm{inf}(Y) \Leftrightarrow \{x\} \le^\ast Y}$ . Here’s how it looks with ${x' \le x = \mathrm{inf}(Y)}$ and ${Y = \{ x_0,x_1,x_2 \}}$ :

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 ${x, x_0, x_1, x_2}$ is called a cone, from vertex ${x}$ to base ${x_0,x_1,x_2}$ (and so is ${x',x_0,x_1,x_2}$ ). The cone ${x,x_0,x_1,x_2}$ is called a limit when, for any other cone from vertex ${x'}$ to the same base, there is a unique arrow ${x' \rightarrow x}$ 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 ( ${X}$ in the diagram below) with arrows to each of the objects in the base ( ${f_i : X \rightarrow X_i}$ ) making the diagram commute ( ${g_0 \cdot f_0 = f_1}$ , etc). As before, the cone from vertex ${X}$ 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 ( ${X_0,X_1,X_2}$ below) to a vertex ( ${X}$ ), being a colimit if allowing unique factorization for any other cone from the same base to another vertex ( ${X'}$ ).

Initial algebras and final coalgebras

Recall that, for a functor ${\mathsf{F}}$ , an ${\mathsf{F}}$ -algebra is a pair ${(X,f)}$ consisting of an object ${X}$ and an arrow ${f : \mathsf{F}(X) \rightarrow X}$ . A homomorphism between ${\mathsf{F}}$ -algebras ${(X,f)}$ and ${(Y,g)}$ is an arrow ${h : X \rightarrow Y}$ such that:

The ${\mathsf{F}}$ -algebra ${(X,f)}$ is initial if there is a unique such ${h}$ for each ${(Y,g)}$ . We usually write ${\mu\mathsf{F}}$ for the “carrier” of this initial algebra (because it is the “least fixed point” of ${\mathsf{F}}$ , as we shall see below), and ${\mathit{in} : \mathsf{F}(\mu\mathsf{F}) \rightarrow \mu\mathsf{F}}$ for the “constructor” (and indeed, it is an isomorphism, so a constructed piece of data can be deconstructed again); we write ${h=\mathit{fold}(g)}$ for the unique ${h}$ such that ${h \cdot \mathit{in} = g \cdot \mathsf{F}(h)}$ .

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 ${\mathsf{F}}$ -algebra is an initial object in the category of ${\mathsf{F}}$ -algebras, whose objects are ${\mathsf{F}}$ -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 ${\mathbb{S}\mathrm{et}}$ , every such a chain has a colimit (categories with this property are called ${\omega}$ -categories).

If the category has an initial object ${0}$ , then any endofunctor ${\mathsf{F}}$ induces such a countable chain:

Under mild assumptions, the colimit of this chain is (the carrier of) an initial ${\mathsf{F}}$ -algebra. (Besides assuming an ${\omega}$ -category with an initial object, we have to assume that ${\mathsf{F}}$ is ${\omega}$ -cocontinuous—that is, that it transforms the colimit ${X}$ of the countable chain ${X_0 \rightarrow X_1 \rightarrow \cdots}$ into a colimit ${\mathsf{F}(X)}$ of the countable chain ${\mathsf{F}(X_0) \rightarrow \mathsf{F}(X_1) \rightarrow \cdots}$ . One can show that any polynomial functor—one built from constants using sum and product—is ${\omega}$ -cocontinuous.)

The construction goes as follows. By assumption, the countable chain ${0 \rightarrow \mathsf{F}(0) \rightarrow \cdots}$ has a colimit; let’s suggestively call the vertex ${\mu \mathsf{F}}$ , so that the edges ${u_i : \mathsf{F}^i(0) \rightarrow \mu\mathsf{F}}$ satisfy ${u_{i+1} \cdot \mathsf{F}^i(!) = u_i}$ for each ${i}$ .

Since ${\mathsf{F}}$ is ${\omega}$ -cocontinuous, it transforms this diagram into another colimiting cone, with base shifted one place to the right and vertex ${\mathsf{F}(\mu \mathsf{F})}$ . But ${\mu \mathsf{F}}$ is the vertex of another cone over the same shifted base; and since ${\mathsf{F}(\mu \mathsf{F})}$ is the colimit, there is a unique arrow—let’s suggestively call it ${\mathit{in}}$ —making the diagram below commute ( ${\mathit{in} \cdot \mathsf{F}(u_i) = u_{i+1}}$ etc).

All we have to do now is to show that ${(\mu\mathsf{F}, \mathit{in})}$ is indeed the initial ${\mathsf{F}}$ -algebra, as claimed. Suppose we are given another ${\mathsf{F}}$ -algebra ${(Y,g)}$ ; we will (i)~construct an arrow ${h : \mu\mathsf{F} \rightarrow Y}$ , (ii)~show that it is a homomorphism between the algebras, ${h \cdot \mathit{in} = g \cdot \mathsf{F}(h)}$ , and (iii)~show that it is the only such.

For (i), given the target ${\mathsf{F}}$ -algebra ${(Y,g)}$ , we can construct a square as follows:

which commutes by virtue of the initiality of ${0}$ . Applying ${\mathsf{F}}$ 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 ${\xi_i = \mathsf{F}^0(g) \cdot \mathsf{F}^1(g) \cdots \mathsf{F}^{i-1}(g) \cdot \mathsf{F}^i(!_Y) : \mathsf{F}^i(0) \rightarrow Y}$ . Moreover, these ${\xi_i}$ s commute with the base of the colimit diagram ( ${\xi_{i+1} \cdot \mathsf{F}^i(!) = \xi_i}$ , etc) to yield another cone to vertex ${Y}$ ; we therefore conclude that there is a unique ${h : \mu\mathsf{F} \rightarrow Y}$ such that ${h \cdot u_i = \xi_i}$ for each ${i}$ .

Now for (ii). Note that ${Y}$ and the ${\xi_{i+1}}$ also form a cone over the shifted base starting from ${\mathsf{F}(0)}$ ; and because ${\mathsf{F}(\mu\mathsf{F})}$ is the colimit from this shifted base, we also get a unique mediating arrow ${k : \mathsf{F}(\mu\mathsf{F}) \rightarrow Y}$ such that ${k \cdot \mathsf{F}(u_i) = \xi_{i+1}}$ for each ${i}$ .

Moreover, both ${h \cdot \mathit{in}}$ and ${g \cdot \mathsf{F}(h)}$ are also such mediating arrows:

$\displaystyle h \cdot \mathit{in} \cdot \mathsf{F}(u_i) = h \cdot u_{i+1} = \xi_{i+1} = g \cdot \mathsf{F}(\xi_i) = g \cdot \mathsf{F}(h \cdot u_i) = g \cdot \mathsf{F}(h) \cdot \mathsf{F}(u_i)$

so both must equal ${k}$ and hence also each other: ${h \cdot \mathit{in} = g \cdot \mathsf{F}(h)}$ .

Finally, for (iii), suppose we have another ${h' : \mu\mathsf{F} \rightarrow Y}$ for which ${h' \cdot \mathit{in} = g \cdot \mathsf{F}(h')}$ ; we have to show that ${h' = h}$ . By the uniqueness of the mediating arrow, it suffices to show that ${h \cdot u_i = \xi_i}$ for each ${i}$ , which is easily done by induction.

That is, given ${\mathsf{F}}$ -algebra ${(Y,g)}$ , there exists a unique ${h : \mu\mathsf{F} \rightarrow Y}$ (for which we write “ ${\mathit{fold}(g)}$ “) such that ${h \cdot \mathit{in} = g \cdot \mathsf{F}(h)}$ . 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 ${\mathsf{F}^i(0)}$ is an approximation to ${\mu\mathsf{F}}$ , cut off at depth ${i}$ ; they all embed into ${\mu\mathsf{F}}$ , and indeed, ${\mu\mathsf{F}}$ is the least extension—the colimit—of them all. Each ${\xi_i}$ is an approximation to ${\mathit{fold}(g)}$ , again restricted to data structures cut off at depth ${i}$ , and ${\mathit{fold}(g)}$ is the completion of all the ${\xi_i}$ .

Naturally, it all dualizes for final coalgebras: then we need “cochains” ${1 \leftarrow \mathsf{F}(1) \leftarrow \mathsf{F}^2(1) \leftarrow \cdots}$ to a terminal object ${1}$ ; an ${\omega^{\mathrm{op}}}$ -category is one in which all such countable cochains have a limit; ${\omega}$ -continuous functors preserve limits of countable cochains. (It is a bit unfortunate that the interesting extreme algebra, namely the initial algebra, is a colimit, whereas the final coalgebra 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 ${\mathsf{F} : \mathbb{J} \rightarrow \mathbb{C}}$ , where ${\mathbb{C}}$ is the category of interest, and index category ${\mathbb{J}}$ determines the shape of the base—for each object ${j}$ of ${\mathbb{J}}$ , there is an object ${\mathsf{F}(j)}$ of ${\mathbb{C}}$ in the base ( ${X_j}$ in the diagram below), and for each arrow ${a : i \rightarrow j}$ of ${\mathbb{J}}$ , an arrow ${\mathsf{F}(a) : \mathsf{F}(i) \rightarrow \mathsf{F}(j)}$ of ${\mathbb{C}}$ in the base ( ${g_a : X_i \rightarrow X_j}$ below).

(In the ${\mathrm{inf}}$ diagram, the index category is the discrete category on three objects—with no arrows other than identity arrows. In the diagram above, ${\mathbb{J}}$ is ${\bullet \mathrel{{-}\vcenter{\hbox{\scriptsize0}}{\rightarrow}} \bullet \mathrel{{\leftarrow}\vcenter{\hbox{\scriptsize2}}{-}} \bullet}$ , with three objects and two generating arrows. In the construction of initial algebras, the index category is ${\omega = \bullet \rightarrow \bullet \rightarrow \cdots}$ , equivalent to the usual ${\le}$ ordering on the natural numbers, whereas for final coalgebras it is ${\bullet \leftarrow \bullet \leftarrow \cdots}$ , equivalent to ${\ge}$ on natural numbers.)

The vertex ${X}$ too can be seen as the image of ${\mathbb{J}}$ under a particular, degenerate functor—the diagonal functor ${\Delta X : \mathbb{J} \rightarrow \mathbb{C}}$ , defined by ${\Delta X(j) = X}$ for each object ${j}$ of ${\mathbb{J}}$ , and ${\Delta X(a) = \mathit{id}_X}$ for each arrow ${a}$ . Then “the cone ${f}$ from vertex ${X}$ to base ${\mathsf{F}}$ ” corresponds to a natural transformation ${f : \Delta X \mathbin{\stackrel{.}{\to}} \mathsf{F}}$ : naturality is exactly the condition that the cone commutes. We write “ ${\mathrm{Lim}\,\mathsf{F}}$ ” for the limiting object, ${X}$ ; its universal property is that, for any cone ${f'}$ from ${X'}$ to ${\mathsf{F}}$ , there exists a unique ${h : X' \rightarrow X}$ such that ${f_i \cdot h = f'_i}$ for each ${i}$ . In other words, there is a (natural) isomorphism between the natural transformations ${\Delta X' \mathbin{\stackrel{.}{\to}} \mathsf{F}}$ and the arrows ${X' \rightarrow \mathrm{Lim}\,\mathsf{F}}$ ; that is, an adjunction ${\Delta \dashv \mathrm{Lim}}$ , 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, ${\mathrm{Colim} \dashv \Delta}$ .

About these ads

5 Responses to Extreme solutions

rich says:

Friday, April 1st, 2011 at 5:58 pm

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

- jeremygibbons says:
  
  Friday, April 1st, 2011 at 10:01 pm
  
  Oops – you’re right, thanks. Fixed now.
  
rich says:

Saturday, April 2nd, 2011 at 5:34 am

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

- jeremygibbons says:
  
  Saturday, April 2nd, 2011 at 1:56 pm
  
  That’s very kind of you – you’re most welcome.
  
Brent says:

Wednesday, April 6th, 2011 at 10:46 pm

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.