# Adjoint Functor Theorems

(under construction)

It can be difficult to establish whether a given functor has a left or right adjoint. To establish the existence, various adjoint functor theorems have been developed.

We first review a list of examples. They are intended to show how adjoint functor theorems for categories generalise those for ordered sets.

Adjoint functor theorems for ordered sets are much simpler since they do not involve quotienting nor size conditions. Nevertheless, adjoint functor theorems for categories can be formulated in essentially the same form as those for ordered sets.

## Examples

### Implication as a Right-Adjoint

The most famous right-adjoint is probably logical implication. The following logic law is easy to establish with Venn diagrams
$$\frac{a\wedge b \le c}{a \le \neg b \vee c}$$

where the horizontal line should be read here as "if and only if". In other words, $(\neg b \vee -)$ is right-adjoint to $(-\wedge b)$. [^fnabc]

In Boolean logic, one defines implication $b\to c$ as $\neg b\vee c$.

If $a,b,c$ do not range over arbitrary subsets but, for example, the open sets of a topological space, then we cannot use disjunction to compute the right adjoint. But the right-adjoint might still exist. So, as usual in mathematics, we turn a theorem ("implication is a right-adjoint") into a definition. We define implication $\to$ as the operation that satisfies
$$\frac{a\wedge b \le c}{a \le b\to c},$$

that is, implication is now by definition the right adjoint to conjunction.

Our first adjoint functor theorem is then the following.

**Theorem:** Let $\mathcal A$ be a complete lattice in which, for all $a\in \mathcal A$ the function $(a\wedge -)$ preserves arbitrary joins. Then
$$b\to c \ \stackrel{\rm def} = \ \bigvee \{a \mid a\wedge b \le c\}$$

satisfies the definition of implication.

The formula for the right-adjoint looks quite technical, but it makes intuitive sense. $b\to c$ is the largest $a$ inside of which we know "if $b$ then $c$".

### Adjoints between Ordered Sets

$(a\wedge -)$ being left-adjoint to the right-adjoint $(a\to -)$ is a special case of a more general situation. Let $f:\mathcal A\to\mathcal B$ and $g:\mathcal B\to\mathcal A$ be monotone (ie order preserving) maps between ordered sets (preorders, posets, lattices, ...). Then we say that $f$ is left-adjoint to $g$ and $g$ is right-adjoint to $f$, in symbols
$$f\dashv g$$

if (again the horizontal line is an "iff")
$$\frac{f(a)\le b}{a\le g(b)}.$$

Our previous adjoint functor theorem generalises to this situation.

**Theorem:** Let $f:\mathcal A\to \mathcal B$ be a join-preserving function between complete lattices. Then $f$ has a right-adjoint $g$ given by
$$g(b) = \ \bigvee \{a \mid f(a) \le b\}.$$

The proof is not more difficult than the one for the special case.

**Examples:** The rounding functions floor and ceiling are adjoints to the inclusion of integers in real numbers.
In temporal logic, the the somtimes-in-the-future $\Diamond$ is left-adjoint to the always-in-the-past $\Box$.
The direct-image of function is left-adjoint to inverse-image.
In first-order logic, existential quantifiers are left-adjoint to substitution and universal quantifiers are right-adjoint to subsitution.
In lattice theory, taking joins is left-adjoint to the singleton map $x\mapsto\{x\}$ and taking meets is righ-adjoint.

### Universal Dynamic Systems

We now turn from ordered sets to categories.

Let $\mathcal A$ be the category of 'dynamical systems', that is, functions $X\to X$. Let $F:\mathcal A\to\sf Set$ be the forgetful functor. Then $F$ has a right-adjoint $G$.

We can compute the right-adjoint $G$ via a formula that generalises the two previous adjoint functor theorems.

**Review of Adjunctions between Ordered Sets:** We first rewrite $g(b) = \ \bigvee \{a \mid f(a) \le b\}$ as
$$g(b) = \ \bigvee_a \mathcal B(f(a),b)\bullet a$$

This works as follows. As before we want to take the join over all $a$ such that $f(a)\le b$. Notice that because $\mathcal B$ is an ordered set, the hom $\mathcal B(f(a),b)$ is $1$ iff $f(a)\le b$ and $0$ otherwise. This allows us to define the operation $\bullet$ as follows. $0\bullet a$ is the bottom element in $\mathcal A$ (which is a complete lattice) and $1\bullet a= a$. With these definitions we obtain $\bigvee_a \mathcal B(f(a),b)\bullet a=\bigvee \{a \mid f(a) \le b\}$.

**Generalising from Ordered Sets to Categories:** The formula for the right-adjoint $g$ generalises from ordered sets to categories as follows. [^maclane234]
$$GY = \int_A {\sf Set}(FA,Y)\bullet A$$

Recall that ${\sf Set}(FA,Y)$ is the set of functions $FA\to Y$. For a set $X$, we have that $X \bullet Y$ is the $|X|$-fold coproduct of $Y$, or, simply (but this does not generalise to other categories than $\sf Set$), $X\times Y$. The notation $\int_A$ denotes a certain colimit in $\mathcal A$.[^commacolimit] This colimit can be understood as the coproduct of all $A\in\mathcal A$ quotiented by a suitable equivalence relation.

If we apply this to the concrete example at hand, then $GY$ is the dynamical system $Y^\omega\to Y^\omega$ that maps an infinite list $(y_0,y_1,y_2,\ldots)$ to $(y_1,y_2,\ldots)$.

**Remark:** I used the formula $GY = \int_X {\sf Set}(FX,Y)\bullet X$ to guess $G$ and then verified the guess directly with the usual universal property of a right-adjoint. This is faster than explicitely writing out the diagram of which $\int_X {\sf Set}(FX,Y)\bullet X$ is the colimit.

### Terminal Objects in a Category

The following can be proved in different ways, or even be taken as a definition of terminal object.

**Fact:** Let $\mathcal I$ be the one element category and $F:\mathcal A\to\mathcal I$. Then $F$ has a right-adjoint $G$ iff $\mathcal A$ has a terminal (aka final) object.

In the light of the previous discussion that means that the terminal object in a category is
$$ G= \int_A A = {\rm colim\ \it Id}$$

where $\it Id$ is the identity functor $\mathcal A\to\mathcal A$. See Mac Lane, page 234, for an explicit proof of this.

### Final Coalegbras

Let $F:\mathcal A\to \sf Set$ be a functor with a right-adjoint $G$ and let $1$ be the terminal object in $\sf Set$. Then, as we have seen in the previous section, $G1$ is the terminal object in $\mathcal A$.

Now let $\mathcal A$ be the category of coalgebras $X\to TX$ for a functor $T:\sf Set\to Set$ and let $F$ be the forgetful functor.

Then the final coalgebra is given by
$$\int_A FA \to T(\int_A FA).$$

Unpacking the definitions, one can show that $\int_A FA$ is the quotient of the coproduct of all coalgebras by bisimilarity, see the note on [Coalgebraic Bisimilarity](https://hackmd.io/@alexhkurz/SJs53demu) for more details.

This finishes our list of examples.

## Size

A distinction between small and large sets is crucial for category theory. The set of objects is (typically) large, but homsets are small. A category is complete if it has all small limits.

A category is equivalent to a lattice iff it has all large limits.

...

## General Adjoint Functor Theorems

Theorem 2 on page 234 of Mac Lane:

**Theorem:** A functor $F:\mathcal A\to\mathcal B$ has a right-adjoint iff $F$ preserves all colimits that exist in $\mathcal A$ and the colimits $GY=\int_A (FA,Y)\bullet A$ exist for all $Y$.

**Remark:** The colimit $\int_A (FA,Y)\bullet A$ is the colimit of the diagram $F{\downarrow}Y\to\mathcal A$.

**Remark:** In other words, the right-adjoint of $F$ is the left-Kan extension of $\it Id:\mathcal A\to\mathcal A$ along $F$. Dually. the left-adjoint of $G$ is the right-Kan extension of the identity along $G$.

... there is more to say here ... for now see Mac Lane, Chapter X, Kan Extensions.

The next step is to specialise the theorem to the case where $\mathcal A$ is cocomplete, that is, where $\mathcal A$ has all small colimits. Unfortunately, the colimit of the theorem is not small. But it may still be equivalent to a small one. If this is the case then $F$ satisfies the so-called **solution set condition**.

...

## Special Adjoint Functor Theorems

Special adjoint functor theorems are typical about situations where we can infer the solution set condition.

For example, ...

## References

Mac Lane: Categories for the Working Mathematician.

[^fnabc]: Would it be more memorable to write the following? We have
$$\frac{a\wedge b \le c}{b \le \neg a \vee c},$$

that is, $(\neg a\vee -)$ is right-adjoint to $(a\wedge -)$.

[^maclane234]: Theorem 2 on page 234 of Mac Lane states and proves the dual theorem in slightly different notation. In our setting it reads as follows: A functor $F:\mathcal A\to\mathcal B$ has a right-adjoint iff $F$ preserves all colimits that exist in $\mathcal A$ and the colimits $GY=\int_A (FA,Y)\bullet A$ exist for all $Y$.

[^commacolimit]: For $F:\mathcal A\to\mathcal B$ and $H:\mathcal A\to\mathcal C$, the left-Kan extension ${\rm Lan}_FH:\mathcal B\to\mathcal C$ of $H$ along $F$, applied to $B$, is written as $\int_A \mathcal B(FA,B)\bullet HA$ and can be defined as the colimit of $F{\downarrow}B\to\mathcal A\stackrel H\longrightarrow \mathcal B$.