[Last time](https://forum.azimuthproject.org/discussion/2253/lecture-47-chapter-3-adjoint-functors/p1) I threw the definition of 'adjoint functor' at you. Now let me actually _explain_ adjoint functors!

As we learned [long ago](https://forum.azimuthproject.org/discussion/1845/lecture-5-chapter-1-galois-connections/p1), the basic idea is that adjoints give _the best possible way to approximately recover data that can't really be recovered_.

For example, you might have a map between databases that discards some data. You might like to reverse this process. Strictly speaking this is impossible: if you've truly discarded some data, you don't know what it is anymore, so you can't restore it. But you can still _do your best!_

There are actually two kinds of 'best': left adjoints and right adjoints.

Remember the idea. We have a functor \\(F : \mathcal{A} \to \mathcal{B}\\). We're looking for a nice functor \\(G: \mathcal{B} \to \mathcal{A} \\) that goes back the other way, some sort of attempt to reverse the effect of \\(F\\). We say that \\(G\\) is a **right adjoint** of \\(F\\) if there's a natural one-to-one correspondence between

* morphisms from \\(F(a)\\) to \\(b\\)

and

* morphisms from \\(a\\) to \\(G(b)\\)

whenever \\(a\\) is an object of \\(\mathcal{A}\\) and \\(b\\) is an object of \\(\mathcal{B}\\). In this situation we also say \\(F\\) is a **left adjoint** of \\(G\\).

The tricky part in this definition is the word 'natural'. That's why I had to explain natural transformations. But let's see how far we can get understanding adjoint functors without worrying about this.

Let's do an example. There's a category \\(\mathbf{Set}\\) where objects are sets and morphisms are functions. And there's much more boring category \\(\mathbf{1}\\), with exactly one object and one morphism. Today let's call that one object \\(\star\\), so the one morphism is \\(1_\star\\).

In [Puzzle 135](https://forum.azimuthproject.org/discussion/2247/lecture-44-chapter-3-categories-functors-and-natural-transformations/p1) we saw there is always exactly one functor from any category to \\(\mathbf{1}\\). So, there's exactly one functor

\[ F: \mathbf{Set} \to \mathbf{1} \]

This sends every set to the object \\(\star\\), and every function between sets to the morphism \\(1_\star\\).

This is an incredibly destructive functor! It discards _all_ the information about every set and every function! \\(\mathbf{1}\\) is like the ultimate trash can, or black hole. Drop data into it and it's _gone_.

So, it seems insane to try to 'reverse' the functor \\(F\\), but that's what we'll do. First let's look for a right adjoint

\[ G: \mathbf{1} \to \mathbf{Set} .\]

For \\(G\\) to be a right adjoint, we need a natural one-to-one correspondence between morphisms

\[ m: F(S) \to \star \]

and morphisms

\[ n: S \to G(\star) \]

where \\(S\\) is any set.

Think about what this means! We know \\(F(S) = \star\\): there's nothing else it could be, since \\(\mathbf{1}\\) has just one object. So, we're asking for a natural one-to-one correspondence between the set of morphisms

\[ m : \star \to \star \]

and the set of functions

\[ n : S \to G(\star) .\]

This has got to work for every set \\(S\\). This should tell us a lot about \\(G(\star)\\).

Well, there's just _one_ morphism \\( m : \star \to \star\\), so there had better be just one function \\(n : S \to G(\star)\\), _for any set_ \\(S\\). This forces \\(G(\star)\\) to be a set with just one element. And that does the job! We can take \\(G(\star)\\) to be _any_ set with just one element, and that gives us our left adjoint \\(G\\).

Well, okay: we have to say what \\(G\\) does to _morphisms_, too. But the only morphism in \\(\mathbf{1}\\) is \\(1_\star\\), and we must have \\(G(1_\star) = 1_{G(\star)} \\), thanks to how functors work.

(Furthermore you might wonder about the 'naturality' condition, but this example is so trivial that it's automatically true.)

So: if you throw away a set into the trash bin called \\(\mathbf{1}\\), and I say "wait! I want that set back!", and I have to make up something, the right adjoint procedure says "pick any one-element set". Weird but true. When you really understand adjoints, you'll have a good intuitive sense for why it works this way.

What about the left adjoint procedure? Let's use \\(L\\) to mean a left adjoint of our functor \\(F\\):

**Puzzle 149.** Again suppose \\(F: \mathbf{Set} \to \mathbf{1}\\) is the functor that sends every set to \\(\star\\) and every function to \\(1_\star\\). A _left_ adjoint \\(L : \mathbf{1} \to \mathbf{Set} \\) is a functor for which there's a natural one-to-one correspondence between functions

\[ m: L(\star) \to S \]

and morphisms

\[ n: \star \to F(S) \]

for every set \\(S\\). On the basis of this, try to figure out all the left adjoints of \\(F\\).

Let's also try some slightly harder examples. There is a category \\(\mathbf{Set}^2\\) where an object is a pair of sets \\( (S,T)\\). In this category a morphism is a pair of functions, so a morphism

\[ (f,g): (S,T) \to (S',T') \]

is just a function \\(f: S \to S'\\) together with function \\(g: T \to T'\\). We compose these morphisms componentwise:

\[ (f,g) \circ (f',g') = (f\circ f', g \circ g') . \]

You can figure out what the identity morphisms are, and check all the category axioms.

There's a functor

\[ F: \mathbf{Set}^2 \to \mathbf{Set} \]

that discards the second component. So, on objects it throws away the second set:

\[ F(S,T) = S \]

and on morphisms it throws away the second function:

\[ F(f,g) = f .\]

**Puzzle 150.** Figure out all the right adjoints of \\(F\\).

**Puzzle 151.** Figure out all the left adjoints of \\(F\\).

There's also a functor

\[ \times: \mathbf{Set}^2 \to \mathbf{Set} \]

that takes the Cartesian product, both for sets:

\[ \times (S,T) = S \times T \]

and for functions:

\[ \times (f,g) = f \times g \]

where \\((f\times g)(s,t) = (f(s),g(t))\\) for all \\(s \in S, t \in T\\).

**Puzzle 152.** Figure out all the right adjoints of \\(\times\\).

**Puzzle 153.** Figure out all the left adjoints of \\(\times\\).

Finally, there's also a functor

\[ + : \mathbf{Set}^2 \to \mathbf{Set} \]

that takes the disjoint union, both for sets:

\[ + (S,T) = S + T \]

and for functions:

\[ +(f,g) = f + g .\]

Here \\(S + T\\) is how category theorists write the [disjoint union](https://en.wikipedia.org/wiki/Disjoint_union#Set_theory_definition) of sets \\(S\\) and \\(T\\). Furthermore, given functions \\(f: S \to S'\\) and \\(g: T \to T'\\) there's an obvious function \\(f+g: S+T \to S'+T'\\) that does \\(f\\) to the guys in \\(S\\) and \\(g\\) to the guys in \\(T\\).

**Puzzle 152.** Figure out all the right adjoints of \\(+\\).

**Puzzle 153.** Figure out all the left adjoints of \\(+\\).

I think it's possible to solve all these puzzles even if one has a rather shaky grasp on adjoint functors. At least try them! It's a good way to start confronting this new concept.

**[To read other lectures go here.](http://www.azimuthproject.org/azimuth/show/Applied+Category+Theory#Chapter_3)**

As we learned [long ago](https://forum.azimuthproject.org/discussion/1845/lecture-5-chapter-1-galois-connections/p1), the basic idea is that adjoints give _the best possible way to approximately recover data that can't really be recovered_.

For example, you might have a map between databases that discards some data. You might like to reverse this process. Strictly speaking this is impossible: if you've truly discarded some data, you don't know what it is anymore, so you can't restore it. But you can still _do your best!_

There are actually two kinds of 'best': left adjoints and right adjoints.

Remember the idea. We have a functor \\(F : \mathcal{A} \to \mathcal{B}\\). We're looking for a nice functor \\(G: \mathcal{B} \to \mathcal{A} \\) that goes back the other way, some sort of attempt to reverse the effect of \\(F\\). We say that \\(G\\) is a **right adjoint** of \\(F\\) if there's a natural one-to-one correspondence between

* morphisms from \\(F(a)\\) to \\(b\\)

and

* morphisms from \\(a\\) to \\(G(b)\\)

whenever \\(a\\) is an object of \\(\mathcal{A}\\) and \\(b\\) is an object of \\(\mathcal{B}\\). In this situation we also say \\(F\\) is a **left adjoint** of \\(G\\).

The tricky part in this definition is the word 'natural'. That's why I had to explain natural transformations. But let's see how far we can get understanding adjoint functors without worrying about this.

Let's do an example. There's a category \\(\mathbf{Set}\\) where objects are sets and morphisms are functions. And there's much more boring category \\(\mathbf{1}\\), with exactly one object and one morphism. Today let's call that one object \\(\star\\), so the one morphism is \\(1_\star\\).

In [Puzzle 135](https://forum.azimuthproject.org/discussion/2247/lecture-44-chapter-3-categories-functors-and-natural-transformations/p1) we saw there is always exactly one functor from any category to \\(\mathbf{1}\\). So, there's exactly one functor

\[ F: \mathbf{Set} \to \mathbf{1} \]

This sends every set to the object \\(\star\\), and every function between sets to the morphism \\(1_\star\\).

This is an incredibly destructive functor! It discards _all_ the information about every set and every function! \\(\mathbf{1}\\) is like the ultimate trash can, or black hole. Drop data into it and it's _gone_.

So, it seems insane to try to 'reverse' the functor \\(F\\), but that's what we'll do. First let's look for a right adjoint

\[ G: \mathbf{1} \to \mathbf{Set} .\]

For \\(G\\) to be a right adjoint, we need a natural one-to-one correspondence between morphisms

\[ m: F(S) \to \star \]

and morphisms

\[ n: S \to G(\star) \]

where \\(S\\) is any set.

Think about what this means! We know \\(F(S) = \star\\): there's nothing else it could be, since \\(\mathbf{1}\\) has just one object. So, we're asking for a natural one-to-one correspondence between the set of morphisms

\[ m : \star \to \star \]

and the set of functions

\[ n : S \to G(\star) .\]

This has got to work for every set \\(S\\). This should tell us a lot about \\(G(\star)\\).

Well, there's just _one_ morphism \\( m : \star \to \star\\), so there had better be just one function \\(n : S \to G(\star)\\), _for any set_ \\(S\\). This forces \\(G(\star)\\) to be a set with just one element. And that does the job! We can take \\(G(\star)\\) to be _any_ set with just one element, and that gives us our left adjoint \\(G\\).

Well, okay: we have to say what \\(G\\) does to _morphisms_, too. But the only morphism in \\(\mathbf{1}\\) is \\(1_\star\\), and we must have \\(G(1_\star) = 1_{G(\star)} \\), thanks to how functors work.

(Furthermore you might wonder about the 'naturality' condition, but this example is so trivial that it's automatically true.)

So: if you throw away a set into the trash bin called \\(\mathbf{1}\\), and I say "wait! I want that set back!", and I have to make up something, the right adjoint procedure says "pick any one-element set". Weird but true. When you really understand adjoints, you'll have a good intuitive sense for why it works this way.

What about the left adjoint procedure? Let's use \\(L\\) to mean a left adjoint of our functor \\(F\\):

**Puzzle 149.** Again suppose \\(F: \mathbf{Set} \to \mathbf{1}\\) is the functor that sends every set to \\(\star\\) and every function to \\(1_\star\\). A _left_ adjoint \\(L : \mathbf{1} \to \mathbf{Set} \\) is a functor for which there's a natural one-to-one correspondence between functions

\[ m: L(\star) \to S \]

and morphisms

\[ n: \star \to F(S) \]

for every set \\(S\\). On the basis of this, try to figure out all the left adjoints of \\(F\\).

Let's also try some slightly harder examples. There is a category \\(\mathbf{Set}^2\\) where an object is a pair of sets \\( (S,T)\\). In this category a morphism is a pair of functions, so a morphism

\[ (f,g): (S,T) \to (S',T') \]

is just a function \\(f: S \to S'\\) together with function \\(g: T \to T'\\). We compose these morphisms componentwise:

\[ (f,g) \circ (f',g') = (f\circ f', g \circ g') . \]

You can figure out what the identity morphisms are, and check all the category axioms.

There's a functor

\[ F: \mathbf{Set}^2 \to \mathbf{Set} \]

that discards the second component. So, on objects it throws away the second set:

\[ F(S,T) = S \]

and on morphisms it throws away the second function:

\[ F(f,g) = f .\]

**Puzzle 150.** Figure out all the right adjoints of \\(F\\).

**Puzzle 151.** Figure out all the left adjoints of \\(F\\).

There's also a functor

\[ \times: \mathbf{Set}^2 \to \mathbf{Set} \]

that takes the Cartesian product, both for sets:

\[ \times (S,T) = S \times T \]

and for functions:

\[ \times (f,g) = f \times g \]

where \\((f\times g)(s,t) = (f(s),g(t))\\) for all \\(s \in S, t \in T\\).

**Puzzle 152.** Figure out all the right adjoints of \\(\times\\).

**Puzzle 153.** Figure out all the left adjoints of \\(\times\\).

Finally, there's also a functor

\[ + : \mathbf{Set}^2 \to \mathbf{Set} \]

that takes the disjoint union, both for sets:

\[ + (S,T) = S + T \]

and for functions:

\[ +(f,g) = f + g .\]

Here \\(S + T\\) is how category theorists write the [disjoint union](https://en.wikipedia.org/wiki/Disjoint_union#Set_theory_definition) of sets \\(S\\) and \\(T\\). Furthermore, given functions \\(f: S \to S'\\) and \\(g: T \to T'\\) there's an obvious function \\(f+g: S+T \to S'+T'\\) that does \\(f\\) to the guys in \\(S\\) and \\(g\\) to the guys in \\(T\\).

**Puzzle 152.** Figure out all the right adjoints of \\(+\\).

**Puzzle 153.** Figure out all the left adjoints of \\(+\\).

I think it's possible to solve all these puzzles even if one has a rather shaky grasp on adjoint functors. At least try them! It's a good way to start confronting this new concept.

**[To read other lectures go here.](http://www.azimuthproject.org/azimuth/show/Applied+Category+Theory#Chapter_3)**