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: representable free functors?

David Egolf (Sep 28 2023 at 01:35):

I have seen several examples of forgetful functors that are representable. For example, consider the forgetful functor $U:\mathsf{Group} \to \mathsf{Set}$ that sends each group to its underlying set, and each group homomorphism to its underlying function. As noted in Riehl's "Category Theory in Context", this functor is represented by the group $\Z$ of integers under addition; so $U \cong \mathsf{Group}(\Z,-)$. There are also several other examples of representable forgetful functors in the same book.

However, I don't currently know of any examples of "free functors" that are representable. Intuitively, a free functor is one that "freely adds in" structure, often mapping from $\mathsf{Set}$ to a category of sets with additional structure.

I tried to describe what I meant by a free functor more concretely in an earlier version of this post. However, I have since realized that I don't yet have a precise idea of what a "free functor" is! Hopefully the rough intent of this question is somewhat clear, despite this: Are there any representable free functors? (And if so, what are some examples?)

Kevin Arlin (Sep 28 2023 at 03:30):

Well, are there any functors that feel “free” to you that land in Set? Tough to be representable with that! (Although there may be more to say in that direction…)

Todd Trimble (Sep 28 2023 at 03:47):

There is the identity functor on sets...

A "free functor" is left adjoint to a "forgetful functor", but what does "forgetful" mean exactly? What is being forgotten? There is a point of view where pretty much any functor can be regarded as forgetting something (even if that something is "nothing", as in the identity functor). See stuff, structure, property for some in-depth thinking on this topic.

David Egolf (Sep 28 2023 at 05:02):

Kevin Arlin said:

Well, are there any functors that feel “free” to you that land in Set? Tough to be representable with that! (Although there may be more to say in that direction…)

Ah, that's a good point. I had forgotten that representable functors always map to $\mathsf{Set}$...
However, I'd be willing to consider working in a $V$-enriched category, so that representable functors wouldn't need to map to $\mathsf{Set}$, but would instead map to $V$.

The intuition I have in mind is that possibly the morphisms between objects in some case could be more "structured" than the objects themselves (e.g. maybe in some category the morphisms from $A$ to $B$ assemble into a vector space, but $A$ and $B$ are simpler objects than vector spaces).

@Todd Trimble also makes a good point - what is "free" depends strongly on what we consider to be "forgetful". Thanks for linking to that nlab article talking about how functors can forget different amounts/kinds of things! Hopefully someday relatively soon I'll work on understanding the concept of "stuff, structure, and properties" - but there are so many interesting things to learn, and so this may take me a while.

Morgan Rogers (he/him) (Sep 28 2023 at 06:56):

@David Egolf it's worth noting that (covariant) representable functors preserve all limits - can you see why? That means that as soon as the hypotheses of one of the Adjoint Functor Theorems are satisfied by your categories that they will be right adjoints. As such, unless a free functor has a further left adjoint, it is unlikely to be representable.

John Baez (Sep 28 2023 at 07:38):

David Egolf said:

I have seen several examples of forgetful functors that are representable. For example, consider the forgetful functor $U:\mathsf{Group} \to \mathsf{Set}$ that sends each group to its underlying set, and each group homomorphism to its underlying function. As noted in Riehl's "Category Theory in Context", this functor is represented by the group $\Z$ of integers under addition; so $U \cong \mathsf{Group}(\Z,-)$.

A lot of forgetful functors are right adjoints, like the one you mentioned. Did you notice that every right adjoint $U: \mathsf{C} \to \mathsf{Set}$ is representable?

In the example you mentioned it's representable by $F(1)$, where $F: \mathsf{Set} \to \mathsf{C}$ is the left adjoint of $U$. Did you notice that every right adjoint $U: \mathsf{C} \to \mathsf{Set}$ is representable by $F(1)$?

If don't already know this, you might enjoy showing it. The proof is just a two line computation using the definitions of "representable", "left adjoint", "right adjoint", and the special feature of the set $1$: for any set $X$,

$\mathsf{Set}(1,X) \cong X$

John Baez (Sep 28 2023 at 07:40):

I learned this very late in life, from @Todd Trimble. It explains a lot of things.

Matteo Capucci (he/him) (Sep 28 2023 at 08:48):

Ha, what a nice little fact!

John Baez (Sep 28 2023 at 10:42):

We used the 2-categorical analogue of this in our paper on 2-rigs to show that the forgetful functor from 2-rigs to categories is represented by the free 2-rig on one object. It doesn't matter what a 2-rig is: all that matters is that you have a right adjoint 2-functor from the 2-category of them to $\mathsf{Cat}$.

Mike Shulman (Sep 28 2023 at 16:08):

There's also a version of this for categories enriched over any closed symmetric monoidal category $V$, since in any such category $[I,X] \cong X$ where $I$ is the unit object and $[-,-]$ is the internal-hom, which is the enriched hom in the canonical self-enrichment of $V$.

David Egolf (Sep 28 2023 at 21:04):

Thanks again for all your excellent answers! It will take me some time to properly read them and respond, but I hope to do so. (I have some catching up to do in some other threads too, so I should probably try and restrain myself from asking even more questions for now!)

David Egolf (Sep 29 2023 at 00:57):

Morgan Rogers (he/him) said:

David Egolf it's worth noting that (covariant) representable functors preserve all limits - can you see why?

This is actually something I've been wanting to understand for a while now! I'm currently working on doing some exercises relating to preservation of limits (currently in Riehl), to try and expand my toolbox relating to this.
So I suppose the answer to "can you see why?" is: "not yet, but I hope to relatively soon!"

Todd Trimble (Sep 29 2023 at 02:04):

As for the "can you see why?", I might suggest closing the books and thinking through, from first principles, why representable functors preserve binary products, and similarly preserve terminal objects. The case for general limits is an extrapolation that is not too extravagant.

John Baez (Sep 29 2023 at 09:16):

Yes, you don't really need tools to prove that representable functors preserve limits: it sort of falls out from the definitions. Even I can do it, and I never remember any of those tools. Todd is right: start with binary products and just write down what it means that representable functors preserve those.

David Egolf (Sep 29 2023 at 17:06):

Todd Trimble said:

As for the "can you see why?", I might suggest closing the books and thinking through, from first principles, why representable functors preserve binary products, and similarly preserve terminal objects. The case for general limits is an extrapolation that is not too extravagant.

Thanks for the suggestion! It's helpful to have something specific to try.

Let us assume we have a functor $C(a,-): C \to \mathsf{Set}$ that sends a morphism $f: x \to y$ to the morphism $f_*: C(a,x) \to C(a,y)$, where $f_*(g) = f \circ g$.
To show that $C(a,-)$ preserves products, we want to show that $C(a,c \times d) \cong C(a,c) \times C(a,d)$.

• Side note: maybe we actually want to do more than this, because technically a product is a whole cone, not just a single object. But maybe this is a good starting point.

However, $C(a,c \times d) \cong C(a,c) \times C(a,d)$ seems to follow immediately from the universal property for products. (I'm not sure if expanding in more detail here would be helpful).

So, since $c \times d$ is a product, we conclude that $C(a,c \times d) \cong C(a,c) \times C(a,d)$, for any $c,d \in C$. We conclude that any functor of the form $C(a,-): C \to \mathsf{Set}$ preserves products.

Now let us assume we have a functor $F: C \to \mathsf{Set}$ so that $F \cong C(a,-)$ for some $a \in C$. Then $F(c \times d) \cong C(a,c \times d)$, because $F \cong C(a,-)$. But we saw already that $C(a, c \times d) \cong C(a,c) \times C(a,d)$. By transitivity of "being isomorphic", we conclude that $F(c \times d) \cong C(a,c) \times C(a,d)$.

I would like to note that $C(a,c) \cong F(c)$ and $C(a,d) \cong F(d)$ and conclude that $C(a,c) \times C(a,d) \cong F(c) \times F(d)$. I think this is probably true: that replacing objects with isomorphic objects should only impact the result of taking the product up to isomorphism. I'm not immediately seeing how to prove this though.

If we assume that $C(a,c) \cong F(c)$ and $C(a,d) \cong F(d)$ implies that $C(a,c) \times C(a,d) \cong F(c) \times F(d)$, then we have that $F(c \times d) \cong C(a,c) \times C(a,d) \cong F(c) \times F(d)$, and so $F$ preserves products. Under this assumption, we conclude that any covariant representable functor preserves products.

David Egolf (Sep 29 2023 at 17:09):

Two things that might warrant some future thought:

• Can we upgrade this argument to incorporate the fact that a product is a cone? Maybe we can think of the product as a special kind of natural transformation to faciliate this.
• Can I see why (or if) switching out isomorphic objects in a diagram will only impact the limit of that diagram up to isomorphism?

Kevin Arlin (Sep 29 2023 at 17:30):

For the first question, yes we can and should: the definition of "$F$ preserves (binary) products" is that if $\pi_A:C\to A,\pi_B:C\to B$ is a product cone then $F(\pi_A):F(C)\to F(A),F(\pi_B):F(C)\to F(B)$ is a product cone as well. Checking that more concrete condition may help you to avoid saying "well, this sure seems obvious" rather than just writing things down, though indeed it ought to eventually seem obvious!

The second question is slightly subtle. Naturally isomorphic diagrams have isomorphic limits, and this is an important result to know eventually but maybe not to prove today; you might like to check directly that isomorphic product diagrams have isomorphic products, since the diagram for a product is just a pair of objects and an isomorphism between such diagrams is just a pair of isomorphisms. That handles both the result I stated and the result you stated in this case. For the result you stated in general, you would want to show that if I have a diagram $D$ with some value $D(j)$ and an object $X$ with an isomorphism $D(j)\cong X,$ then there's a natural isomorphism $D\cong D'$ with $D'(j)=X.$ Then you could apply the result I stated. This is not really an important result at this stage, nor hard to prove once you're quite comfortable working with arbitrary diagrams and their natural isomorphisms, although it's good that you noticed it's not vacuous! It becomes more interesting much further down the road when you find you want to know the word "cofibration".

Chris Grossack (they/them) (Sep 29 2023 at 17:33):

David Egolf said:

• Can I see why (or if) switching out isomorphic objects in a diagram will only impact the limit of that diagram up to isomorphism?

Here's a very boots-on-the-ground approach:

Let's stick with products as a toy example. Say we have isomorphisms $f: A \cong A'$ and $g : B \cong B'$. We want to build an isomorphism $A \times B \cong A' \times B'$. I'll tell you that the trick is to leverage the uniqueness of the universal property!

To get used to reading proofs that say nothing more than "the following diagram commutes", I'll say exactly that! Do you see how to flesh this out into a proof?

Screenshot-2023-09-29-at-10.32.50-AM.png

Chris Grossack (they/them) (Sep 29 2023 at 17:37):

I'll also say that there's a fancier approach, which shows why people care about the "functor of points" methodology. Notice that the representables $\text{Hom}(-, A \times B)$ and $\text{Hom}(-, A' \times B')$ are naturally isomorphic (do you see why? Here we're just working with a family of bijections of sets!). But now Yoneda tells us that $A \times B$ and $A' \times B'$ must have been isomorphic to start with!

Hopefully it's clear that this is cleaner than having to draw the diagrams like the previous proof I outlined, especially when we start working with more complicated limits.

Josselin Poiret (Sep 29 2023 at 19:00):

let me just note though (because I am That Finnicky Person™) that you often don't just want $A \times B \simeq A' \times B'$, you want them to be isomorphic as products, ie. that the product structure as well is respected by this isomorphism. With the above method on representables, it's easy to check, but it is not optional. This is similar to the usual warning that continuous functors have to respect the whole limit cones, not just their tips. Once you start working with objects with additional structure (of which the products are an example), you always want to consider the whole thing, and not just the object.

David Egolf (Sep 29 2023 at 20:47):

Kevin Arlin said:

For the first question, yes we can and should: the definition of "$F$ preserves (binary) products" is that if $\pi_A:C\to A,\pi_B:C\to B$ is a product cone then $F(\pi_A):F(C)\to F(A),F(\pi_B):F(C)\to F(B)$ is a product cone as well.

Let me see how far I can get... To make things easier, I'll consider the special case where our representable functor $F: C \to \mathsf{Set}$ is of the form $F = C(a,-)$ for some object $a \in C$. Hopefully the resulting argument can then be transferred to the more general case where we only know that $F \cong C(a,-)$ for some $a \in C$.

We start out with a product cone $\pi_p: p \times q \to p$ and $\pi_q: p \times q \to q$ in $C$:
product cone

We now apply our functor $C(a,-)$ to this cone, and introduce a test cone $z_p: z \to C(a,p), z_q: z \to C(a,q)$:
test cone and image of product cone

To show that this is a product cone in $\mathsf{Set}$ we need to show that for each $z$, $z_p$, and $z_q$ there is a unique $f: z \to C(a, p \times q)$ so that $(\pi_p)_* \circ f = z_p$ and $(\pi_q)_* \circ f= z_q$.

We make use of the fact that we are in $\mathsf{Set}$, and so we have elements available to us. If the equations $(\pi_p)_* \circ f = z_p$ and $(\pi_q)_* \circ f= z_q$ are to hold, that implies that for each element $x \in z$ we must have:

• $((\pi_p)_* \circ f)(x) = z_p(x)$
• $((\pi_q)_* \circ f)(x)= z_q(x)$

We can draw a diagram illustrating these equations:
equations at x

Because $p \times q$ is a product of $p$ and $q$ in $C$, there is a unique $f(x): a \to p \times q$ that makes this diagram commute.

So, we conclude that for each $x \in z$, a unique value for $f(x)$ exists so that these equations hold:

• $((\pi_p)_* \circ f)(x) = z_p(x)$
• $((\pi_q)_* \circ f)(x)= z_q(x)$

Since we can do this for any $x$, we find that there is a unique $f: z \to C(a, p \times q)$ that makes these equations hold:

• $(\pi_p)_* \circ f = z_p$
• $(\pi_q)_* \circ f= z_q$

We conclude that the image of the product cone $\pi_p: p \times q \to p, \pi_q: p \times q \to q$ under the functor $C(a,-)$ is also a product cone. So, $C(a,-)$ preserves binary products.

It remains to show that if $F \cong C(a,-)$ for some $a \in C$, then $F$ also preserves binary products. But before thinking about this, I want to read some of the other comments above that talk about this sort of thing!

John Baez (Sep 29 2023 at 20:58):

Ultimately one gets use to the fact that if one uses "non-evil" definitions, i.e. definitions that involve isomorphisms between objects, perhaps obeying some equations, rather than equations between objects, everything one does with them is invariant under isomorphisms in the way you'd want. E.g. a functor naturally isomorphic to one that preserves products again preserves products. But I guess it's important to sweat over these facts for a while, and then get used to the idea, and then learn some general results along these lines, and then maybe use a formalism like homotopy type theory where it's all automatic.

David Egolf (Sep 29 2023 at 21:14):

I'm wondering if there was a faster way to do the above.

$C(a, p \times q) \cong C(a,p) \times C(a,q)$ as objects in $\mathsf{Set}$, using the universal property of $p \times q$. Then, I wonder if we can argue something (roughly!) along these lines: $C(a,p) \times C(a,q)$ is the apex for a limit over the discrete diagram with $C(a,p)$ and $C(a,q)$, and since $C(a,p \times q) \cong C(a,p) \times C(a,q)$, I think $C(a,p) \times C(a,q)$ should also be the apex for a limit over the discrete diagram formed by $C(a,p)$ and $C(a,q)$.

I guess the intuition I have is this: if $A$ is an apex for a limit over a diagram $D$ and $A' \cong A$ as objects, then $A'$ is (I hope) also an apex for a limit over $D$. But I would need to prove this!

Probably my plan to prove this would be to create a cone under $A'$ by starting with the limit cone under $A$. To do this, I would use the isomorphism between $A'$ and $A$ to convert this cone to one under $A'$ - morphism by morphism. Then I would check to see if our isomorphism $A' \cong A$ between objects extends to an isomorphism between the two cones we now have under these objects.

John Baez (Sep 29 2023 at 22:50):

David Egolf said:

I guess the intuition I have is this: if $A$ is an apex for a limit over a diagram $D$ and $A' \cong A$ as objects, then $A'$ is (I hope) also an apex for a limit over $D$. But I would need to prove this!

Probably my plan to prove this would be to create a cone under $A'$ by starting with the limit cone under $A$. To do this, I would use the isomorphism between $A'$ and $A$ to convert this cone to one under $A'$ - morphism by morphism. Then I would check to see if our isomorphism $A' \cong A$ between objects extends to an isomorphism between the two cones we now have under these objects.

Yes, all this works. If you do a concrete example of a limit, say a pullback, you can just draw everything you're talking about here (the diagram, a cone over it with apex $A$, an isomorphism between $A$ and $A'$, etc.) you can see how it works. The case of a general limit is harder because you can't draw a "general diagram", so you have to reason more abstractly. But personally I'm so lazy that I often draw a concrete example and then leave it at that.

Mike Shulman (Sep 30 2023 at 02:59):

John Baez said:

But I guess it's important to sweat over these facts for a while, and then get used to the idea, and then learn some general results along these lines, and then maybe use a formalism like homotopy type theory where it's all automatic.

Of course, once homotopy type theory takes over the world, the progression will be reversed. (-:O

Todd Trimble (Sep 30 2023 at 22:47):

David Egolf said:

I'm wondering if there was a faster way to do the above.

$C(a, p \times q) \cong C(a,p) \times C(a,q)$ as objects in $\mathsf{Set}$, using the universal property of $p \times q$. Then, I wonder if we can argue something (roughly!) along these lines: $C(a,p) \times C(a,q)$ is the apex for a limit over the discrete diagram with $C(a,p)$ and $C(a,q)$, and since $C(a,p \times q) \cong C(a,p) \times C(a,q)$, I think $C(a,p) \times C(a,q)$ should also be the apex for a limit over the discrete diagram formed by $C(a,p)$ and $C(a,q)$.

I guess the intuition I have is this: if $A$ is an apex for a limit over a diagram $D$ and $A' \cong A$ as objects, then $A'$ is (I hope) also an apex for a limit over $D$. But I would need to prove this!

Probably my plan to prove this would be to create a cone under $A'$ by starting with the limit cone under $A$. To do this, I would use the isomorphism between $A'$ and $A$ to convert this cone to one under $A'$ - morphism by morphism. Then I would check to see if our isomorphism $A' \cong A$ between objects extends to an isomorphism between the two cones we now have under these objects.

The crucial thing to remember is that $C(a, p \times q) \cong C(a,p) \times C(a,q)$ is supposed to be natural in $a$. In fact, the very definition of product in a category $C$ can be derived directly by supposing given such a natural transformation. Hint: use the Yoneda lemma, applied to natural transformations coming out of $C(-, p \times q)$ !!

If you work through this, then $C(a, -)$ preserves products $p \times q$, precisely by the definition suggested bt the last paragraph.

David Egolf (Oct 01 2023 at 16:14):

Chris Grossack (they/them) said:

David Egolf said:

• Can I see why (or if) switching out isomorphic objects in a diagram will only impact the limit of that diagram up to isomorphism?

Here's a very boots-on-the-ground approach:

Let's stick with products as a toy example. Say we have isomorphisms $f: A \cong A'$ and $g : B \cong B'$. We want to build an isomorphism $A \times B \cong A' \times B'$. I'll tell you that the trick is to leverage the uniqueness of the universal property!

To get used to reading proofs that say nothing more than "the following diagram commutes", I'll say exactly that! Do you see how to flesh this out into a proof?

Screenshot-2023-09-29-at-10.32.50-AM.png

Thanks for explaining this! Below, I try to flesh out the diagram to a proof.

We have $f: A \cong A'$ and $g: B \cong B'$ and we wish to show $A \times B \cong A' \times B'$. In the diagram, we first use the universal property of products to induce a unique morphism from $A \times B$ to $A' \times B'$ by using the maps $f \circ \pi: A \times B \to A'$ and $g \circ \pi: A \times B \to B'$. This is the unique morphism $h: A \times B \to A' \times B'$ so that $\pi \circ h = f \circ \pi$ and $\pi \circ h = g \circ \pi$. So the upper two squares in the diagram commute if $h$ is the upper dashed morphism.

We next similarly induce a morphism $h'$ from $A' \times B' \to A \times B$ so that the lower two squares in the diagram commute. Consequently, the outer square in the diagram commutes. That means that $h \circ h'$ is the unique morphism from $A \times B \to A \times B$ such that $\pi \circ (h \circ h') = f^{-1} \circ f \circ \pi = \pi$ and $\pi \circ (h \circ h') = g^{-1} \circ g \circ \pi = \pi$. The morphism $1_{A \times B}: A \times B \to A \times B$ satisfies these two equations, and since the morphism induced by the universal property of products is unique, we conclude that $h' \circ h = 1_{A \times B}$.

We could then repeat the entire argument with the top and bottom halves of the diagram interchanged, and conclude that $h \circ h' = 1_{A \times B}$. We conclude that $h: A \times B \to A' \times B'$ is an isomorphism, so that $A \times B$ and $A' \times B'$ are isomorphic as objects.

David Egolf (Oct 01 2023 at 16:42):

Chris Grossack (they/them) said:

I'll also say that there's a fancier approach, which shows why people care about the "functor of points" methodology. Notice that the representables $\text{Hom}(-, A \times B)$ and $\text{Hom}(-, A' \times B')$ are naturally isomorphic (do you see why? Here we're just working with a family of bijections of sets!). But now Yoneda tells us that $A \times B$ and $A' \times B'$ must have been isomorphic to start with!

Having a way to think about this that doesn't involve drawing huge diagrams sounds very helpful. Below, I try to use this approach to prove that if $A \cong A'$ and $B \cong B'$ then $A \times A' \cong B \times B'$ as objects.

Our strategy is to first show that $C(-,A \times B) \cong C(-,A' \times B')$ and then use the fact (a corollary of the Yoneda lemma) that this is true exactly if $A \times B \cong A' \times B'$. To show that $C(-,A \times B) \cong C(-,A' \times B')$ we apply both functors to a morphism $f: X \to Y$ in $C$, and consider the following naturality square:
naturality square

We want to find isomorphisms $\alpha_X$ and $\alpha_Y$ so that this square commutes for any choice of $X,Y$ and $f: X \to Y$. Focusing on the left side, given a morphism $m: X \to A \times B$, we wish to find a canonical corresponding morphism $m': X \to A' \times B'$. To induce a morphism to a product $A' \times B'$, we need to first find a morphism to $A'$ and a morphism to $B'$. Our morphism $m: X \to A \times B$ induces a morphism $m_A: X \to A$ and a morphism $m_B: X \to B$ (by the universal property of products). We already have isomorphisms $f: A \to A'$ and $g: B \to B'$. Composing, we get $f \circ m_A: X \to A'$ and $g \circ m_B: X \to B'$. Using the universal property of products, this induces a morphism $\langle f \circ m_A, g \circ m_B \rangle$ from $X$ to $A' \times B'$.

We can visualize the situation so far in this diagram:
induced morphism from X to A' x B'

So, we have taken a morphism $m: X \to A \times B$ and produced a morphism $\langle f \circ m_A, g \circ m_B \rangle: X \to A' \times B'$. We guess that $\alpha_X: C(X, A \times B) \to C(X, A' \times B')$ should be the function that does this, for each $X$. It remains to show that $\alpha_X$ is a isomorphism (a bijection) and that the this makes the naturality square commute.

I'm not quite sure how to do this, and I need to take a break, so I'll stop here (for now, at least). I'm not sure if this is a good way to go about this... it seems a bit complicated!

Todd Trimble (Oct 01 2023 at 22:54):

I'll say here what I meant to suggest and should have really said back here. People, including me, keep harping on the fundamental importance of the Yoneda lemma, but for me it's not necessarily just the statement and conclusion of the Yoneda lemma that is important to keep in mind, but the actual proof. What I am suggesting is that it can be illuminating to run the proof of the Yoneda lemma through specific examples, and see what it tells us.

To say it quickly: the proof of the Yoneda lemma indicates that a natural transformation $\eta: \hom(-, x) \to F$ is uniquely determined by what it does to the identity element $1_x$, i.e., by the element $\eta_x(1_x) \in F(x)$. Let me abbreviate that element to $\theta$. The remainder of the natural transformation $\eta$ is then, by naturality, forced. If it were me teaching category theory to a student one-on-one, then I would get the student to close the book and figure out how this works from scratch, but we can give the formula for $\eta$ in terms of $\theta$ here: for an object $y$, the component $\eta_y: C(y, x) \to F(y)$ is forced to be defined by the formula $\eta_y(f) = F(f)(\theta)$, where $f: y \to x$ is an element of $C(y, x)$.

Now, suppose we define a product of objects $p$ and $q$ in a category to be any representing object for the functor $C(-, p) \times C(-, q)$. This means an object (traditionally denoted $p \times q$) equipped with a natural isomorphism

$C(-, p \times q) \cong C(-, p) \times C(-, q)$.

Exercise: run the proof of the Yoneda lemma through this definition, and retrieve in this way the usual definition of product and its universal property. If you carry out the exercise, then preservation of products by covariant representables will pop out from how the definitions are set up from this procedure.

The moral is that it's the proof of the Yoneda lemma which unites the concept of representability with the concept of universal property. The element $\theta$ above is called a universal element. This was the first really big lesson I learned in category theory many years ago, when I was first learning it from Mac Lane's book, and it is marvelous to me still.

Josselin Poiret (Oct 02 2023 at 13:42):

Mike Shulman said:

John Baez said:

But I guess it's important to sweat over these facts for a while, and then get used to the idea, and then learn some general results along these lines, and then maybe use a formalism like homotopy type theory where it's all automatic.

Of course, once homotopy type theory takes over the world, the progression will be reversed. (-:O

But surely the path going from "not checking details" to "checking details" then back is homotopic to the constant path at "not checking details"

David Egolf (Oct 02 2023 at 17:08):

Todd Trimble said:

I'll say here what I meant to suggest and should have really said back here. People, including me, keep harping on the fundamental importance of the Yoneda lemma, but for me it's not necessarily just the statement and conclusion of the Yoneda lemma that is important to keep in mind, but the actual proof. What I am suggesting is that it can be illuminating to run the proof of the Yoneda lemma through specific examples, and see what it tells us.

The moral is that it's the proof of the Yoneda lemma which unites the concept of representability with the concept of universal property. The element $\theta$ above is called a universal element. This was the first really big lesson I learned in category theory many years ago, when I was first learning it from Mac Lane's book, and it is marvelous to me still.

I've had a vague idea that the Yoneda lemma, representable functors, and universal properties all fit together somehow, but I've never understood it. Thanks for suggesting a specific exercise to help with fitting these pieces together. I'll plan to give it a try!

David Egolf (Oct 02 2023 at 17:31):

Todd Trimble said:

To say it quickly: the proof of the Yoneda lemma indicates that a natural transformation $\eta: \hom(-, x) \to F$ is uniquely determined by what it does to the identity element $1_x$, i.e., by the element $\eta_x(1_x) \in F(x)$. Let me abbreviate that element to $\theta$. The remainder of the natural transformation $\eta$ is then, by naturality, forced. If it were me teaching category theory to a student one-on-one, then I would get the student to close the book and figure out how this works from scratch, but we can give the formula for $\eta$ in terms of $\theta$ here: for an object $y$, the component $\eta_y: C(y, x) \to F(y)$ is forced to be defined by the formula $\eta_y(f) = F(f)(\theta)$, where $f: y \to x$ is an element of $C(y, x)$.

I review how this works below, to refresh my memory. (I will use the notation $C(-,x)$ to mean the same thing as $\hom(-,x)$).

Consider a natural transformation $\eta: C(-,x) \to F$ for $F,C(-,x): C^{op} \to \mathsf{Set}$. We apply each functor to a morphism $f^{op}: x \to y$ in $C^{op}$. I will write $f$ to mean the corresponding morphism in $C$, so $f \in C(y,x)$.

We get the following naturality square:
naturality square

Here, $f^*$ refers to precomposition. So $f^*(g:x \to x) = g \circ f$.

For this square to commute, it must in particular commute for each element of $C(x,x)$. We pick $1_x \in C(x,x)$ and trace it around the diagram. We find that $\eta_y(f^*(1_x)) = F(f^{op}) \circ \eta_x(1_x)$. Setting $\theta = \eta_x(1_x)$, and using $f^*(1_x) = f$, we obtain $\eta_y(f) = F(f^{op})(\theta)$. This argument works similarly for any $f$ and $y$, so that the entire natural transformation $\eta$ is forced once we set $\eta_x(1_x) = \theta$.

David Egolf (Oct 02 2023 at 17:39):

Todd Trimble said:

Now, suppose we define a product of objects $p$ and $q$ in a category to be any representing object for the functor $C(-, p) \times C(-, q)$. This means an object (traditionally denoted $p \times q$) equipped with a natural isomorphism

$C(-, p \times q) \cong C(-, p) \times C(-, q)$.

Exercise: run the proof of the Yoneda lemma through this definition, and retrieve in this way the usual definition of product and its universal property. If you carry out the exercise, then preservation of products by covariant representables will pop out from how the definitions are set up from this procedure.

Huh! Defining a product in terms of a representing object for a functor is quite interesting! I need to take a break now, but I will plan to try and apply the proof of the Yoneda lemma to the definition for $p \times q$ induced by $C(-, p \times q) \cong C(-, p) \times C(-, q)$. It would be very cool to see the usual definition of product (with its universal property) emerge from this.

Todd Trimble (Oct 02 2023 at 17:52):

There is one more tiny thing that should be settled before we take leave of your run-through of the proof of the Yoneda lemma here. You certainly did should that a natural transformation $\eta: C(-, x) \to F$ is uniquely determined by the element $\theta = \eta_x(1_x)$, so that the assignment $\eta \mapsto \theta$ is injective. One should also show that it is surjective, i.e., that any element $\theta \in F(x)$ gives rise to a natural transformation $\eta$ by this formula. This will necessitate consideration of general morphisms $g: y \to z$.

John Baez (Oct 02 2023 at 18:15):

Of course "did should" $\mapsto$ "did show".

David Egolf (Oct 03 2023 at 17:44):

Todd Trimble said:

There is one more tiny thing that should be settled before we take leave of your run-through of the proof of the Yoneda lemma here. You certainly did should that a natural transformation $\eta: C(-, x) \to F$ is uniquely determined by the element $\theta = \eta_x(1_x)$, so that the assignment $\eta \mapsto \theta$ is injective. One should also show that it is surjective, i.e., that any element $\theta \in F(x)$ gives rise to a natural transformation $\eta$ by this formula. This will necessitate consideration of general morphisms $g: y \to z$.

Thanks for pointing this out! I don't think I had understood this part of the Yoneda lemma proof before.

We have a function $u:[C^{op}, \mathsf{Set}](C(-,x),F) \to F(x)$ that sends any natural transformation $\eta: C(-,x) \to F$ to $\eta_x(1_x) \in F(x)$. Above, we saw this: if $\eta: C(-,x) \to F$ is a natural transformation, then its value for $\eta_x(1_x)$ determines all the other data for $\eta$. So, if $\eta_x(1_x) = \eta'_x(1_x)$ for $\eta, \eta':C(-,x)\to F$, then $\eta = \eta'$. Thus, $u$ is an injective function.

However, we wish to show that $u$ is a bijection. To do this, we next show that $u$ is surjective. To show it is surjective, we pick an arbitrary element $\theta$ of $F(x)$ and show there is some $\eta: C(-,x) \to F$ so that $u(\eta) = \theta$. The condition $u(\eta)=\theta$ implies that $\eta_x(1_x) = \theta$. We saw earlier that specifying this information forces by naturality $\eta_y(f) = F(f^{op})(\theta)$ for any $y \in C$ and any $f: y \to x$. It remains to show that the data $\eta$ defined in this manner actually constitutes a natural transformation when $\eta_x(1_x) = \theta$ is an arbitrarily chosen element of $F(x)$.

To show that this $\eta$ is a natural transforation, we seek to show that an arbitrary naturality square for it commutes. We obtain the following naturality square by evaluating $C(-,x)$ and $F$ on the morphism $g^{op}: y \to z$ (I use $g$ to denote the corresponding morphism $g: z \to y$ in $C$):
naturality square

Here, $g^*$ refers to the function that precomposes $g$ before an input morphism $f$ , so $f \mapsto f \circ g$.

To show this square commutes, we evaluate the "bottom left" and "top right" paths around the square at an arbitrary element $f \in C(y,x)$.

For the bottom left path, we get:
$F(g^{op})\circ \eta_y(f) = F(g^{op}) \left( F(f^{op})(\theta)\right)$

For the top right path, we get:
$\eta_z \circ g^*(f) = \eta_z(f \circ g)=F((f \circ g)^{op})(\theta)$
By definition of $C^{op}$, $(f \circ g)^{op} = g^{op} \circ f^{op}$.
So, $\eta_z \circ g^*(f) = F(g^{op} \circ f^{op})(\theta)$.
Using functoriality of $F$:
$\eta_z \circ g^*(f) = F(g^{op}) \circ F(f^{op})(\theta) = F(g^{op}) \left( F(f^{op})(\theta)\right)$.

We conclude that this arbitrary naturality square commutes, and so $\eta$ really is a natural transformation.
That means that our function $u: [C^{op}, \mathsf{Set}](C(-,x),F) \to F(x)$ acting by $\eta \mapsto \eta_x(1_x)$ is not only injective, but also surjective: for any $\theta \in F(x)$, there exists an $\eta$ so that $u(\eta) = \theta$.

So, we have an isomorphism $u:[C^{op}, \mathsf{Set}](C(-,x),F) \cong F(x)$ in $\mathsf{Set}$.

Todd Trimble (Oct 03 2023 at 19:54):

That would get a big check mark from my red pen. :grinning:

David Egolf (Nov 17 2023 at 22:54):

I want to return to this for a bit, because these concepts are important and they keep coming up when I try to understand other things!

What I want to understand:

• The preservation of limits by covariant representable functors
• I'd be happy to start by understanding this for products

Where I'm at currently:

• I understand the proof of the Yoneda lemma, I think (see discussion above)

• I currently use this definition for a limit of a diagram:
  A limit of a diagram $F: J \to C$ in $C$ is an object $x \in C$ together with a natural isomorphism $\alpha: C(-,x) \cong Cone(-,F)$. (I'm following Riehl's "Category Theory in Context", page 75).

• I know that, by the Yoneda lemma, a natural isomorphism $\alpha: C(-,x) \cong Cone(-,F)$ uniquely specifies (and is specified by) a particular element of $Cone(x,F)$. This special element is $\alpha_x(1_x) \in Cone(x,F)$. I think this is the "universal cone" associated with a limit.

David Egolf (Nov 17 2023 at 22:59):

Todd Trimble said:

Exercise: run the proof of the Yoneda lemma through this definition, and retrieve in this way the usual definition of product and its universal property. If you carry out the exercise, then preservation of products by covariant representables will pop out from how the definitions are set up from this procedure.

The exercise described in this quote is what I would like to do next.

However, to do this, I think I first need to state what it means for a functor to preserve a limit. In particular, I want to do this using my current definition for a limit, in terms of a natural isomorphism from a representable functor to the cone functor.

David Egolf (Nov 17 2023 at 23:04):

So, let us assume we have a functor $G: C \to D$. And let us assume we have a diagram $F: J \to C$ that has a limit in $C$. The limit of $F$ is described by the following data:

• An object $x \in C$
• A natural isomorphism $\alpha: C(-,x) \cong Cone(-,F)$

I decree that $G$ "preserves the limit" for the diagram $F$. But what does that mean, exactly? Given our diagram $F: J \to C$, we can get a corresponding diagram $G \circ F: J \to D$ in $D$. I think the idea is that:

1. This diagram will have a limit in $D$
2. We can compute this limit using the data that describes the limit of $F$ in $C$

David Egolf (Nov 17 2023 at 23:05):

To describe the limit of $G \circ F$, we'll need two pieces of data:

1. An object $x' \in D$
2. A natural isomorphism $\alpha': D(-,x') \cong Cone(-,G \circ F)$

It seems reasonable to guess that $x' = G(x)$.
It remains to form a guess for $\alpha'$ using $\alpha$ and $x$.

So, we are looking for a natural isomorphism $\alpha': D(-,G(x)) \cong Cone(-,G \circ F)$.
Let's consider some component of this, $\alpha'_y: D(y,G(x)) \cong Cone(y, G \circ F)$.
This is a bijective function that takes a morphism $m: y \to G(x)$ and produces a cone with apex $y$ over the diagram $G \circ F$.
What is a cone over $G \circ F$ with apex $y$? Part of the data of such a cone is a bunch of "leg" functions $\lambda_j: y \to G(F(j))$ where $j \in J$ is an object in the category $J$ that determines the shape of our diagrams.

David Egolf (Nov 17 2023 at 23:20):

I want to somehow build these "leg" functions $\lambda_j$ from analogous ones in $C$, using the fact that we have a limit for the diagram $F$ in $C$ and that $G$ preserves this limit. But I'm not quite seeing how to do this yet.

Oh! Maybe I can use the Yoneda lemma, and note that our natural isomorphism $\alpha'$ is determined by $\alpha'_{G(x)}(1_{G(x)})$. So, I should probably pay special attention to that element in $Cone(G(x), G \circ F)$. I strongly suspect that this special element will be the image of the cone $\alpha_x(1_x) \in Cone(x,F)$ under the functor $G$!

(Apologies for the multiple messages: I have to split things up so that zulip can render the math).

David Egolf (Nov 18 2023 at 00:25):

So, my guess is this: we say that $G: C \to D$ preserves a limit for the diagram $F: J \to C$ when the following holds.

Assume that an original limit of $F: J \to C$ is determined by this data:

• $x \in C$
• $\alpha: C(-,x) \cong Cone(-,F)$

Then we have a limit for $G \circ F: J \to D$ in $D$, determined by this data:

• $G(x) \in D$
• $\alpha': D(-,G(x)) \cong Cone(-,G \circ F)$
• where we have $\alpha'_{G(x)}(1_{G(x)}) = G(\alpha_x(1_x)) \in Cone(G(x), G \circ F)$

I'll take a break now, but maybe I'll next investigate if this guess matches with the real definition.

Todd Trimble (Nov 18 2023 at 21:21):

Okay, I'll play it back starting from the end of what you write. So we start from a limit cone for $F: J \to C$, with the limit $x$ placed at the apex, and cone components $x \to Fj$ indexed by objects $j$ of $J$. (I'm not seeing right away what notation you are using for these, but I'll just name them $f_j: x \to Fj$.) Then we can apply $G: C \to D$ to that, to get a cone with apex $Gx$ and components $G(f_j): Gx \to GFj$.

Todd Trimble (Nov 18 2023 at 21:21):

As you point out, this corresponds, via Yoneda, to a map $D(-, Gx) \to Cone(-, GF)$. So far, we haven't used anything about $G$ except that is is a functor.

Todd Trimble (Nov 18 2023 at 21:21):

Definition: $G$ preserves the limit $x$ of $F: J \to C$, with limit cone $f_j: x \to Fj$, if the cone $Gf_j: Gx \to GFj$ is a limit cone for $GF: J \to D$.

Todd Trimble (Nov 18 2023 at 21:21):

This is the same as saying that the map $D(-, Gx) \to Cone(-, GF)$ is an isomorphism. Or, in other language, that the functor $Cone(-, GF)$ is representable by the object $Gx$.

David Egolf (Nov 18 2023 at 22:08):

Great! I think that matches with the guess I gave above! Now that I better understand what it means to preserve a limit, I can try and do this:

Todd Trimble said:

Exercise: run the proof of the Yoneda lemma through this definition, and retrieve in this way the usual definition of product and its universal property. If you carry out the exercise, then preservation of products by covariant representables will pop out from how the definitions are set up from this procedure.

So that's next in my plan for figuring this stuff out. I hope to work on it in the next few days.

Todd Trimble (Nov 18 2023 at 22:10):

Yeah, that's what I got from what you wrote, so you're on the right track and making progress!

David Egolf (Nov 19 2023 at 18:22):

Starting on the exercise, the first thing is to take the following as the definition of a product for two objects $p$ and $q$:

• an object $p \times q$
• a natural isomorphism $\alpha: C(-, p \times q) \cong C(-, p) \times C(-,q)$

Before accepting this definition, I want to show that it is equivalent to the one I've been using most recently. To do that, I want to show that $C(-,p) \times C(-,q):C^{op} \to \mathsf{Set}$ is naturally isomorphic to $Cone(-,F):C^{op} \to \mathsf{Set}$, where $F: J \to C$ is the discrete diagram on the two objects $p$ and $q$.

David Egolf (Nov 19 2023 at 19:47):

To see that these two functors are naturally isomorphic, we check that any naturality square commutes. Evaluating each functor on $f^{op}: y \to x$ in $C^{op}$ (which has a corresponding morphism $f:x \to y$ in $C$), we get:
naturality square

A cone with apex $y$ over $F$ is a natural transformation $\beta: \Delta_y \to F$, where $\Delta_y: J \to C$ is the functor constant at $y$. This natural transformation has two components, which I'll call $\beta_1: y \to p$ and $\beta_2: y \to q$. We can then set $\gamma_y$ to act as follows: $\gamma_y(\beta) \mapsto (\beta_1, \beta_2)$. This function I believe is a bijection from $Cone(y,F)$ to $C(y,p) \times C(y,q)$, as it is injective and surjective.

David Egolf (Nov 19 2023 at 19:47):

It remains to show the square commutes. Let $\beta: \Delta_y \to F$ be an element of $Cone(y,F)$. Next we compute $\gamma_x \circ f^*(\beta)$. Note that $f^*(\beta)$ is the natural transformation having components $(f^*(\beta))_1 = \beta_1 \circ f$ and $(f^*(\beta))_2 = \beta_2 \circ f$. So $\gamma_x \circ f^*(\beta) = (\beta_1 \circ f, \beta_2 \circ f)$.

Going the other way around the square, we compute $(f^* \times f^*) \circ \gamma_y (\beta) = (f^* \times f^*)(\beta_1, \beta_2) = (\beta_1 \circ f, \beta_2 \circ f)$. We conclude that the square commutes, and so $\gamma:Cone(-,F) \cong C(-,p) \times C(-,q)$.

David Egolf (Nov 19 2023 at 20:07):

Now we are in business, hopefully. Assume we have a product for $p$ and $q$. We take this to mean that we have:

• an object $p \times q$
• a natural isomorphism $\alpha: C(-,p \times q) \cong C(-,p) \times C(-,q)$

The first part of the proof of the Yoneda lemma (specialized to this case) involves showing that once we set $\alpha_{p \times q}(1_{p \times q})$ then all the rest of the definition of $\alpha$ is forced.

David Egolf (Nov 19 2023 at 20:30):

We evaluate each functor involved here on the morphism $f^{op}: p \times q \to y$ (with corresponding morphism $f: y \to p \times q$ in $C$):

naturality square

Tracking $1_{p \times q}$ around the diagram, we learn that for the diagram to commute we must have $\alpha_y(f) = (\theta_p \circ f, \theta_q \circ f)$, where $\theta = (\theta_p, \theta_q)= \alpha_{p \times q}(1_{p \times q})$. And this is true for any $f: y \to p \times q$, so that all of the definition of $\alpha$ is forced once we define $\alpha_{p \times q}(1_{p \times q})$.

David Egolf (Nov 19 2023 at 20:41):

So far, I'm not seeing how this helps us conclude that products are preserved by covariant representables. But I will press on to the second part of the proof!

We next pick an arbitrary element $\theta'$ of $C(p \times q,p) \times C(p \times q,q)$ and show that this induces a natural transformation $\beta: C(-,p \times q) \to C(-,p) \times C(-,q)$. To do this, we set $\beta_{p \times q}(1_{p \times q}) = \theta'$. By the first part of the proof of the Yoneda lemma, we know that this forces the definition of all the other components of $\beta$ (if $\beta$ is to be a natural transformation). But it remains to show that the resulting structure is actually a natural transformation.

David Egolf (Nov 19 2023 at 21:01):

Here is an arbitrary naturality square, for a morphism $g^{op}: y \to z$ in $C^{op}$:
naturality square

We track an element $f \in C(y, p \times q)$ around the diagram to demonstrate commutativity.

Taking the bottom left path, we get:
$(g^* \times g^*) \circ \beta_y(f) = (g^* \times g^*) \circ (\theta'_p \circ f, \theta'_q \circ f)$
$=(\theta'_p \circ f \circ g, \theta'_q \circ f \circ g)$

David Egolf (Nov 19 2023 at 21:03):

Taking the top right path, we get:
$\beta_z \circ g^*(f) = \beta_z (f \circ g)$
$=(\theta'_p \circ (f \circ g), \theta'_q \circ (f \circ g))$
We conclude that the square commutes, and so setting $\beta_{p \times q}(1_{p \times q}) = \theta'$ uniquely induces a natural transformation $\beta: C(-,p \times q) \to C(-,p) \times C(-,q)$.

David Egolf (Nov 19 2023 at 21:04):

Hmm. I seem to arrived at the end of the proof of the Yoneda lemma (specialized to a particular case), and I do not feel like I better understand why products are preserved by covariant representables. I'll take a break and see if I can come back and look at this with a fresh perspective!

Ah, I haven't done this part yet "retrieve in this way the usual definition of product and its universal property". Maybe that's what I'm missing!

David Egolf (Nov 19 2023 at 22:01):

I think I've figured some things out!
We start with a common definition for a product of $p$ and $q$:
product diagram

Referencing this picture, we need the following data to have a product of $p$ and $q$:

• an object $p \times q$
• a cone $\theta$ with apex $p \times q$ over the discrete diagram $F: J \to C$ with $p$ and $q$

And this additional condition needs to hold:

• For every cone $\theta'$ with some apex $y$, so $\theta' \in Cone(y, F)$, there is a unique morphism $f:y \to p \times q$ so that $f^* \theta = \theta'$. That is, there is a unique $f$ so that $(\theta_p \circ f, \theta_q \circ f) = (\theta'_p, \theta'_q)$.