Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Adjunctions

Julius Hamilton (Jun 16 2024 at 03:25):

I know this is a central topic in category theory, and it recently came up in another thread. I’d like to analyze the definition here.

https://en.m.wikipedia.org/wiki/Adjoint_functors

Adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories.

Pairs of adjoint functors…often arise from constructions of "optimal solutions" to certain problems (i.e., constructions of objects having a certain universal property).

An adjunction between categories $\mathcal C$ and $\mathcal D$ is a pair of functors $F: \mathcal{D} \to \mathcal{C}$ and $G : \mathcal{C} \to \mathcal{D}$ and for all objects $X$ in $\mathcal{C}$ and $Y$ in $\mathcal D$, there is a bijection $hom_{\mathcal{C}}(FY, X) \cong hom_{\mathcal{D}}(Y, GX)$…

This says that for an object in $C$ and an object in $D$, the hom-set of $GX$ and $Y$ is in bijection with the hom-set of $X$ and $FY$. I am wondering how significant it is that this is a bijection. I feel like in category theory, things tend to be abstract enough that we think of isomorphic objects as basically the same, since their structural properties are identical. I’ll definitely need to work through an example now to see what this property is really saying. I’ll try to think of something relating to the category of sets, first.

…such that this family of bijections is natural in $X$ and $Y$.

Julius Hamilton (Jun 16 2024 at 03:28):

I’d like to challenge myself to think of two functors which have this bijection-between-Hom-sets property, but I might need to sleep on it.

Julius Hamilton (Jun 16 2024 at 03:30):

Let’s say that I just want to stick to the category of sets, so I’ll be thinking about endofunctors on it.

Julius Hamilton (Jun 16 2024 at 03:34):

To gain better context, I want to take a short detour to think about what interesting species of endofunctors there are, in $\mathbf{Set}$.

David Egolf (Jun 16 2024 at 04:42):

There's a big list of examples in that Wikipedia article you linked to! To better understand the definition, you may find it helpful to pick a specific example from that list and then review the definition in that context.

David Egolf (Jun 16 2024 at 04:59):

Julius Hamilton said:

To gain better context, I want to take a short detour to think about what interesting species of endofunctors there are, in $\mathbf{Set}$.

In this direction, doing a search for "exponential object" on that Wikipedia page might be useful. Note that the category of sets $\mathsf{Set}$ is a "Cartesian closed category".

David Egolf (Jun 16 2024 at 05:05):

On a related note, you might enjoy contemplating this:
$\mathsf{Set}(X \times Y, Z) \cong \mathsf{Set}(X, Z^Y)$.

This says that there is a bijection between:

• the set of functions from $X \times Y$ to $Z$, and...
• ...the set of functions from $X$ to $Z^Y$, where $Z^Y$ is the set of functions from $Y$ to $Z$.

This Wikipedia article describes a famous bijection of this kind.

Todd Trimble (Jun 16 2024 at 11:42):

constructions of objects having a certain universal property

Keep this in mind as a potential source as you search for examples.

Some people say that adjunction is the single most important concept in category theory. It's deep, all right. But I think one could equally well argue that the concept of universal property is the single most important concept in category theory. And the two concepts are closely intertwined.

I am wondering how significant it is that this is a bijection.

Another thing you may wonder about, in time, is the fact that not only do you have a bijection of hom-sets, but that the bijection has to be natural (that's part of the hom-set definition of adjunction).

John Baez (Jun 16 2024 at 11:49):

I sometimes like telling the tale of how @Jade Master and I were trying to construct an adjunction: we found a bijection of homsets $\mathrm{hom}(L x , y) \cong \mathrm{hom}(x, R y)$, it was "natural" in the intuitive sense of not requiring ad hoc choices to define... but when Jade tried to prove it was natural in the technical sense, it wasn't!

This came as a big lesson to me.

Todd Trimble (Jun 16 2024 at 12:15):

John Baez said:

I sometimes like telling the tale of how Jade Master and I were trying to construct an adjunction: we found a bijection of homsets $\mathrm{hom}(L x , y) \cong \mathrm{hom}(x, R y)$, it was "natural" in the intuitive sense of not requiring ad hoc choices to define... but when Jade tried to prove it was natural in the technical sense, it wasn't!

This came as a big lesson to me.

That's very interesting. And I don't remember hearing tell of said tale.

Eric M Downes (Jun 16 2024 at 12:16):

John Baez said:

I sometimes like telling the tale of how Jade Master and I were trying to construct an adjunction: we found a bijection of homsets $\mathrm{hom}(L x , y) \cong \mathrm{hom}(x, R y)$, it was "natural" in the intuitive sense of not requiring ad hoc choices to define... but when Jade tried to prove it was natural in the technical sense, it wasn't!

This came as a big lesson to me.

If you or Jade are ever feeling up for story-time, I would love to hear this tale!

We could certainly schedule a special seminar on it.

Figuring out how to balance intuition and paranoia is hard, even when I (think I) have a handle on my own hubris, and in comparison I'm just playing around in the shallows. This is the kind of thing I don't think one can learn from a textbook. I expect these more personal oral/written lessons are critical for practice in an art.

John Baez (Jun 16 2024 at 12:42):

I don't have the energy to tell the tale in detail right now, but the left adjoint functor goes from Petri nets to commutative monoidal categories - see Definition 8 and Lemma 9 here.

We conjectured a right adjoint for this functor, and showed that gave an intuitively 'natural' bijection of homsets, but when @Jade Master tried to prove naturality she couldn't. Eventually @Mike Shulman showed that our candidate right adjoint was actually the wrong adjoint - and he showed us the true right adjoint! Jade wrote about this in greater generality in a companion paper.

A commutative monoidal category, in case anyone is curious, is a commutative monoid object in the category $\mathsf{Cat}$. In other words, it's a symmetric monoidal category where the associator, left and right unitors, and braiding are all identities. By chance I mentioned them yesterday on this very Zulip.

Julius Hamilton (Jun 16 2024 at 12:48):

Thanks John, Todd, David and Eric.

I want to explore thoughts about endofunctors and also functors in general before I get back to adjoint functors.

I might throw out some big but hazy questions just to get my thoughts moving freely.

I think I’ve always been attracted to finding really compact or elegant ways to define or express something logically.

So, we can define a functor in terms of about 3-4 “pieces of information” (depending on how you count them) - a functor is:

• a map on objects
• and a map on arrows
  - such that identities are mapped to identities
  - and basically, to me, the only really essential aspect: such that it commutes with the composition operation.

But wouldn’t it be nice if we could package those separate pieces of information together into one single notion? Then defining things wouldn’t be like listing out a number of separate clauses. For example, we could say, “a functor is a morphism in the category of categories”; but then we’d still need to do some thinking to reconstruct the specifics. I also don’t think this definition would be adequate, since there could be multiple choices for what to use as morphisms if $Ob$ is the set of all small categories.

I’m imagining some time in the future I’ll think of a different way to define functors where the separate clauses in the definition are integrated into what feels more like “a single notion”.

Here is just one of various different directions you could go in. What if instead of thinking of abstract categories as “denoting” other mathematical objects (like sets), we can functionally transform the structure of an abstract category into the structure of whatever it’s supposed to represent?

So if the objects of a category “represented” sets, there could be a “pluralization” mapping where each “single point” (an object) is “expanded” into a “collection of points” (a set) by a computational process. That process could then be logically extrapolated to the arrows in some way. That way, we actually construct a concrete category procedurally out of an abstract one, instead of just doing guess-work about “I wonder what the arrows should be”.

I don’t know if this is common when learning category theory, but I have frequently had this feeling that first you build an intuition for and learn how to interpret diagrams mainly in terms of set theory - at least in terms of lots of concrete categories like $\mathbf{Grp}$, $\mathbf{Top}$, etc. But then you reach a limit where this way of understanding categories actually bogs you down; then you have to actually reverse your intuition and think about purely categorical properties of diagrams, and categories as abstract categories. For example, for the most part, up until now, I tend to think of arrow composition as function composition. But a question I am revolving around currently is how the properties of the specific things we choose to form a category out of, correspond to the actual abstract properties we need those things to have, in a category. Functions have lots of little nuances characterizing “what they are like”, what we can do with them. But for something to qualify as a “morphism” in a category, it only needs very few properties - (associative composition and “the existence of identities” (which I think can be called “unitality”)).

Actually, even this is not true. Seeing as defining a category begins with the declaration of “two sets” (you could call them $Ob$ and $Arr$, but I’ve also seen them written $\mathcal{C}_0$ and $\mathcal{C}_1$), conceptually, we can choose the “in-between” case, between concrete and abstract, where the objects and arrows are given an interpretation as “some thing” (be they mathematical objects or real-world phenomena), but they conceptually have nothing to do with each other. Instead of trying to find something to “serve as arrows” which captures the sense of “a relationship” between the things, or “a transformation”, it could be any arbitrary second collection of things - like, $C_0$ is a collection of dice, and $C_1$ is a collection of fruits.

This brings me to the idea that the composition operation in a category, and perhaps even the equality symbol, can be viewed as equally “meaningless”. We do not need to think of $\circ$ as “some sort of process followed by another is equivalent to some third process”. It can be any arbitrary relation, like “a berry $\circ$ a dog $=$ a computer, because I said so.” This isn’t the best example of what I mean, but it’s a step in that direction.

As you can see, there are lots of little contextual thoughts I want to go over a bit, as I warm up to viewing adjoint functors better.

Jean-Baptiste Vienney (Jun 16 2024 at 16:20):

If you want to package the preservation of identities and composition together, you can write the definition of a functor $F$ from $\mathcal{C}$ to $\mathcal{D}$ like this:

• A function from $Ob_{\mathcal{C}}$ to $Ob_{\mathcal{D}}$
• For every $A,B \in Ob_{\mathcal{C}}$, a function from $\mathcal{C}[A,B]$ to $\mathcal{D}[F(A),F(B)]$

such that:

• $F$ preserves the multicomposition of morphisms i.e. $F(f_1 \circ … \circ f_n) = F(f_1) \circ … \circ F(f_n)$

where the $0$-ary composition is understood as an identity.

Jean-Baptiste Vienney (Jun 16 2024 at 16:27):

You would have to define precisely the multicomposition first, in particular the $0$-ary case for this to be completely rigorous.

Jean-Baptiste Vienney (Jun 16 2024 at 16:28):

It’s not extremely satisfying but that’s all I’m thinking to.

Jean-Baptiste Vienney (Jun 16 2024 at 16:37):

But what I like is that it makes me feel like maybe we could define a functor as an algebra over some monad. The multicomposition looks like a list of morphisms and it makes me think to how a monoid can be encoded as an algebra over the list monad on $\mathbf{Set}$.

Jean-Baptiste Vienney (Jun 16 2024 at 16:53):

Hmm, now I think that what makes sense is maybe to define a category as an algebra over some monad.

Jean-Baptiste Vienney (Jun 16 2024 at 17:07):

Small categories are polynomial comonads on $\mathbf{Set}$, so they are probably comonoids in some monoidal categories and so coalgebras over some comonad. I don’t know if it has anything to do with this simple idea of functors and multicomposition but I’ve just remembered that (with the help of Google).

Julius Hamilton (Jun 16 2024 at 17:51):

Thanks, that sounds really interesting.

Julius Hamilton (Jun 16 2024 at 18:07):

I’m going to respond to the above in just a moment. I wanted to outline another thought I had.

Imagine some sort of “context” where we only have to specify a single property of something, and it would follow necessarily that the described object or structure has its own corresponding version of an “identity structure”. That way, we don’t need to state “the presence of identities”, when defining anything.

For example, for a category, the “identity structure” is the fact that every object is associated with an “identity arrow”.

For a functor, the “identity structure” part of its definition is that it maps $id_X$ to $id_{FX}$.

And so on.

I think but am not sure, one of the cool things about “internal category theory” is that we can write expressions that look more or less exactly like set-theoretic descriptions of anything in mathematics (such as the axioms of a monoid), but we can interpret that notation as a categorical structure (I learned this from Mike Shulman’s intro to categorical logic text). When we do that, I think it opens up very alternative definitions of the same things, for example because you can identify universal properties of those structures.

So that’s what I hopefully mean or envision regarding a “context” in which we could “implant” a definition of this structure or that structure, yet the context would make the existence of an “identity component” follow.

Mike Stay (Jun 16 2024 at 21:17):

Julius Hamilton said:

To gain better context, I want to take a short detour to think about what interesting species of endofunctors there are, in $\mathbf{Set}$.

All monads are endofunctors, every adjunction induces a monad, and for any monad there's a category of adjunctions that induce it.

Julius Hamilton (Jun 16 2024 at 21:25):

Cool.

Maybe it’s also time for me to start working through / drawing my first examples of specific monads. And monoid objects.

Jean-Baptiste Vienney (Jun 16 2024 at 22:01):

Maybe you could think about this:

For every set $X$, define $\mathcal{L}(X)$ as the set of all the lists with elements in $X$. An element $l \in \mathcal{L}(X)$ is thus a tuple of the form $(x_1,...,x_n)$ for some $n \ge 0$ and $x_1,...,x_n \in X$. If $n=0$, you can simply write the empty list which is the only list of size $0$ as $()$. It happens that the functor $\mathcal{L}:\mathbf{Set} \rightarrow \mathbf{Set}$ can be made into a monad on $\mathbf{Set}$.

How can we define $\mathcal{L}$ on morphisms?

What could be the unit of the monad $u_X:X \rightarrow \mathcal{L}(X)$?

What is the multiplication of the monad $m_X:\mathcal{L}(\mathcal{L}(X)) \rightarrow \mathcal{L}(X)$?

Jean-Baptiste Vienney (Jun 16 2024 at 22:03):

$\mathbf{Set}$ is a monoidal category with monoidal product the cartesian product $\times$ and monoidal unit the terminal object $\{*\}$ (a singleton set).

Jean-Baptiste Vienney (Jun 16 2024 at 22:03):

For a given set $X$, can you make $\mathcal{L}(X)$ into a monoid in the monoidal category $(\mathbf{Set},\times,\{*\})$?

Eric M Downes (Jun 16 2024 at 23:20):

One technicality, in case you were unaware @Jean-Baptiste Vienney the monad distributive law fails to exist for $\mathcal{L\circ L}$ (lists of lists) though you can still form a monad isomorphic to it using the Maybe monad and the non-empty lists semad (semigroup in the category of endofunctors); see Example 4.18 and Remark 4.19 in Zwart & Marsden's paper. Probably this will matter if/when you get to natural transformations, I suspect.

Jean-Baptiste Vienney (Jun 16 2024 at 23:37):

I wasn't aware of this but it doesn't change the fact that $\mathcal{L}$ is a monad and so that $u_X$ and $m_X$ are natural transformations.

Eric M Downes (Jun 16 2024 at 23:42):

I think it is a very cool approach.