Lecture 53 - Chapter 3: Free and Forgetful Functors

John Baez · June 2018

The main reason mathematicians like category theory is that there are tons of categories where the objects are 'mathematical gadgets' and the morphisms are maps between these. Thus, category theory helps organize the study of math. Some examples include:

$\mathbf{Set}$, the category with sets as objects and functions as morphisms.
$\mathbf{Preord}$, the category with preorders as objects and monotone functions as morphisms.
$\mathbf{Poset}$, the category with posets as objects and monotone functions as morphisms.
$\mathbf{Cat}$, the category with categories as objects and functors as morphisms.
$\mathbf{Mon}$, the category with monoids as objects and monoid homomorphisms as morphisms.
$\mathbf{Grp}$, the category with groups as objects and group homomorphisms as morphisms.

I could go on a lot longer, but I'm mainly sticking to examples we've already discussed. And since this is a class on category theory, all these examples can be seen as various kinds of categories!

For example, we can think of a set as a category with only identity morphisms - the set gives the objects. A preorder is a category where there's at most one morphism between any pair of objects, and a poset is a preorder where isomorphic objects are equal. We can think of a monoid as category with one object: the elements of the monoid give the morphisms. From this point of view, a group is a category with one object whose morphisms are all isomorphisms!

One thing mathematicians like is functors between categories of mathematical gadgets. Often these functors come in pairs: a left adjoint and a right adjoint! The right adjoint usually 'forgets' structure, so we call it a 'forgetful functor'. The left adjoint usually puts this structure back in, and we call it a 'free functor'. I should warn you right now that 'forgetful' and 'free' don't have precise definitions: rather, they convey a certain way of thinking about right and left adjoints.

To pick up this way of thinking, you need to think about examples. So, let's look at some!

There's a functor

$$ \text{Ob}: \mathbf{Cat} \to \mathbf{Set} $$ that forgets everything about a category except its objects. In other words, it sends any category $\mathcal{C}$ to its set of objects $\mathrm{Ob}(\mathcal{C})$, and sends any functor $F: \mathcal{C} \to \mathcal{D}$ to the function it defines on objects, which I've been calling just $F : \mathrm{Ob}(\mathcal{C}) \to \mathrm{Ob}(\mathcal{D})$. A more systematic name for it is $\mathrm{Ob}: \mathrm{Ob}(\mathcal{C}) \to \mathrm{Ob}(\mathcal{D})$.

It's easy to check that $\mathrm{Ob}$ is a functor. More interestingly, it has a left adjoint

$$ \mathrm{Disc}: \mathbf{Set} \to \mathbf{Cat} $$ which turns a set into a category! It does this in a pretty dull way, though - I already hinted at how: it takes any set $S$ and produces a category whose set of objects is $S$, with only identity morphisms. This is usually called the discrete category on the set $S$, but we could also call it the free category on the set $S$.

Since $\mathrm{Disc}$ is a functor, it must also send any function $f : S \to T$ between sets to a functor

$$ \mathrm{Disc}(f) : \mathrm{Disc}(S) \to \mathrm{Disc}(T) $$ between the corresponding discrete categories. It works in a simple way: on objects this functor is just the function $f$, and it does what it has to on morphisms, which are all identity morphisms: identities have to be sent to identities.

It's easy to check that $ \mathrm{Disc}: \mathbf{Set} \to \mathbf{Cat} $ is a functor. More interestingly, it's the left adjoint of $ \mathrm{Ob}: \mathbf{Cat} \to \mathbf{Set}$. Let's think about this!

Saying that $\mathrm{Disc}$ is the left adjoint of $\mathrm{Ob}$ means there's a natural one-to-one correspondence

$$ \alpha_{S,\mathcal{C}} : \mathbf{Cat}( \mathrm{Disc}(S), \mathcal{C} ) \to \mathbf{Set}( S, \mathrm{Ob}(\mathcal{C}) ) .$$ for every set $S$ and every category $\mathcal{C}$. Unraveling this a bit, it means there's a natural bijection between

$$ \text{ functors } G : \mathrm{Disc}(S) \to \mathcal{C} $$ and

$$ \text{ functions } g : S \to \mathrm{Ob}(\mathcal{C}) $$ It's easy to see how this bijection should work. If you give me a functor $G : \mathrm{Disc}(S) \to \mathcal{C} $, I look at what it does to objects, and that's the function $g$. Conversely, if you give me a function $g : S \to \mathrm{Ob}(\mathcal{C}) $, I give you the only functor $G : \mathrm{Disc}(S) \to \mathcal{C}$ that equals $g$ on objects: there will be no choice about what $G$ does to morphisms, since $\mathrm{Disc}(S)$ has only identity morphisms.

Puzzle 162. Show that this bijection is natural.

But this is just one of many examples!

Puzzle 163. Show the forgetful functor

$$ \text{Ob}: \mathbf{Cat} \to \mathbf{Set} $$ sending each category to its set of objects has a left adjoint

$$ \mathrm{Disc} : \mathbf{Set} \to \mathbf{Cat} $$ sending each set to the category with that set of objects and only identity morphisms. Show that $\text{Ob}$ also has a right adjoint.

Puzzle 164. A poset is a special sort of preorder, and a preorder is a special sort of category. Thus, we get functors from $\mathbf{Poset}$ to $\mathbf{Preord}$ and from $\mathbf{Preord}$ to $\mathbf{Cat}$. Does the functor from $\mathbf{Poset}$ to $\mathbf{Preord}$ have a left adjoint, a right adjoint or both? How about the functor from $\mathbf{Preord}$ to $\mathbf{Cat}$?

Puzzle 165. Does the forgetful functor from $\mathbf{Grp}$ to $\mathbf{Mon}$ have a right adjoint, a left adjoint or both?

To read other lectures go here.

Ken Scambler · June 2018

I'll have a stab at 164:

It has a left adjoint that generates an inverse element -x for every non-identity element x.

The inverse operation takes x to -x, -x to x, and the identity 0 to itself. The group equations follow: -x + x = x + -x = 0 and 0 = -0

This is like how integers can be freely generated from natural numbers.

I'll guess it has a right adjoint by analogy to the German/Italian example where the right adjoint threw away all the information into a crappy trivial mapping onto a single Italian. So I guess we melt the monoid down into the* trivial group with one element, where everything maps to id.

Left = generous, right = stingy!

Keith E. Peterson · June 2018

Ken Scambler wrote:

The inverse operation takes x to -x, -x to x, and the identity 0 to itself. The group equations follow: -x + x = x + -x = 0 and 0 = -0

I don't think that will work since it just swaps inversion.

However, $-x \mapsto x$, $x \mapsto x$, and $0 \mapsto 0$ I think will work.

The adjoint here takes a monoid and freely adds inverse elements, while it's right adjoint forgets what it means to be an inverse.

In the context of numbers, the adjoint is the multiplication of a natural number by $-1$, \[-n : \mathbb{N} \to \mathbb{Z},\] it's right adjoint is the absolute value, \[|z|: \mathbb{Z} \to \mathbb{N}.\]

John Baez · June 2018

Ken's formula for inverses:

The inverse operation takes $x$ to $-x$, $-x$ to $x$, and the identity 0 to itself.

works better than Keith's:

However, $-x \mapsto x$, $x \mapsto x$, and $0 \mapsto 0$ I think will work.

You're on the right track, Ken. But the case of building the integers from the natural numbers fails to illustrate some of the strange things that can happen. So try applying your procedure to the Boolean monoid! This is the monoid with two elements 0 and 1, and addition defined as follows:

$$ 0 + 0 = 0, \qquad 0 + 1 = 1, \qquad 1 + 0 = 1, \qquad 1 + 1 = 1 .$$ In the end everything will work out beautifully, and you're on the road to success, but there is a road bump.

John Baez · June 2018

Keith wrote approximately:

In the context of numbers, the adjoint is the multiplication of a natural number by $-1$,
$$ \begin{align} \mathbb{N} &\to \mathbb{Z} \\ n &\mapsto -n \end{align} $$ its right adjoint is the absolute value, $$ \begin{align}\mathbb{Z} &\to \mathbb{N}\\ z &\mapsto |z| \end{align} $$

That's not true. Also, you seem to be making a level slip here. We are looking for adjoint functors

$$ L : \mathbf{Mon} \to \mathbf{Grp}, \qquad R: \mathbf{Grp} \to \mathbf{Mon} $$ but you seem to be trying to invent adjoint functors from a particular monoid to a particular group. A group is a kind of monoid, and a monoid is a kind of category, so it does make sense to talk about adjoint functors between monoids (e.g. groups). But that's not what we were talking about.

We can look into this issue anyway, just for fun:

A functor between monoids is just the same as a monoid homomorphism. This is an example of one:

$$ \begin{align} \mathbb{N} &\to \mathbb{Z} \\ n &\mapsto -n \end{align} $$

but this is not:

$$ \begin{align}\mathbb{Z} &\to \mathbb{N}\\ z &\mapsto |z| \end{align} $$

because $|z_1 + z_2| \ne |z_1| + |z_2| $.

The only functor (i.e. monoid homomorphism) from $\mathbb{Z}$ to $\mathbb{N}$ is the one that sends every integer to zero. If you write down the definition of adjoint functor and apply it to this case, you'll see there are no adjoint functors between $\mathbb{N}$ and $\mathbb{Z}$.

Michael Hong · June 2018

I have a question about the forgetful functor $\mathbf{Preord} \stackrel{R_2}{\longrightarrow} \mathbf{Poset} $. How would this functor forget 2-cycles? Since we are keeping the objects, it seems to me there can be a choice of which arrow to forget but don't think it can be mapped to the other arrow coming back since source and target won't match. Does the whole cycle just get forgotten ie mapped into an identity?

Upon further pondering, I have another question. When going from $\mathbf{Poset} \stackrel{R_2}{\longrightarrow} \mathbf{Set} $, how exactly does the functor forget the arrows? Where do they get mapped to? In order to preserve source and target, all connected objects need to get mapped to one object?

Keith E. Peterson · June 2018

Hmm...

How about, since every group is a monoid, why not make $\mathbf{R}: \mathbf{Grp} \to \mathbf{Mon}$ simply the inclusion of groups into monoids, forgetting the inversion operation.

Also, I suppose if anything else, we could make a functor $\mathbf{Mon} \to \mathbf{Grp}$ by first taking any monoid and making a set from that monoid, $\mathbf{S} : \mathbf{Mon} \to \mathbf{Set}$; then taking that set and freely creating a group from that set, $\mathbf{T} : \mathbf{Set} \to \mathbf{Grp}$, since functors compose we get our desired functor, $\mathbf{L} = \mathbf{T}\circ\mathbf{S}$.

Then, I believe the following natural isomorphism is satisfied,

\[ \mathbf{Grp}[L(m),g] \cong \mathbf{Mon}[m,R(g)] \]

Keith E. Peterson · June 2018

Michael Hong wrote:

I have a question about the forgetful functor $\mathbf{Preord} \stackrel{R_2}{\longrightarrow} \mathbf{Poset} $. How would this functor forget 2-cycles? Since we are keeping the objects, it seems to me there can be a choice of which arrow to forget but don't think it can be mapped to the other arrow coming back since source and target won't match. Does the whole cycle just get forgotten ie mapped into an identity?

I think we're free to choose between, \[ x \sim y \mapsto x \leq y, \]

and,

\[ x \sim y \mapsto x = y, \]

Either way, the operation is destructive.

Christopher Upshaw · June 2018

Puzzle 163. Show there are functors
$$ \mathbf{Cat} \stackrel{R_1}{\longrightarrow} \mathbf{Preord} \stackrel{R_2}{\longrightarrow} \mathbf{Poset} \stackrel{R_3}{\longrightarrow} \mathbf{Set} $$ with left adjoints going back: $$ \mathbf{Set} \stackrel{L_3}{\longrightarrow} \mathbf{Poset} \stackrel{L_2}{\longrightarrow} \mathbf{Preord} \stackrel{L_1}{\longrightarrow} \mathbf{Cat} . $$ Hint: the composite $ R_3 R_2 R_1 : \mathbf{Cat} \to \mathbf{Set} $ is our friend $$ \text{Ob}: \mathbf{Cat} \to \mathbf{Set} ,$$ and the composite $L_1 L_2 L_3 : \mathbf{Set} \to \mathbf{Cat} $ is our friend $$ \mathrm{Disc} : \mathbf{Set} \to \mathbf{Cat} .$$

Wait, doesn't going to Poset skeletonise things? I.e. any connected* groupoid is taken to the poset $\{\ast\}$? So that the composition doesn't equal Ob?

Christopher Upshaw · June 2018

I don't think $\mathbf{Grp}[L(m),g] \cong \mathbf{Mon}[m,R(g)]$ is true with $\mathbf{L} = \mathbf{T}\circ\mathbf{S}$.

Let's look at $m = (bool, or), g = L(m)$.

Given $f \in [m, g]$ \[f(t) = f (t+t) =f(t)f(t)\] but the only element of g with that property is $\epsilon$. So there is exactly one morephism on the rhs.

But on the lhs, there are at least two, $x\mapsto \epsilon$ and $x \mapsto x$.

Ken Scambler · June 2018

Thanks John!

The problem with my approach on the boolean example seems to be that it's a bit hard to know what to do with -1 + -1. How do the negative elements behave when not directly combined with their inverse or id? I drew up a truth table, and -1 + -1 = -1 is the only one that doesn't kill associativity. Extracting ourselves from booleans, we could express the general rule as (-x + -x) = -(x + x), which feels nice, but I don't remember groups having a distributive law. I haven't done the working, but maybe this is too arbitrary to qualify. The general case also needs (-x + y) defined for the new elements...

My reasoning with integers was similarly wrong: integers are a free group from a single generator {.}, not the (N, +, 0) monoid. The integer behaviour for (-x + -x) or (-x + y) here uses special integer knowledge, not just general monoid structure, which we must exclusively use to construct the group.

My next hunch is that it might require the alternating red, black, red black thing we saw in Chapter 1, although I haven't thought this through at all. I've taken my intuition as far as it can go now, and really need to do some calculations.

Christopher Upshaw · June 2018

You can prove $(xx)^{-1}= x^{-1}x^{-1}$ in a group, its a consequence of canceling and asocitivity.\[(xy)(y^{-1}x^{-1})= x(yy^{-1})x^{-1}=xx^{-1}=1\]

Then let y = x. Man it's been a long time since I've used that.

Keith E. Peterson · June 2018

Christopher Upshaw wrote:

I don't think $\mathbf{Grp}[L(m),g] \cong \mathbf{Mon}[m,R(g)]$ is true with $\mathbf{L} = \mathbf{T}\circ\mathbf{S}$.

Let's look at $m = (bool, or), g = L(m)$.

Given $f : m\to g$ \[f(T) = f (TT) =f(T)f(T)\] but the only element of g with that property is $\epsilon$. So there is exactly one morephism on the rhs.

But on the lhs, there are at least two, $ x\mapsto \epsilon$ and $x \mapsto x$.

I don't understand your reasoning here. In which category does $f$ live in? And why are we using $T$?

Anindya Bhattacharyya · June 2018

re Puzzle 165 about adjoints for the forgetful functor $U : \textbf{Grp} \rightarrow \textbf{Mon}$:

I think people are on the right track in trying to construct a left adjoint as the free group on a monoid $M$ but the construction is trickier and involves words/quotients.

Specifically, we take words (ie finite sequences) comprising elements of $M$ and their formal inverses (ie tokens of the form $x^{-1}$ where $x \in M$).

We "reduce" these words as far as possible using these following rules:

• multiply together any adjacent "plain" elements – so $[x, y]$ becomes $[xy]$
• multiply together any adjacent "inverse" elements – so $[y^{-1}, x^{-1}]$ becomes $[(xy)^{-1}]$
• remove any adjacent pairs of elements and their inverses – so $[x, x^{-1}]$ becomes $[\ ]$
• remove any adjacent pairs of inverses and plain elements – so $[y^{-1}, y]$ becomes $[\ ]$
• remove any units or inverses of units – so $[1]$ becomes $[\ ]$, as does $[1^{-1}]$

To multiply two reduced words we concatenate them and reduce. The empty word is the identity, and every word has an inverse (reverse the order of terms and invert each one, so $[x, y^{-1}, z]^{-1} = [z^{-1}, y, x^{-1}]$).

So we have a group, which we'll call $FM$. We can check any monoid homomorphism from $M$ into the underlying monoid of a group $G$ can be uniquely extended to a group homomorphism $FM \rightarrow G$, and any such group homomorphism restricts to a monoid homomorphism $M \rightarrow UG$. So $F$ is left adjoint to $U$.

The right adjoint is simpler to construct – it just sends every monoid $M$ to its submonoid $RM$ of invertible elements (considered as a group). Then group homomorphisms $G \rightarrow RM$ correspond naturally to monoid homomorphisms $UG \rightarrow M$.

Christopher Upshaw · June 2018

Ah sorry. f is in Mon. And T is short for true, not your T. Bad choice on my part.

Keith E. Peterson · June 2018

To be really fair, a group is a lot like the product of a monoid with itself as an opposite category.

Especially since for any $f$ in our monoid $\mathbf{M}$,

\[f^{op} \circ f = id_{\mathbf{M}} = f\circ f^{op}.\]

Keith E. Peterson · June 2018

I know! Let's be extremely restrictive.

Let $\mathbf{R}$ be the functor that maps every group to the trivial monoid, and let $\mathbf{L}$ be the functor that maps every monoid to the trivial group.

Then,

\[ \mathbf{Grp}[\mathbf{L}(m),g] \cong \mathbf{Mon}[m,\mathbf{R}(g)] \\ \Leftrightarrow \\ \mathbf{Grp}[0_{\mathbf{Grp}},g] \cong \mathbf{Mon}[m,1_{\mathbf{Mon}}]. \]

Christopher Upshaw · June 2018

Hmmmmmm. That is true! Interesting.

That should work for any pair where R maps to the terminal object, and L maps to the initial object.

(The trivial group and monoid are both initial and terminal. Because the single element pointed set is both initial and terminal.)

Christopher Upshaw · June 2018

I wonder if that's the terminal or initial object in some sort of category of adjunctions.

Keith E. Peterson · June 2018

Christopher Upshaw wrote:

That should work for any pair where R maps to the terminal object, and L maps to the initial object.

I believe Puzzle 162 can be answered the same way using the initial objects and terminal objects of $\mathbf{Cat}$ and $\mathbf{Set}$.

Dan Oneata · July 2018

Keith wrote:

I believe Puzzle 162 can be answered the same way using the initial objects and terminal objects of $\mathbf{Cat}$ and $\mathbf{Set}$.

I'm not sure how to use this idea, so my attempt takes the long and tedious route.

Puzzle 162. Show that this bijection is natural.

The two functors in question are:

$$ \begin{align} \mathbf{Cat}(\mathrm{Disc}(-), =) &: \mathbf{Set}^{\mathrm{op}} \times \mathbf{Cat} \to \mathbf{Set} \\ \mathbf{Set}(-, \mathrm{Ob}(=)) &: \mathbf{Set}^{\mathrm{op}} \times \mathbf{Cat} \to \mathbf{Set}. \end{align} $$ We will check the naturality of the two functors in both arguments, which are denoted above by $-$ and $=$.

First, we show that for any morphism in $\mathbf{Cat}$, $F: \mathcal{C} \to \mathcal{D}$ (functor), the following diagram commutes:

$$ \begin{matrix} \mathbf{Cat}(\mathrm{Disc}(S), \mathcal{C}) & \rightarrow & \mathbf{Cat}(\mathrm{Disc}(S), \mathcal{D}) \\ \downarrow & & \downarrow \\ \mathbf{Set}(S, \mathrm{Ob}(\mathcal{C})) & \rightarrow & \mathbf{Set}(S, \mathrm{Ob}(\mathcal{D})) \end{matrix} $$ Written as an equation, this means:

$$ \mathbf{Set}(S, \mathrm{Ob}(F)) \circ \alpha_{S,\mathcal{C}} = \alpha_{S,D} \circ \mathbf{Cat}(\mathrm{Disc}(S), F). $$ For any functor $G : \mathrm{Disc}(S) \to \mathcal{C}$, we have:

$$ \begin{align} & (\mathbf{Set}(S, \mathrm{Ob}(F)) \circ \alpha_{S,\mathcal{C}})(G) \\ & = \text{{ composition }} \\ & \mathbf{Set}(S, \mathrm{Ob}(F))(\alpha_{S,\mathcal{C}}(G)) \\ & = \text{{ definition of the hom functor }} \\ & \alpha_{S,\mathcal{C}}(G) \circ \mathrm{Ob}(F) \\ & = \left\{ \; \alpha \text{ behaves like Ob on functors } \right\} \\ & \mathrm{Ob}(G) \circ \mathrm{Ob}(F) \\ & = \text{{ Ob preserves composition }} \\ & \mathrm{Ob}(G \circ F) \\ & = \left\{ \; \alpha \text{ behaves like Ob on functors } \right\} \\ & \alpha_{S,\mathcal{D}}(G \circ F)) \\ & = \text{{ definition of the hom functor }} \\ & \alpha_{S,\mathcal{D}}(\mathbf{Cat}(\mathrm{Disc}(S), F)(G))) \\ & = \text{{ composition }} \\ & (\alpha_{S,\mathcal{D}} \circ \mathbf{Cat}(\mathrm{Disc}(S), F))(G). \end{align} $$ Second, we show that for any morphism in $\mathbf{Set}$, $f: T \to S$ (function), the following diagram commutes:

$$ \begin{matrix} \mathbf{Cat}(\mathrm{Disc}(S), \mathcal{C}) & \rightarrow & \mathbf{Cat}(\mathrm{Disc}(T), \mathcal{C}) \\ \downarrow & & \downarrow \\ \mathbf{Set}(S, \mathrm{Ob}(\mathcal{C})) & \rightarrow & \mathbf{Set}(T, \mathrm{Ob}(\mathcal{C})) \end{matrix} $$ Written as an equation, this means:

$$ \mathbf{Set}(f, \mathrm{Ob}(\mathcal{C})) \circ \alpha_{S,\mathcal{C}} = \alpha_{T,\mathcal{C}} \circ \mathbf{Cat}(\mathrm{Disc}(f), \mathcal{C}). $$ For any functor $G : \mathrm{Disc}(S) \to \mathcal{C}$, we have:

$$ \begin{align} & (\mathbf{Set}(f, \mathrm{Ob}(\mathcal{C})) \circ \alpha_{S,\mathcal{C}})(G) \\ & = \text{{ composition }} \\ & \mathbf{Set}(f, \mathrm{Ob}(\mathcal{C}))(\alpha_{S,\mathcal{C}})(G)) \\ & = \text{{ definition of the hom functor }} \\ & f \circ \alpha_{S,\mathcal{C}}(G) \\ & = \left\{ \; \alpha \text{ behaves like Ob on functors } \right\} \\ & f \circ \mathrm{Ob}(G) \\ & = \left\{ \mathrm{Ob} \circ \mathrm{Disc} = 1 \right\} \\ & \mathrm{Ob}(\mathrm{Disc}(f)) \circ \mathrm{Ob}(G) \\ & = \text{{ Ob preserves composition }} \\ & \mathrm{Ob}(\mathrm{Disc}(f) \circ G) \\ & = \left\{ \; \alpha \text{ behaves like Ob on functors } \right\} \\ & \alpha_{T,\mathcal{C}}(\mathrm{Disc}(f) \circ G) \\ & = \text{{ definition of the hom functor }} \\ & \alpha_{T,\mathcal{C}}(\mathbf{Cat}(\mathrm{Disc}(f), \mathcal{C})(G)) \\ & = \text{{ composition }} \\ & (\alpha_{T,\mathcal{C}} \circ \mathbf{Cat}(\mathrm{Disc}(f), \mathcal{C}))(G). \end{align} $$

Keith E. Peterson · July 2018

Dan Oneata wrote:

Keith wrote:

I believe Puzzle 162 can be answered the same way using the initial objects and terminal objects of $\mathbf{Cat}$ and $\mathbf{Set}$.

I'm not sure how to use this idea, so my attempt takes the long and tedious route.

What you did above I think is correct.

However, note that for all sets, there's a function from the empty set into any other set, therefore we must have,

\[ \begin{matrix} \mathbf{Cat}[ & Disc(\varnothing) & \rightarrow & \mathcal{C} & ] \\ & & & & \\ & \Uparrow & & \Downarrow & \\ & & & & \\ \mathbf{Set}[ & \varnothing & \rightarrow & Ob(\mathcal{C}) & ] \end{matrix} \]

which must hold for every category. However, the discrete category on an empty set is the empty category, which does have a functor into every other category.

This gives an interesting special case,

\[ \begin{matrix} \mathbf{Cat}[ & Disc(\varnothing) & \rightarrow & Disc(\varnothing) & ] \\ & & & & \\ & \Uparrow & & \Downarrow & \\ & & & & \\ \mathbf{Set}[ & \varnothing & \rightarrow & Ob(Disc(\varnothing)) & ] \end{matrix} \]

Likewise, for any one object, one morphism category there exists a unique functor into from any other category, therefore we must have,

\[ \begin{matrix} \mathbf{Cat}[ & Disc(S) & \rightarrow & \mathbf{1} & ] \\ & & & & \\ & \Uparrow & & \Downarrow & \\ & & & & \\ \mathbf{Set}[ & S & \rightarrow & Ob(\mathbf{1}) & ] \end{matrix} \]

which must hold for every set. However, any object set on a one object category is just a one element set, for which every other set maps uniquely into.

This gives an interesting special case,

\[ \begin{matrix} \mathbf{Cat}[ & Disc(Ob(\mathbf{1})) & \rightarrow & \mathbf{1} & ] \\ & & & & \\ & \Uparrow & & \Downarrow & \\ & & & & \\ \mathbf{Set}[ & Ob(\mathbf{1}) & \rightarrow & Ob(\mathbf{1}) & ] \end{matrix} \]

Michael Hong · July 2018

I don't see how $ \text{Ob}: \mathbf{Cat} \to \mathbf{Set} $ can be a functor if it forgets all the arrows and keeps only the objects. Wouldn't this not be able to preserve composition since it breaks all the objects into separate entities? I think I am missing something here...

Christopher Upshaw · July 2018

Its not a functor on the categories in Cat. Its a functor on Cat, the category with (small enough) categories as objects and natural transformations as morphisims.

So no, its action on the categories in Cat is just a function on objects, not a functor, and so doesn't have to preserve anything.

What it has to preserve is composition of the morphisms of Cat, i.e. (horizontal) composition of natural transformations.

Michael Hong · July 2018

@Christopher

Wait if categories are objects shouldn't functors be morphisms and not natural transformation? Now I am really confused...

Anindya Bhattacharyya · July 2018

The objects of $\textbf{Cat}$ are small categories and the arrows are functors between them.

The objects of $\textbf{Set}$ are sets and the arrows are maps between them.

$\textrm{Ob} : \textbf{Cat} \rightarrow \textbf{Set}$ sends:

— small categories $C$ to their underlying object sets $\textrm{Ob}(C)$

— functors $F : C \rightarrow C'$ to their underlying object maps $\textrm{Ob}(F) : \textrm{Ob}(C) \rightarrow \textrm{Ob}(C')$

$\textrm{Ob}$ is a functor because it sends identity functors to identity maps and composition of functors to composition of maps.

It is basically a "forgetful" functor because it "forgets" the arrows in small categories, and "forgets" the what functors between them do to those arrows. It also forgets the composition of arrows within a small category, but preserves the composition of functors between small categories (ie composition of arrows of $\textbf{Cat}$).

Christopher Upshaw · July 2018

@Michael Yes..yes it would. You make a level error in one direction, I make one in another. facepalm

John Baez · July 2018

Michael wrote:

I have a question about the forgetful functor $\mathbf{Preord} \stackrel{R_2}{\longrightarrow} \mathbf{Poset} $. How would this functor forget 2-cycles? Since we are keeping the objects, it seems to me there can be a choice of which arrow to forget but don't think it can be mapped to the other arrow coming back since source and target won't match. Does the whole cycle just get forgotten i.e. mapped into an identity?

I'm having a bit of trouble understanding this, but as others have hinted:

The difference between a poset and a preorder is that a poset is a preorder where isomorphic objects are equal, i.e., one where

$$ x \le y \text{ and } y \le x \implies x = y $$ So, if you're trying to dream up a functor

$$\mathbf{Preord} \stackrel{R_2}{\longrightarrow} \mathbf{Poset} $$ the natural thing to make it do is force isomorphic objects to be equal.

To do this, you take your preorder, say $X$, and form a new set $R_2(X)$ whose elements are isomorphism classes of elements of $X$, where $x,y\in X$ are isomorphic iff

$$ x \le y \text{ and } y \le x $$ Let $[x]$ stand for the isomorphism class of $x\in X$, so that

$$ x \le y \text{ and } y \le x \iff [x] = [y] $$ Let $R_2(X)$ be the set of these isomorphism classes. Then:

How can we make $R_2(X)$ into a poset using the fact that $X$ was a preorder?
Can we define $R_2$ on morphisms, too? Given a monotone function between preorders, say $f: X \to X'$, we want to define a monotone function $R_2(f) : R_2(X) \to R_2(X')$.
Can we check that $R_2$ is a functor? We want to show that it preserves composition and identities.

John Baez · July 2018

Michael wrote:

I don't see how $ \text{Ob}: \mathbf{Cat} \to \mathbf{Set} $ can be a functor if it forgets all the arrows and keeps only the objects. Wouldn't this not be able to preserve composition since it breaks all the objects into separate entities? I think I am missing something here...

I hope Anindya cleared it up for you in comment #25. It seems you were making a "level slip", mixing up the arrows in each object of $\mathbf{Cat}$ (which the functor $\text{Ob}$ simply throws out) with the arrows in $\mathbf{Cat}$ (which the functor $\text{Ob}$ converts from functors to functions).

It's easy to make level slips in category theory, especially when discussing the category of categories, which is practically an invitation to make level slips. So, don't feel bad - just learn to notice when you're slipping: there's a certain sense of confusion involved, which is a sign to slow down and think carefully.

In the paragraph before the last one I was trying to write clearly. If I were trying to torture you further, I might have said something like this:

It seems you were mixing up the morphisms in each object of the category of categories, which are categories, with the morphisms in the category of categories, which are functors. The functor $\text{Ob} $ from the category of categories to the category of sets maps categories to sets by discarding the morphisms in each category and retaining just their set of objects, and it maps functors to functions by retaining only the functor's action on the set of objects.

Fun!

John Baez · July 2018

Ken wrote:

The problem with my approach on the boolean example seems to be that it's a bit hard to know what to do with -1 + -1.

Since 1+1 = 1 in the booleans, if we're creating a group where -1 is the inverse of 1 then we're forced to have -1 + -1 = -1. But that creates this "problem", which I was trying to inflict on you:

$$ 1 = 1 + 0 = 1 + (1 + -1) = (1 + 1) + -1 = 1 + -1 = 0. $$ In fact this "problem" is not really a problem, it's just a fact of life! Sometimes when you take a monoid and make it into a group by throwing in inverses of the existing elements, you get new equations between elements that weren't previously equal!

In particular, if you turn the boolean monoid into a group you get the trivial group, with 0 as its only element.

It's pretty easy to turn commutative monoids into groups, as follows.

I hand you a commutative monoid $(M,+,0)$. You create a group where the elements are equivalence classes of "formal differences" $ [x - y] $ where $x,y\in M$. "Formal" means that the minus sign is just a symbol. "Equivalence class" means that we decree

$$ [x-y] = [x'-y'] \text{ if and only if } x + y' = x' + y $$ This is nice because if we really could subtract, as we can in a commutative group, we would have $x - y = x' - y'$ if and only if $x + y' = x' + y$.

We can then define addition of these equivalence classes by

$$ [x - y] + [x' - y'] := [(x+x') - (y+y')] $$ and we can define negatives of them by

$$ -[x - y] := [y - x] $$ Puzzle. Show that this construction really gives a group, in fact a commutative group.

Puzzle. Show that if we apply this construction to the boolean monoid we get the trivial group.

Puzzle. Show that if we apply this construction to the natural numbers with its usual $+$ operation, we get the group of integers.

This construction actually gives rise to a left adjoint to the forgetful functor from commutative groups (usually called abelian groups) to commutative monoids.

The noncommutative case requires more work - but luckily Anindya has sketched out how it goes in comment #13. Basically instead of formal differences like $[x-y]$ we need fancier things like $[a_1 a_2^{-1} a_3 a_4^{-1} \dots ]$.

Keith E. Peterson · July 2018

John Baez wrote:

It's easy to make level slips in category theory, especially when discussing the category of categories, which is practically an invitation to make level slips.

To be fair, calling $\mathbf{Cat}$ a category is itself probably a level slip. My understanding from one of your papers you've shared in here is that $\mathbf{Cat}$ is something called a 2-category.

John Baez · July 2018

There is definitely a category version of $\mathbf{Cat}$, where the objects are categories and the morphisms are functors. That's what we are using in this course - that's not a mistake, it's a useful thing.

There's also a 2-category version of $\mathbf{Cat}$, where the objects are categories, the morphisms are functors, and the 2-morphisms are natural transformations. This is ultimately more powerful, because natural transformation are very important - but we're not ready for it yet, because one has to learn categories before one can handle 2-categories.

(Math is like a game where there are always more 'levels': after we master one, we go on to the next.)

Christopher Upshaw · July 2018

If we apply that to the multiplicative monoid on $N^{+}$ we get the (positive) rational numbers, correct?

Keith E. Peterson · July 2018

What do you mean by multiplicative monoid exactly? All monoid technically have a "multiplication".

Also, the rational numbers are given by pairs of integers.

Christopher Upshaw · July 2018

Multiplicative as in it's identity is 1, and it's multiplication is the standard multiplication on the natural numbers.

And yeah usually, though the second part of the pair is a non-zero integer.

Keith E. Peterson · July 2018

Oh, in math texts and papers mathematicians use $\mathbb{N}^\times$ for what you're describing.

Michael Hong · July 2018

Chris, Anindya and John:

Thanks for clearing up the Category vs. Category of Category mix up. You can always count on me falling into every trap/hole possible along the way. LOL.

So I basically now realized the huge difference between $\mathcal{C} \to \mathbf{Set}$ and $\mathbf{Cat} \to \mathbf{Set}$.

This would also mean that the category of $\mathbf{Preord}$ doesn't necessarily have to have at most one morphism like a preorder but all of that information is trapped inside the object? These bold-faced categories are categories of a higher level in that the structure of the category doesn't actually reflect the actual structure of the object? For some odd reason, I was thinking this way which probably caused the level slip...

Christopher Upshaw · July 2018

Honestly i had to read your post 3 times and think about it for over an hour before realizing that it was off.

But yes you have it right now. $\mathbf{Preord}$ is not a preorder. For example there are 6 different monotonic functions from $\mathbf{2}$ to $\mathbf{3}$.

Keith E. Peterson · July 2018

There's an easy way to settle if the category of $X$s is a $X$ itself.

Take $X$ to be sets. The question of whether $\mathbf{Set}$, the category of sets, is itself is a set (a set of all sets) gives Cantor's paradox.

Cheuk Man Hwang · July 2018

Puzzle 162

Piggyback on Dan's answer in comment#20, I think one can make the answer shorter by combining the two cases there into one.

To avoid level slip, let's clarify the objects and morphisms on different levels before we start. To prove that the functors $\mathrm{Disc}$ and $\mathrm{Ob}$ are left and right adjoints to each other, our main focus is

The $\mathrm{Hom}$-functors $$ \begin{align} \mathbf{Cat}(\mathrm{Disc}(-), =) &: \mathbf{Set}^{\mathrm{op}} \times \mathbf{Cat} \to \mathbf{Set} \\\\ \mathbf{Set}(-, \mathrm{Ob}(=)) &: \mathbf{Set}^{\mathrm{op}} \times \mathbf{Cat} \to \mathbf{Set}. \end{align} $$ and
we want to show that there is a natural isomorphism $\alpha$ (i.e. an invertible natural transformation) from $\mathbf{Cat}(\mathrm{Disc}(-), =)$ to $\mathbf{Set}(-, \mathrm{Ob}(=))$ $$ \alpha:\mathbf{Cat}(\mathrm{Disc}(-), =) \Longrightarrow \mathbf{Set}(-, \mathrm{Ob}(=)) $$

This is our top and most abstract level.

To understand $\mathbf{Cat}(\mathrm{Disc}(-), =)$, $\mathbf{Set}(-, \mathrm{Ob}(=))$, and $\alpha$, we need to bring it down to a more concrete level by considering the images of these functors on some particular elements. Hence, let's pick a fixed element $(S, \mathcal{C})$ from the domain $\mathbf{Set}^{\mathrm{op}} \times \mathbf{Cat}$.

The images under the two functors are, obviously, $\mathbf{Cat}(\mathrm{Disc}(S), \mathcal{C})$ and $\mathbf{Set}(S, \mathrm{Ob}(\mathcal{C}))$. Moreover, $\alpha$ will "generate" a morphism between these two objects

\begin{matrix} \mathbf{Cat}(\mathrm{Disc}(S), \mathcal{C}) \\ \\ \alpha_{S,\mathcal{C}} \downarrow \\ \\ \mathbf{Set}(S, \mathrm{Ob}(\mathcal{C}))& \end{matrix} I think of it as "one level down".

In order to prove the naturality of $\alpha$, we need to consider the naturality square $$ \begin{matrix} \mathbf{Cat}(\mathrm{Disc}(S), \mathcal{C}) & \rightarrow & \mathbf{Cat}(\mathrm{Disc}(T), \mathcal{D}) \\\\ \alpha_{S,\mathcal{C}} \downarrow & & \alpha_{T,\mathcal{D}} \downarrow \\\\ \mathbf{Set}(S, \mathrm{Ob}(\mathcal{C})) & \rightarrow & \mathbf{Set}(T, \mathrm{Ob}(\mathcal{D})) \end{matrix} $$ where $(T, \mathcal{D})$ is just another fixed element in $\mathbf{Set}^{\mathrm{op}} \times \mathbf{Cat}$ and the "right edge" of the naturality square is just another manifestation of $\alpha$ at the element $(T, \mathcal{D})$. However, we still have to understand the "horizontal edges" of the naturality square. To this end, we first have to choose any fixed morphism

$(\mathbf{f}, \mathbf{F}):(S, \mathcal{C})\to (T, \mathcal{D})$.

I consider this "two levels down" because this is a morphism belongs to the domain of $\mathbf{Cat}(\mathrm{Disc}(-), =)$ and $\mathbf{Set}(-, \mathrm{Ob}(=))$.

Then we have to bring $(\mathbf{f}, \mathbf{F})$ "one level up" by considering its images under $\mathbf{Cat}(\mathrm{Disc}(-), =)$ and $\mathbf{Set}(-, \mathrm{Ob}(=))$. Namely, $\mathbf{Cat}(\mathrm{Disc}(\mathbf{f}), \mathbf{F})$ and $\mathbf{Set}(\mathbf{f}, \mathrm{Ob}(\mathbf{F}))$. It is these two morphisms that contribute to the "horizontal edges" of the naturality square $$ \begin{matrix} \mathbf{Cat}(\mathrm{Disc}(S), \mathcal{C}) & \overset{\mathbf{Cat}(\mathrm{Disc}(\mathbf{f}), \mathbf{F})}\longrightarrow & \mathbf{Cat}(\mathrm{Disc}(T), \mathcal{D}) \\\\ \alpha_{S,\mathcal{C}} \downarrow & & \alpha_{T,\mathcal{D}} \downarrow \\\\ \mathbf{Set}(S, \mathrm{Ob}(\mathcal{C})) & \underset{\mathbf{Set}(\mathbf{f}, \mathrm{Ob}(\mathbf{F}))}\longrightarrow & \mathbf{Set}(T, \mathrm{Ob}(\mathcal{D})) \end{matrix} $$ Now we are ready to prove the naturality of $\alpha$. Namely, we have to show that

$$ \mathbf{Set}(\mathbf{f}, \mathrm{Ob}(\mathbf{F}))\circ\alpha_{S,\mathcal{C}}(\mathbf{G})=\alpha_{T,\mathcal{D}}\circ\mathbf{Cat}(\mathrm{Disc}(\mathbf{f}), \mathbf{F})(\mathbf{G})\quad\quad \forall \mathbf{G}\in \mathbf{Cat}(\mathrm{Disc}(S), \mathcal{C}) $$ Below is just the same as the proof provided by Dan but combining the 2 cases there into a single case.

Starting from the left side, we have

$$ \mathbf{Set}(\mathbf{f}, \mathrm{Ob}(\mathbf{F}))\circ\alpha_{S,\mathcal{C}}(\mathbf{G})=\mathrm{Ob}(\mathbf{F})\circ\alpha_{S,\mathcal{C}}(\mathbf{G})\circ\mathbf{f} $$ according to the definition of the Hom-functor in Lecture 52.

Moreover, what $\alpha_{S,\mathcal{C}}$ does is sending functors in $\mathbf{Cat}(\mathrm{Disc}(S), \mathcal{C})$ to the set function on objects, that is, $\alpha_{S,\mathcal{C}}$ acts the same as the functor $\mathrm{Ob}$ on $\mathbf{Cat}(\mathrm{Disc}(S), \mathcal{C})$. Hence, we further have $$ \mathrm{Ob}(\mathbf{F})\circ\alpha_{S,\mathcal{C}}(\mathbf{G})\circ\mathbf{f}=\mathrm{Ob}(\mathbf{F})\circ\mathrm{Ob}(\mathbf{G})\circ\mathbf{f} $$ Next, Dan recognized that the composition $\mathrm{Ob}\circ\mathrm{Disc}$ is the same as the identity function on the set $\mathbf{Set}^\text{op}(S,T)$, so $$ \mathrm{Ob}(\mathbf{F})\circ\mathrm{Ob}(\mathbf{G})\circ\mathbf{f}=\mathrm{Ob}(\mathbf{F})\circ\mathrm{Ob}(\mathbf{G})\circ\mathrm{Ob}(\mathrm{Disc}(\mathbf{f})) $$ Since $\mathrm{Ob}$ is a functor, it preserves compositions. We can further imply \begin{matrix} \mathrm{Ob}(\mathbf{F})\circ\mathrm{Ob}(\mathbf{G})\circ\mathrm{Ob}(\mathrm{Disc}(\mathbf{f}))&=&\mathrm{Ob}(\mathbf{F}\circ\mathbf{G}\circ\mathrm{Disc}(\mathbf{f}))\\ &:=&\mathrm{Ob}\circ\mathbf{Cat}(\mathrm{Disc}(\mathbf{f}), \mathbf{F})(\mathbf{G})\\ &:=&\alpha_{T,\mathcal{D}}\circ\mathbf{Cat}(\mathrm{Disc}(\mathbf{f}), \mathbf{F})(\mathbf{G}), \end{matrix}

which we invoked, again, the definitions of $\alpha_{T,\mathcal{D}}$ and $\mathbf{Cat}(\mathrm{Disc}(\mathbf{f}), \mathbf{F})$.

This shows that $\mathbf{Set}(\mathbf{f}, \mathrm{Ob}(\mathbf{F}))\circ\alpha_{S,\mathcal{C}}(\mathbf{G})=\alpha_{T,\mathcal{D}}\circ\mathbf{Cat}(\mathrm{Disc}(\mathbf{f}), \mathbf{F})(\mathbf{G})$ for all $\mathbf{G}\in \mathbf{Cat}(\mathrm{Disc}(S), \mathcal{C})$.

Keith E. Peterson · July 2018

This actually raises another issue with $\mathrm{Ob}$.

Namely, since $\mathbf{Set}$ is itself a category, we uncomfortably get this case,

\[ \mathbf{Cat}(\mathrm{Disc}(S),\mathbf{Set}) \cong \mathbf{Set}(S,\mathrm{Ob}(\mathbf{Set})). \]

Anindya Bhattacharyya · July 2018

@Keith important to note that Cat is the category of all small categories, ie ones with a an underlying set of objects, but as you note, Cantor's theorem tells us that Set is not small!

Anindya Bhattacharyya · July 2018

Puzzle 163. Show there are functors
$$ \mathbf{Cat} \stackrel{R_1}{\longrightarrow} \mathbf{Preord} \stackrel{R_2}{\longrightarrow} \mathbf{Poset} \stackrel{R_3}{\longrightarrow} \mathbf{Set} $$ with left adjoints going back: $$ \mathbf{Set} \stackrel{L_3}{\longrightarrow} \mathbf{Poset} \stackrel{L_2}{\longrightarrow} \mathbf{Preord} \stackrel{L_1}{\longrightarrow} \mathbf{Cat} . $$ Hint: the composite $ R_3 R_2 R_1 : \mathbf{Cat} \to \mathbf{Set} $ is our friend $$ \text{Ob}: \mathbf{Cat} \to \mathbf{Set} ,$$ and the composite $L_1 L_2 L_3 : \mathbf{Set} \to \mathbf{Cat} $ is our friend $$ \mathrm{Disc} : \mathbf{Set} \to \mathbf{Cat} .$$

Has anyone got anywhere on Puzzle 163? I'm thoroughly stuck.

The inclusion functors Poset → Preord and Preord → Cat have left adjoints: we can send a preorder to its skeleton, and a category to its "thin-ification", but I don't think they have right adjoints, and I can't think of any other sensible functors between these categories.

The only bit I can get is to work is the discrete functor Set → Poset, which has a right adjoint: send a poset to its underlying set.

Also the underlying functor Preord → Set has a left and a right adjoint (the discrete and codiscrete preorders on a set). But this doesn't seem to factor through Poset since the codiscrete preorder on a set is typically not a poset.

Michael Hong · July 2018

This is probably wrong or I'm talking funny but I'll try Puzzle 163 the best I can in hopes of someone giving a solution.

So using John's tip in comment 27 I will define the functors first.

So say we have a category $\mathcal{C}, \mathcal{D} \in Ob(\mathbf{Cat})$ and a functor $F : \mathcal{C} \rightarrow \mathcal{D}$. Also $x,y \in Ob(\mathcal{C})$. We also need $S,T \in \mathbf{Set}$ and a function $f : S \rightarrow T$.

$\mathbf{Cat} \stackrel{R_1}{\longrightarrow} \mathbf{Preorder}$

Let $[\leq]$ be the isomorphism class on the morphisms in $homset(x,y)$ so that $$homset(x,y) \iff x \; [\leq] \; y$$ Define $R_1(C)$ to be the preorder formed by applying Reflexivity and Transivity using $[\leq]$.

Define $R_1(F)$ to be the monotone function such that $x \; [\leq] \; y \iff m_1(x) \; [\leq] \; m_1(y)$ where $m_1$ is a monotone function in $\mathbf{Preorder}$.

$\mathbf{Preorder} \stackrel{R_2}{\longrightarrow} \mathbf{Poset}$

Let $[x]$ be the isomorphism class on the morphisms in $x \in Ob(C)$ so that $$x \; [\leq] \; y \; and \; y \; [\leq] \; x \iff [x] \; = \; [y]$$ Define $R_2R_1(C)$ to be the preorder formed by applying Reflexivity and Transivity using $[\leq]$ and $[x]$.

Define $R_2R_1(F)$ to be the monotone function such that $[x] \; [\leq] \; [y] \iff m_2([x]) \; [\leq] \; m_2([y])$ where $m_2$ is a monotone function in $\mathbf{Poset}$.

$\mathbf{Poset} \stackrel{R_3}{\longrightarrow} \mathbf{Set}$

Define $R_3R_2R_1(C)$ to be the set $Ob(\mathcal{C})$ such that $[x] \; [\leq] \; [y] \iff [x],[y] \in Ob(\mathcal{C})$.

Define $R_3R_2R_1(F)$ to be the function $m_3$ such that $[x] \rightarrow m_2([x])$ for all $[x] \in Ob(\mathcal{C})$

Then we can daisy chain the naturality square Cheuk Man used and proved the naturality for in comment 39 to define the left adjoints.

$$ \begin{matrix} \mathbf{Cat}(L_1L_2L_3(S), \mathcal{C}) & \overset{\mathbf{Cat}(L_1L_2L_3(\mathbf{f}), \mathbf{F})}\longrightarrow & \mathbf{Cat}(L_1L_2L_3(T), \mathcal{D}) \\ \alpha_{L_2L_3(S),\mathcal{C}} \downarrow & & \alpha_{L_2L_3(T),\mathcal{D}} \downarrow \\ \mathbf{Pre}(L_2L_3(S), R_1(\mathcal{C})) & \underset{\mathbf{Pre}(L_2L_3(\mathbf{f}), R_1(\mathbf{F}))}\longrightarrow & \mathbf{Pre}(L_2L_3T, R_1(\mathcal{D}))\\ \alpha_{L_3(S),R_1(\mathcal{C})} \downarrow & & \alpha_{L_3(T),R_1(\mathcal{D})} \downarrow \\ \mathbf{Pos}(L_3(S), R_2R_1(\mathcal{C})) & \underset{\mathbf{Pos}(L_3(\mathbf{f}), R_2R_1(\mathbf{F}))}\longrightarrow & \mathbf{Pos}(L_3(T), R_2R_1(\mathcal{D}))\\ \alpha_{S,R_2R_1(\mathcal{C})} \downarrow & & \alpha_{T,R_2R_1(\mathcal{D})} \downarrow \\ \mathbf{Set}(S, R_3R_2R_1(\mathcal{C})) & \underset{\mathbf{Set}(\mathbf{f}, R_3R_2R_1(\mathbf{F}))}\longrightarrow & \mathbf{Set}(T, R_3R_2R_1(\mathcal{D}))\\ \end{matrix} $$

Michael Hong · July 2018

@Anindya

I was hoping surely you would have a solution to Puzzle 163 & 164! Reading through your comment made me realize I have no clue whats going on. LOL

Doesn't the puzzle ask to look for left and right adjoints to $R_1, R_2,R_3$?

This naturality isomorphism for adjoint functors is really confusing. I have no sense of intuition for this yet. Do you have a worked out example of how to use the naturality square to determine whether a functor is a left or right adjoint? Sorry to bother you while you are working on the problem but if you get a chance maybe?

Anindya Bhattacharyya · July 2018

@Michael

The puzzle asks us to cook up suitable functors $R_1, R_2, R_3$ and find left adjoints for them, and possibly right adjoints. Currently I can't even cook up the first two functors!

Re the natural isomorphism $\mathcal{D}[LX, Y] \cong \mathcal{C}[X, RY]$, I've found that you don't usually need to worry too much about naturality. The key thing is to look for a bijection between $\mathcal{D}$-arrows $LX \rightarrow Y$ and $\mathcal{C}$-arrows $X \rightarrow RY$. Usually something will "jump out" at you, and it will usually turn out to be natural.

What the naturality condition actually says is that if we write $\Phi$ for our bijection, we ought to have

\[\Phi(Lf \circ x \circ g) = f \circ \Phi(x) \circ Rg\]

for any arrows $f$ into $X$ and $g$ out of $Y$. But this tends to fall out automatically for any sensible choice of $\Phi$.

Christopher Upshaw · July 2018

Maybe try just leaving out Poset?

Anindya Bhattacharyya · July 2018

That helps but you're still stuck with the "obvious" adjunction Cat $\rightleftharpoons$ Preorder being the "wrong way round".

Cheuk Man Hwang · July 2018

@Keith comment38, the collection of objects $\mathrm{Ob}(\mathbf{Set})$ in the category $\mathbf{Set}$ is not a set, it is a class. This means $\mathbf{Set}$ is a large category, echoing Anindya's comment#41. This is a way to resolve Cantor's/Russell's Paradox. I think John intentionally left it out so that we won't get distracted by the technicality.

Keith E. Peterson · July 2018

As John wrote it, I see nothing wrong,

There's a functor
$$ \text{Ob}: \mathbf{Cat} \to \mathbf{Set} $$ that forgets everything about a category except its objects. In other words, it sends any category $\mathcal{C}$ to its set of objects $\mathrm{Ob}(\mathcal{C})$, and sends any functor $F: \mathcal{C} \to \mathcal{D}$ to the function it defines on objects, which I've been calling just $F : \mathrm{Ob}(\mathcal{C}) \to \mathrm{Ob}(\mathcal{D})$. A more systematic name for it is $\mathrm{Ob}: \mathrm{Ob}(\mathcal{C}) \to \mathrm{Ob}(\mathcal{D})$.

In fact, John insists very strongly that $\mathbf{Cat}$ is a category in its own right. We therefore get an even more uncomfortable case,

\[ \mathbf{Cat}(\mathrm{Disc}(S),\mathbf{Cat}) \cong \mathbf{Set}(S,\mathrm{Ob}(\mathbf{Cat})). \]

Anindya Bhattacharyya · July 2018

The key phrase is "it sends any category C to its set of objects". But the objects of Cat do not form a set. Neither do the objects of Set.

Azimuth Forum

Howdy, Stranger!

Categories

Lecture 53 - Chapter 3: Free and Forgetful Functors

Comments