It looks like you're new here. If you want to get involved, click one of these buttons!

- All Categories 2.4K
- Chat 502
- Study Groups 21
- Petri Nets 9
- Epidemiology 4
- Leaf Modeling 2
- Review Sections 9
- MIT 2020: Programming with Categories 51
- MIT 2020: Lectures 20
- MIT 2020: Exercises 25
- Baez ACT 2019: Online Course 339
- Baez ACT 2019: Lectures 79
- Baez ACT 2019: Exercises 149
- Baez ACT 2019: Chat 50
- UCR ACT Seminar 4
- General 73
- Azimuth Code Project 110
- Statistical methods 4
- Drafts 10
- Math Syntax Demos 15
- Wiki - Latest Changes 3
- Strategy 113
- Azimuth Project 1.1K
- - Spam 1
- News and Information 148
- Azimuth Blog 149
- - Conventions and Policies 21
- - Questions 43
- Azimuth Wiki 718

Options

We spent a lot of time in Chapter 2 studying Galois connections. Now all that time is going to pay off! We're going to generalize Galois connections between preorders, and get 'adjoint functors' between categories. These are one of most fruitful ideas in category theory.

Remember, given two preorders \(A\) and \(B\), a **Galois connection** is a pair of monotone maps \(f: A \to B\) and \(g: B \to A\) such that

$$ f(a) \le b \textrm{ if and only if } a \le g(b) $$
for all \(a \in A, b \in B\). We call \(f\) the **left adjoint** of \(g\), and \(g\) the **right adjoint** of \(f\).

But now we know that a preorder is a special sort of category: a category where there's at most one morphism from any object \(x\) to any object \(y\). We denote the existence of a morphism by \(x \le y\).

So how do we generalize Galois connections to arbitrary categories? A first guess might be this:

**First Attempt at a Generalization.** Given categories \(\mathcal{A}\) and \(\mathcal{B}\), an **adjunction** is pair of functors \(F: \mathcal{A} \to \mathcal{B}\) and \(G: \mathcal{B} \to \mathcal{A}\) such that there is a one-to-one correspondence between morphisms

$$ m: F(a) \to b $$ and morphisms

$$ n : a \to G(b) $$
for all objects \(a\) in \(\mathcal{A}\) and \(b\) in \(\mathcal{B}\). We call \(F\) the **left adjoint** of \(G\), and \(G\) the **right adjoint** of \(F\).

You can check that this generalization does indeed reduce to the definition of Galois connection when our categories are preorders. However, it's not the *right* generalization!

The reason is that merely saying *there exists* a one-to-one correspondence is not enough to do much. We should at the very least *specify* a one-to-one correspondence, and make it part of the definition.

This is not good enough either, but it's a step in the right direction, so let's write it down.

Remember, the set of morphisms from \(F(a)\) to \(b\) in the category \(\mathcal{B}\) is called \(\mathcal{B}(F(a),b)\). The set of morphisms from \(a\) to \(G(b)\) in the category \(\mathcal{A}\) is called \(\mathcal{A}(a,G(b))\). So, we're going to specify a one-to-one correspondence, also known as a bijection, between these two sets.

**Second Attempt at a Generalization.** Given categories \(\mathcal{A}\) and \(\mathcal{B}\), an **adjunction** is pair of functors \(F: \mathcal{A} \to \mathcal{B}\) and \(G: \mathcal{B} \to \mathcal{A}\) together with a bijection

$$ \alpha_{a,b} : \mathcal{B}(F(a),b) \to \mathcal{A}(a,G(b)) $$
for every pair of objects \(a\) in \(\mathcal{A}\) and \(b\) in \(\mathcal{B}\). We call \(F\) the **left adjoint** of \(G\), and \(G\) the **right adjoint** of \(F\).

This is getting nice. We could actually do a fair amount with this. But for serious work we'll need \(\alpha\) to be a *natural isomorphism*, which gives a bijection \(\alpha_{a,b}\) when we feed it a pair of objects \( (a,b) \).

And this, in turn, means that we need to interpret \(\mathcal{B}(F(-),-)\) and \(\mathcal{A}(-,G(-))\) as *functors*, which give sets \( \mathcal{B}(F(a),b) \) and \( \mathcal{A}(a,G(b)) \) when we feed them a pair of objects \( (a,b) \). The blanks stand for slots where we can feed in \(a\) and \(b\) - this is standard math notation.

Defining these functors takes a little work. Let me run through it rapidly now in a sketchy way. Next time we'll look at some examples, and eventually we'll need to get serious about the details.

For any pair of categories \(\mathcal{A}\) and \(\mathcal{B}\) there's a category \(\mathcal{A} \times \mathcal{B}\), called the 'product' of \(\mathcal{A}\) and \(\mathcal{B}\). Objects here are pairs \( (a,b) \) where \(a\) is in \(\mathcal{A}\) and \(b\) is in \(\mathcal{B}\); There's more that needs to be said - I haven't filled in all the details - but let's move ahead.

For any category \(\mathcal{A}\) there a category \(\mathcal{A}^{\text{op}} \) called the **opposite** of \(\mathcal{A}\), which has the same objects but has morphisms going the opposite way. In other words, a morphism \(f: a \to a'\) in \(\mathcal{A}^{\text{op}} \) is defined to be morphism \(f: a' \to a\). There's more that needs to be said, but let's keep moving!

Given functors \(F: \mathcal{A} \to \mathcal{B}\) and \(G: \mathcal{B} \to \mathcal{A}\), I claim that there are functors

$$ \mathcal{B}(F(-),-) : \mathcal{A}^{\text{op}} \times \mathcal{B} \to \mathbf{Set} $$ and

$$ \mathcal{A}(-,G(-)) :\mathcal{A}^{\text{op}} \times \mathcal{B} \to \mathbf{Set} $$ that give sets \( \mathcal{B}(F(a),b) \) and \( \mathcal{A}(a,G(b)) \), respectively, when we feed them an object \( (a,b) \in \mathcal{A}^{\text{op}} \times \mathcal{B} \).

So, for an adjunction, what we want is a natural isomorphism between these functors!

Now we are ready - except for the important details I left out - for the correct definition:

**Definition.** Given categories \(\mathcal{A}\) and \(\mathcal{B}\), an **adjunction** is pair of functors \(F: \mathcal{A} \to \mathcal{B}\) and \(G: \mathcal{B} \to \mathcal{A}\) together with a natural isomorphism

$$ \alpha : \mathcal{B}(F(-),-) \to \mathcal{A}(-,G(-)). $$
We call \(F\) the **left adjoint** of \(G\), and \(G\) the **right adjoint** of \(F\).

Note that the final definition is shorter than our two previous guesses! But it packs a bigger punch... and it takes more work to really understand it. We'll start next time.

## Comments

Since I didn't teach a class on Thursday and Friday, I did it on Saturday and Sunday! Now I'm caught up.

I'm sorry for any inconvenience this causes: I know you folks may have trouble dealing with an erratic flood of lectures. Take your time and ask lots of questions whenever you get around to it!

`Since I didn't teach a class on Thursday and Friday, I did it on Saturday and Sunday! Now I'm caught up. <img src = "http://math.ucr.edu/home/baez/emoticons/thumbsup.gif"> I'm sorry for any inconvenience this causes: I know you folks may have trouble dealing with an erratic flood of lectures. Take your time and ask lots of questions whenever you get around to it!`

So, how is that exactly? We are interested in the functor \( F':\mathcal{A}^{op} \times \mathcal{B} \rightarrow \boldsymbol {\text{Set}}. \) For that we consider the functor \( F: \mathcal{A} \rightarrow \mathcal{B}. \) Is this correct? There isn't a functor \( F^{op}: \mathcal{A}^{op} \rightarrow \mathcal{B} \; ?\)

A morphism \( f: X \rightarrow Y \) in \( \mathcal{A}^{op} \) then induces a map of \( \mathcal{B} (F (\mathcal{A}^{op} ),\mathcal {B}) \) like following? Hmm, but actually we are looking for a map on \( \mathcal{B} (F (\mathcal{A} ),\mathcal {B}) \) instead of \( \mathcal{B} (F (\mathcal{A}^{op} ),\mathcal {B}) \)... ???

`So, how is that exactly? We are interested in the functor \\( F':\mathcal{A}^{op} \times \mathcal{B} \rightarrow \boldsymbol {\text{Set}}. \\) For that we consider the functor \\( F: \mathcal{A} \rightarrow \mathcal{B}. \\) Is this correct? There isn't a functor \\( F^{op}: \mathcal{A}^{op} \rightarrow \mathcal{B} \; ?\\) A morphism \\( f: X \rightarrow Y \\) in \\( \mathcal{A}^{op} \\) then induces a map of \\( \mathcal{B} (F (\mathcal{A}^{op} ),\mathcal {B}) \\) like following? ![How a morphism is maped on a morphism on the Hom-sets by a functor](https://svgshare.com/i/78r.svg) Hmm, but actually we are looking for a map on \\( \mathcal{B} (F (\mathcal{A} ),\mathcal {B}) \\) instead of \\( \mathcal{B} (F (\mathcal{A}^{op} ),\mathcal {B}) \\)... ???`

@Peter – it might be easier to first consider just one category \(\mathcal{C}\) and try to build a functor that sends a pair of objects \((X, Y)\) to the set of morphisms from \(X\) to \(Y\), namely \(\mathcal{C}(X, Y)\).

If you think about how this might works on pairs of morphisms \((f, g)\) you'll notice it has to be contravariant in the first variable and covariant in the second one. Hence it's a functor from \(\mathcal{C}^{op} \times \mathcal{C}\) to \(\textbf{Set}\).

The functors \(\mathcal{B}(F(-), -)\) and \(\mathcal{A}(-, G(-))\) are variants of this construction.

`@Peter – it might be easier to first consider just one category \\(\mathcal{C}\\) and try to build a functor that sends a pair of objects \\((X, Y)\\) to the set of morphisms from \\(X\\) to \\(Y\\), namely \\(\mathcal{C}(X, Y)\\). If you think about how this might works on pairs of morphisms \\((f, g)\\) you'll notice it has to be contravariant in the first variable and covariant in the second one. Hence it's a functor from \\(\mathcal{C}^{op} \times \mathcal{C}\\) to \\(\textbf{Set}\\). The functors \\(\mathcal{B}(F(-), -)\\) and \\(\mathcal{A}(-, G(-))\\) are variants of this construction.`

Anindya wrote:

I'm not sure if this relevant for the current discussion, but I wanted to point out that if a map is functorial in each argument it's not a sufficient condition to conclude that it's a functor. We need an additional coherence condition, known as the "interchange law"; for example, see the bifunctor lemma stated in chapter 7 from Awodey's book.

`Anindya wrote: > [I]t has to be contravariant in the first variable and covariant in the second one. Hence it's a functor from \\(\mathcal{C}^{op} \times \mathcal{C}\\) to \\(\textbf{Set}\\). I'm not sure if this relevant for the current discussion, but I wanted to point out that if a map is functorial in each argument it's not a sufficient condition to conclude that it's a functor. We need an additional coherence condition, known as the "interchange law"; for example, see the bifunctor lemma stated in [chapter 7](https://www.andrew.cmu.edu/course/80-413-713/notes/chap07.pdf) from Awodey's book.`

An adjunction between categories looks like the diagram below when you draw out a commuting diagram.

Using John's examples:

\[ \begin{matrix} A & \overset{F}\Rightarrow & F(A) \\ n\downarrow & & \downarrow m \\ G(B) & \underset{G}\Leftarrow & B \end{matrix} \]

`An adjunction between categories looks like the diagram below when you draw out a commuting diagram. Using John's examples: \\[ \begin{matrix} A & \overset{F}\Rightarrow & F(A) \\\\ n\downarrow & & \downarrow m \\\\ G(B) & \underset{G}\Leftarrow & B \end{matrix} \\]`

Peter wrote:

No, there's not a functor from \( \mathcal{A}^{\text{ op}} \) to \(\mathcal{B}\) in this game. We have a functor \(F : \mathcal{A} \to \mathcal{B} \). There's no way to turn that into a functor \( \mathcal{A}^{\text{op}} \) to \(\mathcal{B}\).

The "op" comes in when we consider

$$ \mathcal{B}(F(-),-) : \mathcal{A}^{\mathrm{op}} \times \mathcal{B} \to \mathbf{Set} $$ This functor sends any pair \(a, b\) consisting of an object \(a\) in \(\mathcal{A}\) and an object \(b\) in \(\mathcal{B}\) to the set

$$ \mathcal{B}(F(a),b) . $$ But what does this functor do to morphisms? This is where the "op" comes in! If we have a pair of morphisms \(f: a' \to a\) and \(g: b \to b'\) this functor gives us a map from

$$ \mathcal{B}(F(a),b) $$ to

$$ \mathcal{B}(F(a'),b') $$

Puzzle.Can somehow say how we define this map? It's my duty to explain this, but someone probably knows already.The key point is that to get this map is built from a pair \( (f,g) \) consisting of a morphism \(g: b \to b'\) going

forwardsfrom \(b\) to \(b'\), and a morphism \(f: a' \to a\) goingbackwardsfrom \(a'\) to \(a\). That backwardsness is why we need \(\mathcal{A}^\textrm{op}\).`Peter wrote: > So, how is that exactly? We are interested in the functor \\( F':\mathcal{A}^{op} \times \mathcal{B} \rightarrow \boldsymbol {\text{Set}}. \\) For that we consider the functor \\( F: \mathcal{A} \rightarrow \mathcal{B}. \\) Is this correct? There isn't a functor \\( F^{op}: \mathcal{A}^{op} \rightarrow \mathcal{B} \; ?\\) No, there's not a functor from \\( \mathcal{A}^{\text{ op}} \\) to \\(\mathcal{B}\\) in this game. We have a functor \\(F : \mathcal{A} \to \mathcal{B} \\). There's no way to turn that into a functor \\( \mathcal{A}^{\text{op}} \\) to \\(\mathcal{B}\\). The "op" comes in when we consider \[ \mathcal{B}(F(-),-) : \mathcal{A}^{\mathrm{op}} \times \mathcal{B} \to \mathbf{Set} \] This functor sends any pair \\(a, b\\) consisting of an object \\(a\\) in \\(\mathcal{A}\\) and an object \\(b\\) in \\(\mathcal{B}\\) to the set \[ \mathcal{B}(F(a),b) . \] But what does this functor do to morphisms? This is where the "op" comes in! If we have a pair of morphisms \\(f: a' \to a\\) and \\(g: b \to b'\\) this functor gives us a map from \[ \mathcal{B}(F(a),b) \] to \[ \mathcal{B}(F(a'),b') \] **Puzzle.** Can somehow say how we define this map? It's my duty to explain this, but someone probably knows already. The key point is that to get this map is built from a pair \\( (f,g) \\) consisting of a morphism \\(g: b \to b'\\) going _forwards_ from \\(b\\) to \\(b'\\), and a morphism \\(f: a' \to a\\) going _backwards_ from \\(a'\\) to \\(a\\). That backwardsness is why we need \\(\mathcal{A}^\textrm{op}\\).`

I think in my diagram I have defined it at least for the case where \(g\) is the identity. Due to the fact that f is in the opposite category, we can define the map from \(\mathcal{A}(F(a),b)\) to \(\mathcal{A}(F(a'),b)\) by the composite \(h \mapsto F(f) \circ h\).

`I think in my diagram I have defined it at least for the case where \\(g\\) is the identity. Due to the fact that f is in the opposite category, we can define the map from \\(\mathcal{A}(F(a),b)\\) to \\(\mathcal{A}(F(a'),b)\\) by the composite \\(h \mapsto F(f) \circ h\\).`

I think you got your adjunctions backward John.

You wrote,

implying that,

\[b \text{ in } Obj(\mathcal{B}),\]

however next you wrote,

implying that,

\[b \text{ in } Obj(\mathcal{A}).\]

`I think you got your adjunctions backward John. You wrote, >This functor sends any pair \\(a, b\\) consisting of an object \\(a\\) in \\(\mathcal{A}\\) and an object \\(b\\) in \\(\mathcal{B}\\) to the set implying that, \\[b \text{ in } Obj(\mathcal{B}),\\] however next you wrote, >\[ \mathcal{A}(F(a),b) . \] implying that, \\[b \text{ in } Obj(\mathcal{A}).\\]`

Dan wrote:

There are a couple of different ways to get your hands on a functor \(F: \mathcal{A} \times \mathcal{B} \times \mathcal{C} \) . Awodey is assuming we have categories \(\mathcal{A} , \mathcal{B}, \mathcal{C} \) and two maps:

A) a map sending each pair of objects \((a,b) \in \mathbf{Ob}(\mathcal{A}) \times \mathbf{Ob}(\mathcal{B})\) to an object of \(\mathcal{C}\);

B) a map I'll call \(F\) sending each pair of morphisms \((f,g) \in \mathbf{Mor}(\mathcal{A}) \times \mathbf{Mor}(\mathcal{B})\) to a morphism of \(\mathcal{C}\).

He gives a necessary and sufficient condition for this data to come from a (unique) functor from \(\mathcal{A} \times \mathcal{B}\) to \( \mathcal{C} \). Namely, we need

\(F\) preserves composition in each argument separately and

The

interchange law\( F(f,1) \circ F(1,g) = F(1,g) \circ F(f,1) \) holds, where I'm writing \(1\) for a bunch of different identity morphisms (the only ones that make the equation parse.)But there's another equivalent way to state conditions 1 and 2, which is sometimes just as easy to check. Namely, we can simply require that

$$ F(1_x,1_y) = 1_{(x,y)} $$ and

$$ F(f,g) \circ F(f',g') = F(f \circ f', g \circ g') .$$ This just says straight out that our would-be functor is a functor!

`Dan wrote: > I'm not sure if this relevant for the current discussion, but I wanted to point out that if a map is functorial in each argument it's not a sufficient condition to conclude that it's a functor. We need an additional coherence condition, known as the "interchange law"; for example, see the bifunctor lemma stated in [chapter 7](https://www.andrew.cmu.edu/course/80-413-713/notes/chap07.pdf) from Awodey's book. There are a couple of different ways to get your hands on a functor \\(F: \mathcal{A} \times \mathcal{B} \times \mathcal{C} \\) . Awodey is assuming we have categories \\(\mathcal{A} , \mathcal{B}, \mathcal{C} \\) and two maps: A) a map sending each pair of objects \\((a,b) \in \mathbf{Ob}(\mathcal{A}) \times \mathbf{Ob}(\mathcal{B})\\) to an object of \\(\mathcal{C}\\); B) a map I'll call \\(F\\) sending each pair of morphisms \\((f,g) \in \mathbf{Mor}(\mathcal{A}) \times \mathbf{Mor}(\mathcal{B})\\) to a morphism of \\(\mathcal{C}\\). He gives a necessary and sufficient condition for this data to come from a (unique) functor from \\(\mathcal{A} \times \mathcal{B}\\) to \\( \mathcal{C} \\). Namely, we need 1. \\(F\\) preserves composition in each argument separately and 2. The **interchange law** \\( F(f,1) \circ F(1,g) = F(1,g) \circ F(f,1) \\) holds, where I'm writing \\(1\\) for a bunch of different identity morphisms (the only ones that make the equation parse.) But there's another equivalent way to state conditions 1 and 2, which is sometimes just as easy to check. Namely, we can simply require that \[ F(1_x,1_y) = 1_{(x,y)} \] and \[ F(f,g) \circ F(f',g') = F(f \circ f', g \circ g') .\] This just says straight out that our would-be functor is a functor!`

Keith wrote:

Yes, that should be \(\mathcal{B}(F(a),b)\). I'll fix it. Thanks!

`Keith wrote: > however next you wrote, >\[ \mathcal{A}(F(a),b) . \] Yes, that should be \\(\mathcal{B}(F(a),b)\\). I'll fix it. Thanks!`

I wrote:

Peter wrote:

Yes, right!

Thanks to Dan's remark about Steve Awodey's book, expanded on here, we can get the desired map

$$ \mathcal{B}(F(a),b) \to \mathcal{B}(F(a'),b') $$ as follows. First use \(f: a' \to a\) to cook up a map

$$ \mathcal{B}(F(a),b) \to \mathcal{B}(F(a'),b) . $$ Then use \(g: b \to b'\) to cook up a map

$$ \mathcal{B}(F(a'),b) \to \mathcal{B}(F(a'),b') $$ Finally, compose these two maps to get the job done:

$$ \mathcal{B}(F(a),b) \to \mathcal{B}(F(a'),b) \to \mathcal{B}(F(a'),b') . $$ You explained the first step, where we use \(f : a' \to a\). This gives a map

$$ \mathcal{B}(F(a),b) \to \mathcal{B}(F(a'),b) $$ that maps any morphism \(h\) to \(h \circ F(f)\).

`I wrote: > If we have a pair of morphisms \\(f: a' \to a\\) and \\(g: b \to b'\\) this functor gives us a map from > \[ \mathcal{B}(F(a),b) \] > to > \[ \mathcal{B}(F(a'),b') \] > **Puzzle.** Can somehow say how we define this map? Peter wrote: > I think in my diagram I have defined it at least for the case where \\(g\\) is the identity. Due to the fact that f is in the opposite category, we can define the map from \\(\mathcal{A}(F(a),b)\\) to \\(\mathcal{A}(F(a'),b)\\) by the composite \\(h \mapsto F(f) \circ h\\). Yes, right! Thanks to Dan's remark about Steve Awodey's book, expanded on [here](https://forum.azimuthproject.org/discussion/comment/19552/#Comment_19552), we can get the desired map \[ \mathcal{B}(F(a),b) \to \mathcal{B}(F(a'),b') \] as follows. First use \\(f: a' \to a\\) to cook up a map \[ \mathcal{B}(F(a),b) \to \mathcal{B}(F(a'),b) . \] Then use \\(g: b \to b'\\) to cook up a map \[ \mathcal{B}(F(a'),b) \to \mathcal{B}(F(a'),b') \] Finally, compose these two maps to get the job done: \[ \mathcal{B}(F(a),b) \to \mathcal{B}(F(a'),b) \to \mathcal{B}(F(a'),b') . \] You explained the first step, where we use \\(f : a' \to a\\). This gives a map \[ \mathcal{B}(F(a),b) \to \mathcal{B}(F(a'),b) \] that maps any morphism \\(h\\) to \\(h \circ F(f)\\).`

What is happening to cause a morphism,

\[f: a' \to a\]

to be flipped backward when being mapped to,

$$\mathcal{B}(F(f),b) : \mathcal{B}(F(a),b) \to \mathcal{B}(F(a'),b) ? $$

`>First use \\(f: a' \to a\\) to cook up a map >\[ \mathcal{B}(F(a),b) \to \mathcal{B}(F(a'),b) . \] What is happening to cause a morphism, \\[f: a' \to a\\] to be flipped backward when being mapped to, \[\mathcal{B}(F(f),b) : \mathcal{B}(F(a),b) \to \mathcal{B}(F(a'),b) ? \]`

A functor \(\alpha : (A^{op} \times B) \to Set\) is called an anafunctor from A to B correct?

`A functor \\(\alpha : (A^{op} \times B) \to Set\\) is called an anafunctor from A to B correct?`

Christopher, I think you're looking for profunctors. Anafunctors are somewhat different.

`Christopher, I think you're looking for [profunctors](https://ncatlab.org/nlab/show/profunctor). Anafunctors are [somewhat different](https://ncatlab.org/nlab/show/anafunctor).`

Yes. You are right.

`Yes. You are right.`

Keith wrote:

Peter Addor gave the formula for this map. It sends any guy

$$ h \in \mathcal{B}(F(a),b) $$ to

$$ h \circ F(f) \in \mathcal{B}(F(a'),b) .$$ That is, it sends any guy

$$ h: F(a) \to b $$ to

$$ h \circ F(f) : F(a') to b .$$ We are

precomposingwith \(F(f)\).If you think about this, you'll see why we need \(f: a' \to a\), not \(f: a \to a'\).

Postcomposingdoes not cause this flip.Simply put: if you're riding from Philadelphia to New York, and you want to extend your trip, you can either postcompose with a trip from New York to Boston, or precompose with a trip from Washington DC to Philadelphia.

The second option, stretching out our trip so it includes Washington DC, does not require a trip from your original starting point (Philadelphia) to your new one (Washington DC). It requires a trip

the other way, from Washington DC to Philadelphia! This is the 'flip'.It doesn't feel like a flip when you put it this way; it seems utterly reasonable.

We will talk about this more later....

`Keith wrote: > What is happening to cause a morphism, > \\[f: a' \to a\\] > to be flipped backward when being mapped to, > \[\mathcal{B}(F(f),b) : \mathcal{B}(F(a),b) \to \mathcal{B}(F(a'),b) ? \] Peter Addor gave the formula for this map. It sends any guy \[ h \in \mathcal{B}(F(a),b) \] to \[ h \circ F(f) \in \mathcal{B}(F(a'),b) .\] That is, it sends any guy \[ h: F(a) \to b \] to \[ h \circ F(f) : F(a') to b .\] We are _precomposing_ with \\(F(f)\\). If you think about this, you'll see why we need \\(f: a' \to a\\), not \\(f: a \to a'\\). _Postcomposing_ does not cause this flip. Simply put: if you're riding from Philadelphia to New York, and you want to extend your trip, you can either postcompose with a trip from New York to Boston, or precompose with a trip from Washington DC to Philadelphia. The second option, stretching out our trip so it includes Washington DC, does not require a trip from your original starting point (Philadelphia) to your new one (Washington DC). It requires a trip _the other way_, from Washington DC to Philadelphia! This is the 'flip'. It doesn't feel like a flip when you put it this way; it seems utterly reasonable. We will talk about this more later....`

I have been confused by the 'op' thing for quite a while. On reading Anindya's answer:

I reckon this is a good way to approach the issue, but my brain fails to think out anything. :-/ @Anindya Could you perhaps illustrate a bit more details of the thinking process (even just some informal hints)?

On that note, I notice many textbooks use the 'op' notation without really explicitly explaining why, perhaps because it is too obvious for mathematically better-equipped readers. I see @John might still explain this in his latest lectures, so this course is really making a difference for beginner-beginners. =D>

`I have been confused by the 'op' thing for quite a while. On reading [Anindya's answer](https://forum.azimuthproject.org/discussion/comment/19538/#Comment_19538): >If you think about how this might works on pairs of morphisms \\((f, g)\\) you'll notice it has to be contravariant in the first variable and covariant in the second one. Hence it's a functor from \\(\mathcal{C}^{op} \times \mathcal{C}\\) to \\(\textbf{Set}\\). I reckon this is a good way to approach the issue, but my brain fails to think out anything. :-/ @Anindya Could you perhaps illustrate a bit more details of the thinking process (even just some informal hints)? On that note, I notice many textbooks use the 'op' notation without really explicitly explaining why, perhaps because it is too obvious for mathematically better-equipped readers. I see @John might still explain this in his latest lectures, so this course is really making a difference for beginner-beginners. =D>`

\(\mathbf{op}: \mathcal{C} \to \mathcal{C}^{op}\) is a functor.

In short, it does nothing to objects but flips arrows around.

Puzzle:Prove that \(\mathbf{op}: \mathcal{C} \to \mathcal{C}^{op}\) is a functor.`\\(\mathbf{op}: \mathcal{C} \to \mathcal{C}^{op}\\) is a functor. In short, it does nothing to objects but flips arrows around. **Puzzle:** Prove that \\(\mathbf{op}: \mathcal{C} \to \mathcal{C}^{op}\\) is a functor.`

No, there is no such thing as a functor \(\mathbf{op}: \mathcal{C} \to \mathcal{C}^{\mathrm{op}}\). Functors can't 'flip arrows around', since a functor \(F\) maps a morphism \(f : x \to y\) to a morphism \(F(f) : F(x) \to F(y)\).

This is a great example of a level slip! What we really have is a functor

$$ \mathbf{op} : \mathbf{Cat} \to \mathbf{Cat} $$ This functor sends each object of \(\mathbf{Cat} \) - that is, each category \(\mathcal{C}\) - to its opposite:

$$ \mathbf{op}(\mathcal{C}) = \mathcal{C}^{\mathrm{op}} $$ This functor send each morphism of \(\mathbf{Cat} \) - that is, each functor \(F: \mathcal{C} \to \mathcal{D} \) - to some obvious thing.

Puzzle.What is this obvious thing?`No, there is no such thing as a functor \\(\mathbf{op}: \mathcal{C} \to \mathcal{C}^{\mathrm{op}}\\). Functors can't 'flip arrows around', since a functor \\(F\\) maps a morphism \\(f : x \to y\\) to a morphism \\(F(f) : F(x) \to F(y)\\). This is a great example of a level slip! What we really have is a functor \[ \mathbf{op} : \mathbf{Cat} \to \mathbf{Cat} \] This functor sends each object of \\(\mathbf{Cat} \\) - that is, each category \\(\mathcal{C}\\) - to its opposite: \[ \mathbf{op}(\mathcal{C}) = \mathcal{C}^{\mathrm{op}} \] This functor send each morphism of \\(\mathbf{Cat} \\) - that is, each functor \\(F: \mathcal{C} \to \mathcal{D} \\) - to some obvious thing. **Puzzle.** What is this obvious thing?`

Julio wrote:

Good! This will build up the desire in you to do lots of calculations, to resolve this confusion.

For starters, do you understand what the category \(\mathcal{C}^{\mathbf{op}}\) is?

If so, the next step is to understand why there is no functor

$$ \mathrm{hom} : \mathcal{C} \times \mathcal{C} \to \mathrm{Set} $$ sending each pair of objects \( (c,c') \) to the 'homset' \(\mathcal{C}(c,c')\) - that is, the set of morphisms from \(c\) to \(c'\).

The best possible way is for you to try to define this (nonexistent) functor and see what goes wrong. I've told you what it does to an object of \( \mathcal{C} \times \mathcal{C} \) - that is, a pair \( (c,c')\) of objects in \(\mathcal{C}\). So your job is to define what this functor does to

morphisms.In other words, given

$$ (f,f'): (c,c') \to (d,d') ,$$ try to cook up a map from \(\mathcal{C}(c,c')\) to \(\mathcal{C}(d,d')\).

When you try this, and see exactly why it doesn't work, you'll be ready to see why we

dohave a functor$$ \mathrm{hom} : \mathcal{C}^{\mathrm{op}} \times \mathcal{C} \to \mathrm{Set} $$ You can then define what this does to morphisms, and show that it

doeswork.There's really nothing better, when learning math, than just doing calculatiions and seeing what happens.

Watchingpeople do math is like watching the Olympics. It's fun, but it doesn't make you able to run faster. In the sort of category theory we're doing now, the calculations are all really easy. It just takes a bit of courage to dive and try them.But fear not! I

willexplain the hom-functor$$ \mathrm{hom} : \mathcal{C}^{\mathrm{op}} \times \mathcal{C} \to \mathrm{Set} $$ I

needto explain it, to really explain adjoint functors!But I decided to try, at first, to give people a bit of intuition about adjoint functors before delving into this matter.

`Julio wrote: > I have been confused by the 'op' thing for quite a while. Good! This will build up the desire in you to do lots of calculations, to resolve this confusion. <img src = "http://math.ucr.edu/home/baez/emoticons/tongue2.gif"> For starters, do you understand what the category \\(\mathcal{C}^{\mathbf{op}}\\) is? If so, the next step is to understand why there is no functor \[ \mathrm{hom} : \mathcal{C} \times \mathcal{C} \to \mathrm{Set} \] sending each pair of objects \\( (c,c') \\) to the 'homset' \\(\mathcal{C}(c,c')\\) - that is, the set of morphisms from \\(c\\) to \\(c'\\). The best possible way is for you to try to define this (nonexistent) functor and see what goes wrong. I've told you what it does to an object of \\( \mathcal{C} \times \mathcal{C} \\) - that is, a pair \\( (c,c')\\) of objects in \\(\mathcal{C}\\). So your job is to define what this functor does to _morphisms_. In other words, given \[ (f,f'): (c,c') \to (d,d') ,\] try to cook up a map from \\(\mathcal{C}(c,c')\\) to \\(\mathcal{C}(d,d')\\). When you try this, and see exactly why it doesn't work, you'll be ready to see why we _do_ have a functor \[ \mathrm{hom} : \mathcal{C}^{\mathrm{op}} \times \mathcal{C} \to \mathrm{Set} \] You can then define what this does to morphisms, and show that it _does_ work. There's really nothing better, when learning math, than just doing calculatiions and seeing what happens. _Watching_ people do math is like watching the Olympics. It's fun, but it doesn't make you able to run faster. In the sort of category theory we're doing now, the calculations are all really easy. It just takes a bit of courage to dive and try them. But fear not! I _will_ explain the hom-functor \[ \mathrm{hom} : \mathcal{C}^{\mathrm{op}} \times \mathcal{C} \to \mathrm{Set} \] I _need_ to explain it, to really explain adjoint functors! But I decided to try, at first, to give people a bit of intuition about adjoint functors before delving into this matter.`

Whoops! Especially after I chastised someone today for level slipping with relations...

Anyways, thanks for pointing that out.

`>No, there is no such thing as a functor \\(\mathbf{op}: \mathcal{C} \to \mathcal{C}^{\mathrm{op}}\\). Functors can't 'flip arrows around', since a functor \\(F\\) maps a morphism \\(f : x \to y\\) to a morphism \\(F(f) : F(x) \to F(y)\\). >This is a great example of a level slip! Whoops! Especially after I chastised someone today for level slipping with relations... Anyways, thanks for pointing that out.`

John asked in comment #19:

I think that the functor \(\mathbf{op}(F)\) behaves the same way as the functor \(F\) on both objects and morphisms:

So, I would be tempted to say that the \(\mathbf{op}\) functor sends each functor \(F\) to itself, that is, \(\mathbf{op}(F) = F\).

`John asked in [comment #19](https://forum.azimuthproject.org/discussion/comment/19630/#Comment_19630): > **Puzzle.** What is this obvious thing? I think that the functor \\(\mathbf{op}(F)\\) behaves the same way as the functor \\(F\\) on both objects and morphisms: - On objects, \\(\mathbf{op}(F) : \mathrm{ob}(\mathcal{C}^{\mathrm{op}}) \to \mathrm{ob}(\mathcal{D}^{\mathrm{op}})\\). But objects in the opposite category are the same objects as in the original category, that is, \\(\mathrm{ob}(\mathcal{C}^{\mathrm{op}}) = \mathrm{ob}(\mathcal{C})\\); so the functor \\(\mathbf{op}(F) : \mathrm{ob}(\mathcal{C}) \to \mathrm{ob}(\mathcal{D})\\) can map objects the same way as \\(F\\) does. - On morphisms, \\(\mathbf{op}(F) : \mathcal{C}^{\mathrm{op}}(C', C) \to \mathcal{D}^{\mathrm{op}}(\mathbf{op}(F)(C'), \mathbf{op}(F)(C))\\) for any \\(C, C' \in \mathrm{ob}(\mathcal{C})\\). The opposite category reverses the morphisms, that is, \\(\mathcal{C}^{\mathrm{op}}(C', C) = \mathcal{C}(C, C')\\); so the functor \\(\mathbf{op}(F) : \mathcal{C}(C, C') \to \mathcal{D}(FC, FC')\\) can map morphisms the same way as \\(F\\) does. So, I would be tempted to say that the \\(\mathbf{op}\\) functor sends each functor \\(F\\) to itself, that is, \\(\mathbf{op}(F) = F\\).`

So I think I got why we need the opposite category to send pairs of objects to homsets. As seen in the picture above in order to get from \(\mathcal{C}(a,b)\) to \(\mathcal{C}(a',b)\), we need to precompose f so that the arrows compose.

Now I have a question about how the homfunctor preserves composition. I will use the same example with two objects and one non-trivial morphism above to pose the question.

If we have two composable morphisms \( \mathcal{C}(f,1_{b'}) \circ \mathcal{C}(1_a,g) = \mathcal{C}(f,g)\) , the functor needs to preserve this via \( \mathcal{C}(f \circ 1_a,1_{b'} \circ g)\). But the order doesn't seem right in that \(f \circ 1_a\) and \(1_{b'} \circ g\) are both not composable. What am I doing wrong here?

Edit: Oops \(1_{b'} \circ g\) does compose.

`![homfunctor_opposite_category](http://aether.co.kr/images/homfunctor_op.svg) So I think I got why we need the opposite category to send pairs of objects to homsets. As seen in the picture above in order to get from \\(\mathcal{C}(a,b)\\) to \\(\mathcal{C}(a',b)\\), we need to precompose f so that the arrows compose. Now I have a question about how the homfunctor preserves composition. I will use the same example with two objects and one non-trivial morphism above to pose the question. If we have two composable morphisms \\( \mathcal{C}(f,1_{b'}) \circ \mathcal{C}(1_a,g) = \mathcal{C}(f,g)\\) , the functor needs to preserve this via \\( \mathcal{C}(f \circ 1_a,1_{b'} \circ g)\\). But the order doesn't seem right in that \\(f \circ 1_a\\) and \\(1_{b'} \circ g\\) are both not composable. What am I doing wrong here? Edit: Oops \\(1_{b'} \circ g\\) does compose.`

@Michael: The composition the functor must preserve is composition in \(\mathcal{C}^{op}\times \mathcal{C}\)

How does this composition work? It takes two pairs of morphisms:

and returns the composite pair:

So the rule is \((f', g')\circ (f, g) = (f\circ f', g'\circ g)\), ie the first coordinate is the "other way round".

Now what are we trying to check? We want

The left hand side is a set map sending \(k\mapsto g'\circ (g\circ k\circ f)\circ f'\)

The right hand side is a set map sending \(k\mapsto (g'\circ g)\circ k\circ (f\circ f')\)

... and these two are the same by associativity.

`@Michael: The composition the functor must preserve is composition in \\(\mathcal{C}^{op}\times \mathcal{C}\\) How does this composition work? It takes two pairs of morphisms: > \\((f, g)\\) where \\(f : a' \rightarrow a\\) and \\(g : b \rightarrow b'\\) > \\((f', g')\\) where \\(f' : a'' \rightarrow a'\\) and \\(g : b' \rightarrow b''\\) and returns the composite pair: > \\((f\circ f', g'\circ g)\\) where \\(f\circ f' : a'' \rightarrow a\\) and \\(g'\circ g : b \rightarrow b''\\) So the rule is \\((f', g')\circ (f, g) = (f\circ f', g'\circ g)\\), ie the first coordinate is the "other way round". Now what are we trying to check? We want > \\(\mathcal{C}(f', g')\circ \mathcal{C}(f, g) = \mathcal{C}((f', g')\circ (f, g)) = \mathcal{C}(f\circ f', g'\circ g)\\) The left hand side is a set map sending \\(k\mapsto g'\circ (g\circ k\circ f)\circ f'\\) The right hand side is a set map sending \\(k\mapsto (g'\circ g)\circ k\circ (f\circ f')\\) ... and these two are the same by associativity.`

@Anindya

Ahh the composition rule is also backwards. \(\mathcal{C}^{op}\) is trickier than it seems. Thanks a bunch Anindya. I would have gotten lost everywhere in opposite land had I not known this.

`@Anindya >So the rule is \\((f', g')\circ (f, g) = (f\circ f', g'\circ g)\\), ie the first coordinate is the "other way round". Ahh the composition rule is also backwards. \\(\mathcal{C}^{op}\\) is trickier than it seems. Thanks a bunch Anindya. I would have gotten lost everywhere in opposite land had I not known this.`

For those of you working out the homfunctor and why the first coordinate needs to be contravariant, I drew out the simple example used above in my comment #23. It might help calculate how this functor is working. The left diagram shows the how it maps the objects and the right diagram shows how it maps the morphisms. Let me know if there are mistakes.

Edit: Now that I think about it, this is so natural since morphisms and compositions have directionality which puts the start and target on opposite ends of the morphism and composition must start where the previous left off.

`For those of you working out the homfunctor and why the first coordinate needs to be contravariant, I drew out the simple example used above in my comment #23. It might help calculate how this functor is working. The left diagram shows the how it maps the objects and the right diagram shows how it maps the morphisms. Let me know if there are mistakes. ![How Homfunctor maps objects and morphisms](http://aether.co.kr/images/homfunctor_ob_mor.svg) Edit: Now that I think about it, this is so natural since morphisms and compositions have directionality which puts the start and target on opposite ends of the morphism and composition must start where the previous left off.`

Here's an easy analogy.

View morphisms \(\text{Hom}(-,X)\) in a category like extension cords with the inputs not plugged into a wall outlet.

\[ \overset{\text{black cord}}\longrightarrow \text{Lamp} \]

Then the fact that pre-composition runs backward is analogous to the fact that if I want to extend my extension cord to get closer to a wall outlet, then cords are composed backwards,

\[ \overset{\text{beige cord}}\longrightarrow \ \overset{\text{black cord}}\longrightarrow \text{Lamp} \]

here, we're using the \(\text{beige cord}\) to get the \(\text{black cord}\)'s output closer to a desired input. If we can't, we get another cord and (throwing saefty concerns to the wind) we keep daisy chaining on cords until we can get to a wall outlet (or else you're out in a deserted area and it's actually impossible).

`Here's an easy analogy. View morphisms \\(\text{Hom}(-,X)\\) in a category like extension cords with the inputs not plugged into a wall outlet. \\[ \overset{\text{black cord}}\longrightarrow \text{Lamp} \\] Then the fact that pre-composition runs backward is analogous to the fact that if I want to extend my extension cord to get closer to a wall outlet, then cords are composed backwards, \\[ \overset{\text{beige cord}}\longrightarrow \ \overset{\text{black cord}}\longrightarrow \text{Lamp} \\] here, we're using the \\(\text{beige cord}\\) to get the \\(\text{black cord}\\)'s output closer to a desired input. If we can't, we get another cord and (throwing saefty concerns to the wind) we keep daisy chaining on cords until we can get to a wall outlet (or else you're out in a deserted area and it's actually impossible).`

So here's my attempt at why the homset functor \(\hom : \mathcal{C}^\mathrm{op} \times \mathcal{C} \to \mathbf{Set}\) has to be contravariant in the first argument. Suppose we attempt to define the homset functor as \(\hom : \mathcal{C} \times \mathcal{C} \to \mathbf{Set}\) such that any pair of objects \((c,c')\) is mapped to the set of morphisms \(\mathcal{C}(c,c')\) between these objects. We have to define what happens the morphisms \( (f,f') : (c,c') \to (d,d') \), and applying the homset functor to the morphism pair should give us a map sending morphisms in \(\mathcal{C}(c,c')\) to morphisms in \(\mathcal{C}(d,d')\).

Let \(h \) be any element of \(\mathcal{C}(c,c')\) and \(h'\) an element of \(\mathcal{C}(d,d')\) such that \(\hom (f,f') (h)=h'\). I drew the following diagram (I actually drew a bunch of arrows for each homset, but that's hard to do in LaTeX):

$$ \begin{matrix} & & f' & & \\ & c' & \rightarrow & d' &\\ h & \uparrow & & \uparrow & h'\\ & c & \rightarrow & d &\\ & & f & & \\ \end{matrix} $$ From this diagram, we get two compositions \(f'h : c \to d'\) and \(h'f : c \to d' \), so the morphism \((f,f')\) ends up sending the homset \(\mathcal{C}(c,c')\) to \(\mathcal{C}(c,d')\); not quite what we want. But it's easy to see that if the arrow \(f\) was turned around, we could precompose \(h\) with it.

In \(\mathcal{C}^\mathrm{op}\), \(f : d \to c\) as desired, so we get the following commutative diagram:

$$ \begin{matrix} & & f' & & \\ & c' & \rightarrow & d' &\\ h & \uparrow & & \uparrow & h'\\ & c & \leftarrow & d &\\ & & f & & \\ \end{matrix} $$ where \(h' = f'hf\), which looks a bit like conjugation in a group. So the functor \(\hom\) sends morphisms in \(\mathcal{C}^\mathrm{op} \times \mathcal{C} \) to functions between homsets defined by the previous formula.

`So here's my attempt at why the homset functor \\(\hom : \mathcal{C}^\mathrm{op} \times \mathcal{C} \to \mathbf{Set}\\) has to be contravariant in the first argument. Suppose we attempt to define the homset functor as \\(\hom : \mathcal{C} \times \mathcal{C} \to \mathbf{Set}\\) such that any pair of objects \\((c,c')\\) is mapped to the set of morphisms \\(\mathcal{C}(c,c')\\) between these objects. We have to define what happens the morphisms \\( (f,f') : (c,c') \to (d,d') \\), and applying the homset functor to the morphism pair should give us a map sending morphisms in \\(\mathcal{C}(c,c')\\) to morphisms in \\(\mathcal{C}(d,d')\\). Let \\(h \\) be any element of \\(\mathcal{C}(c,c')\\) and \\(h'\\) an element of \\(\mathcal{C}(d,d')\\) such that \\(\hom (f,f') (h)=h'\\). I drew the following diagram (I actually drew a bunch of arrows for each homset, but that's hard to do in LaTeX): \[ \begin{matrix} & & f' & & \\\\ & c' & \rightarrow & d' &\\\\ h & \uparrow & & \uparrow & h'\\\\ & c & \rightarrow & d &\\\\ & & f & & \\\\ \end{matrix} \] From this diagram, we get two compositions \\(f'h : c \to d'\\) and \\(h'f : c \to d' \\), so the morphism \\((f,f')\\) ends up sending the homset \\(\mathcal{C}(c,c')\\) to \\(\mathcal{C}(c,d')\\); not quite what we want. But it's easy to see that if the arrow \\(f\\) was turned around, we could precompose \\(h\\) with it. In \\(\mathcal{C}^\mathrm{op}\\), \\(f : d \to c\\) as desired, so we get the following commutative diagram: \[ \begin{matrix} & & f' & & \\\\ & c' & \rightarrow & d' &\\\\ h & \uparrow & & \uparrow & h'\\\\ & c & \leftarrow & d &\\\\ & & f & & \\\\ \end{matrix} \] where \\(h' = f'hf\\), which looks a bit like conjugation in a group. So the functor \\(\hom\\) sends morphisms in \\(\mathcal{C}^\mathrm{op} \times \mathcal{C} \\) to functions between homsets defined by the previous formula.`

I drew out the left and right adjoint functors and the underlying naturality square in one picture because I like to draw diagrams to help me memorize the relationships. This one might be intimidating because there is so much going on but once your eyes adjust to the third dimension its pretty straight forward.

I drew this so that morphisms are lines, functors are planes and natural transformations are cubes. The naturality square for the natural isomorphism is shown by the green double arrows and the functors as green planes.

`![adjoint functor](http://aether.co.kr/images/adjoint_functor.svg) I drew out the left and right adjoint functors and the underlying naturality square in one picture because I like to draw diagrams to help me memorize the relationships. This one might be intimidating because there is so much going on but once your eyes adjust to the third dimension its pretty straight forward. I drew this so that morphisms are lines, functors are planes and natural transformations are cubes. The naturality square for the natural isomorphism is shown by the green double arrows and the functors as green planes.`

Michael - wow, that's great! That's the image to have in mind. I will copy this over to Lecture 54, where it can serve as a hint for Puzzle 168. Nobody has solved Puzzle 168 yet!

`Michael - wow, that's great! That's the image to have in mind. I will copy this over to [Lecture 54](https://forum.azimuthproject.org/discussion/2277/lecture-54-chapter-3-tying-up-loose-ends/p1), where it can serve as a hint for Puzzle 168. Nobody has solved Puzzle 168 yet!`