Adjoint functors

The functor arrOf takes a contract for a set of elements and produces a contract for the set of lists of those elements. Concatenation of lists makes them into a monoid. Let Mon be the category of monoids and monoid homomorphisms; then we can say that arrOf is a functor from Set to Mon.

There’s another functor from Mon to Set that simply forgets the monoidal structure: it takes an element of a monoid and produces an opaque wrapper with one method, unwrap. Let’s call it setOf.

The contract setOf(arrOf(x)): Set -> Set is for a wrapped array of x‘s. Given any element xVal, we can produce a value wrap([xVal]) that passes setOf(arrOf(x)).

The contract arrOf(setOf(m)): Mon -> Mon is for lists of wrapped elements of a monoid. Given any list like

[wrap(mVal1), wrap(mVal2), wrap(mVal3)]

passing this contract, we can get a monoid element passing m by unwrapping each element and multiplying them all together.

The categories Set and Mon are not equivalent: setOf ○ arrOf is not isomorphic to the identity since there’s no way to take an element like wrap([xVal1, xVal2, xVal]) that passes setOf(arrOf(x)) and produce an element passing the contract x that doesn’t depend on x.

However, setOf and arrOf are related in a special way: with a little thought, it’s easy to see that the set of monoid homomorphisms from arrOf(x) to y is isomorphic to the set of functions passing hom(x, setOf(y)): a monoid homomorphism from arrOf(x) is completely specified by saying what it does to each of the values that pass x: you just map that function over the list and then multiply the results together.

Two functors L:C \to D and R:D \to C are adjoint functors if for all objects c in C and d in D,

\hom_D(L(c), d) \cong \hom_C(c, R(d)).

In the example above, C = \mbox{Set}, \hom_C(c, c') is the set of functions from the set c to the set c’, D = \mbox{Mon}, and \hom_D(d,d') is the set of monoid homomorphisms from the monoid d to the monoid d’.

Other examples of adjoint functors include

  1. \hom_{\mbox{PSet}}(L(c), d) \cong \hom_{\mbox{Set}}(c, R(d)). PSet is the category of “pointed sets”—i.e. sets with a special chosen element called the “point”—and functions between them that map the point of the domain to the point of the codomain. Here, L(c) is the set c plus an extra point, while R(d) forgets which element of d was the special one.
  2. \hom_{\mathbb{N}}(2m, n) \cong \hom_{\mathbb{N}}(m, \lfloor\frac{n}{2}\rfloor), where \mathbb{N} is the category whose objects are natural numbers and there’s a morphism from m to n if m\le n. Here, the floor function forgets the fractional part of \frac{n}{2}.
  3. \hom_{n+1}(\int_0^x f(y) dy, g(x)) \cong \hom_{n}(f(x), \frac{d}{dx} g(x)), where n is the category of polynomials of degree n and there’s a morphism from f to f’ if f is bounded above by f’. Here, the derivative operator forgets the constant term.
  4. In general, any “forgetful” functor R that forgets some structure has a left adjoint L, the “free” structure of that kind.
  5. \hom_{\mbox{Set}}(c+c', d) \cong \hom_{\mbox{Set}^2}((c,c'), \Delta d), where Set² is the category of pairs of sets and pairs of functions between them, and \Delta d = (d, d). This is a categorification of the fact that in real numbers, d^{c+c'} = d^c d^{c'}.
  6. \hom_{\mbox{Set}^2}(\Delta c, (d, d')) \cong \hom_{\mbox{Set}}(c, d \times d'). This is a categorification of the fact that in real numbers, (dd')^c = d^c d'^c.
  7. \hom_{\mbox{Set}}(c \times c', d) \cong \hom_{\mbox{Set}}(c, \hom_{\mbox{Set}}(c', d)). This is a categorification of the fact that in real numbers, d^{cc'} = (d^c)^{c'}.
  8. \hom_{\mbox{Sub}}(c \cup c', d) \cong \hom_{\mbox{Sub}^2}((c,c'), \Delta d), where Sub is the category of sets and inclusions (i.e. there’s a morphism c\to c' if c \subseteq c'.)
  9. \hom_{\mbox{Sub}^2}(\Delta c, (d, d')) \cong \hom_{\mbox{Sub}}(c, d \cap d').
  10. \hom_{\mbox{Bool}}(\exists x \in c \mbox{ such that } x \in s, d) \cong \hom_{\mathcal{P}s}(c, K(d)). Here Bool is the category with two objects F and T and an arrow from F to T—that is, there’s an arrow from one object to another if the one implies the other. \mathcal{P}s is the set of subsets of s, and K(d) maps F to the empty set and T to s.
  11. \hom_{\mathcal{P}s}(K(c), d) \cong \hom_{\mbox{Bool}}(c, \forall x \in d. x \in s).

Adjoint functors turn up all over the place.


Leave a Reply

Please log in using one of these methods to post your comment: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: