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: Yoneda lemma applications

David Egolf (Feb 08 2022 at 17:06):

I just learned about the Yoneda lemma. The book I was reading makes it sounds like a really big deal:

We can paint a better—rather, a complete—picture of an object once we investigate its interactions with all other objects. This theme finds its origins in an—if not the most—important result in category theory.

(from "Topology, A Categorical Approach")

However, in my opinion, they don't immediately support this claim of huge importance.

What are some reasons that the Yoneda lemma is important? What are some ways in which it has been applied?

Leopold Schlicht (Feb 08 2022 at 17:45):

Here are the first three applications that come to my mind:

1. In categorical homotopy theory one usually identifies maps from a standard simplex $\Delta^n$ to a simplicial set $S_\bullet$ with the $n$-simplices of $S_\bullet$.
2. What is the subobject classifier of $\mathrm{Fun}(C^\mathrm{op}, \mathbf{Set})$? By the Yoneda lemma, any subobject classifier $\Omega$ must have the property that $\Omega(A)\cong \mathrm{Fun}(C^\mathrm{op}, \mathbf{Set})(C(-,A), \Omega)\cong\mathrm{Sub}(C(-, A))$ for all $A\in C$. So here the Yoneda lemma is useful in guessing what the subobject classifier is. (However, you still have to check that this guessed definition has the universal property of the subobject classifier!)
3. In Basic Bicategories Leinster uses the fully faithfulness of the bicategorical Yoneda embedding to prove that every bicategory is biequivalent to a 2-category.

Leopold Schlicht (Feb 08 2022 at 17:50):

The Yoneda embedding is used in stating that $\mathrm{Fun}(C^\mathrm{op}, \mathbf{Set})$ is the free cocompletion of $C$. It is also used in proving that every presheaf can be written as a colimit of representable presheaves: https://en.wikipedia.org/wiki/Density_theorem_(category_theory).

Leopold Schlicht (Feb 08 2022 at 17:52):

Also, often it is easier to prove $\hom(-,A)\cong\hom(-,B)$ or $\hom(A,-)\cong\hom(B,-)$ than to exhibit an isomorphism $A\cong B$ by hand.

Leopold Schlicht (Feb 08 2022 at 17:54):

A good list of applications of the last kind is https://matheplanet.com/matheplanet/nuke/html/article.php?sid=1430, but it's German.

Leopold Schlicht (Feb 08 2022 at 18:02):

Also, check out https://ncatlab.org/nlab/show/Yoneda+lemma#applications.

Ralph Sarkis (Feb 08 2022 at 18:11):

Leopold Schlicht said:

Also, often it is easier to prove $\hom(-,A)\cong\hom(-,B)$ or $\hom(A,-)\cong\hom(B,-)$ than to exhibit an isomorphism $A\cong B$ by hand.

In this vein, see Section 8.4 of Steve Awodey's book.

Leopold Schlicht (Feb 08 2022 at 18:35):

The nLab proof http://nlab-pages.s3.us-east-2.amazonaws.com/nlab/show/adjoints+preserve+(co-)limits uses the Yoneda lemma, but it is not completely rigorous - see https://math.stackexchange.com/questions/101005/right-adjoints-preserve-limits.

John Baez (Feb 08 2022 at 20:07):

Emily Riehl has presented a nice proof using the Yoneda lemma that multiplication of natural numbers distributes over addition, by proving that cartesian product distributes over disjoint union in the category of finite sets:

John Baez (Feb 08 2022 at 20:08):

Of course, this would not convince a skeptic that the Yoneda Lemma is important, but it's easier to understand than some of the more serious applications, and it conveys the general flavor of how it's used.

John Baez (Feb 08 2022 at 20:09):

The first step, of course, is to get in the state of mind where you can believe, or at least pretend to believe, that the distributivity of $\times$ over $+$ in FinSet is something that deserves explanation - not just something "obvious".

David Egolf (Feb 09 2022 at 00:20):

Thanks everyone! That's a lot of great examples and references! I'll have to make reference of this thread as I learn more.

Leopold Schlicht said:

Also, often it is easier to prove $\hom(-,A)\cong\hom(-,B)$ or $\hom(A,-)\cong\hom(B,-)$ than to exhibit an isomorphism $A\cong B$ by hand.

That makes sense!

David Egolf (Feb 09 2022 at 00:23):

For the record, as someone interested in imaging, the emphasis on understanding an object by its interactions is exciting: in imaging we usually just get to see how an object interacts with other objects, and don't get to see the object itself. I am hoping the Yoneda lemma might be helpful for thinking about imaging for this reason.

John Baez (Feb 09 2022 at 00:40):

David Egolf said:

Leopold Schlicht said:

Also, often it is easier to prove $\hom(-,A)\cong\hom(-,B)$ or $\hom(A,-)\cong\hom(B,-)$ than to exhibit an isomorphism $A\cong B$ by hand.

That makes sense!

You can see that Emily Riehl proves the distributive law using just this method.

Nima Motamed (Feb 09 2022 at 15:53):

This might be a bit too specific and simple of an application, but it is one that I particularly like - hope there's something in it for you as well.
The example is from coalgebraic logic, which is a general, category-theoretic framework allowing one to reason uniformly about (modal) logics interpreted over all kinds of transition structures (Kripke frames, Markov chains, automata...). This is all (mostly!) uniform in the kind of transition structure under consideration, which is encoded in a "type functor" $T$, which in its most simple form is an endofunctor on $\mathbf{Set}$.
Now, in order to define a modal logic for our transition systems (which are $T$-coalgebras), we need a propositional logic together with modalities. Skipping over some of the details of how the propositional logic is defined (and how the modalities are added precisely), we need a way to define the semantics of modalities. The approach of coalgebra considers modal formulas $\heartsuit \varphi$ to be "propositions/predicates on the possible one-step transitions of a transition system". This fits in with what is done in e.g. basic modal logic over Kripke frames (which can be treated as coalgebras for the covariant powerset functor $\mathcal{P}$), where asserting $\Box \varphi$ means $\varphi$ is true at all successor states (which are all one-step transitions from the original state). In a sense, the $\Box$-modality is mapping a proposition $\varphi$ (which can be treated as the set of states at which $\varphi$ holds) to a set of sets of states, namely the set of all sets $X$ such that $X \subseteq \varphi$. It can be verified that $\Box$ is a natural transformation $\Box: 2^{(-)} \Rightarrow 2^{\mathcal{P}(-)}$. Generalizing this, a (unary) modality $\heartsuit$ for coalgebra type $T$ is a natural transformation $\heartsuit: 2^{(-)} \Rightarrow 2^{T(-)}$.

This is where the Yoneda lemma comes in. Applying it, we find that the (unary) modalities for our type functor $T$ are in correspondence with the elements of $2^{T 2}$ (in which we apply $T$ to the two-element set). This allows us to do something that I find amazingly useful: we can systematically "search" through and define modalities for any kind of transition system. In fact, for many functors (such as e.g. $\mathcal{P}$), we get that there is a finite amount of modalities one could consider (16 unary modalities for Kripke frames!). We can then also show that we have a kind of "normal form" for our logics, since it can be shown that each modality is a (possibly infinite) join/union/disjunction of certain "elementary" modalities.

There is a lot that I left out of course, and some care needs to be taken (e.g. this really is only about modalities which concern only a single step of transitions), but when I learned this it really stuck with me for some reason. In case anything's unclear about this, I would be glad to try (and potentially fail) to explain it further :)

Fawzi Hreiki (Feb 09 2022 at 16:42):

I'm surprised no one has mentioned Cayley or Dedekind's theorems as special cases (for groups and posets respectively).

Fawzi Hreiki (Feb 09 2022 at 16:52):

Also, the fact that the Yoneda embedding is full and faithful immediately implies that $C$ is a dense subcategory of $\text{PSh}(C)$. This means that every presheaf $X$ on $C$ is the colimit of the diagram $C/X \rightarrow C \hookrightarrow \text{PSh}(C)$. Thus, every functor $C \rightarrow E$ to a cocomplete category $E$ (essentially) uniquely (left Kan) extends to a cocontinuous functor $\text{PSh}(C) \rightarrow E$. Thus, the Yoneda embedding $C \hookrightarrow \text{PSh}(C)$ realises $\text{PSh}(C)$ as the free cocompletion of $C$.

If $C$ is some category of basic shapes or spaces, then $\text{PSh}(C)$ consists of all the possible formal glueings of these shapes/spaces. Usually you want to impose some colimit relations, giving you a sheaf subcategory $\text{Sh}(C, J) \hookrightarrow \text{PSh}(C)$. This is the starting point for a lot of contemporary geometry (manifolds, sheaves, schemes, stacks, etc..).

David Egolf (Feb 09 2022 at 18:48):

Nima Motamed said:

This might be a bit too specific and simple of an application, but it is one that I particularly like - hope there's something in it for you as well.
The example is from coalgebraic logic, which is a general, category-theoretic framework allowing one to reason uniformly about (modal) logics interpreted over all kinds of transition structures (Kripke frames, Markov chains, automata...).

I assure you the example is not too simple, for me at least! This application really grabs my interest. Transitioning between different states, where different statements are true in different states, sounds like something I want to learn more about. To relate this to image reconstruction - which is my big area of interest - different states could corresponds to having collected different observations of an unknown object, and the statements (with varying truth values across states) could be along the lines of "Given the observations obtained in this state, the unknown object could have property $x$".

I would like to try and understand what you said. Some of my questions may be a bit basic. I welcome any explanations you are willing and able to share!

This is all (mostly!) uniform in the kind of transition structure under consideration, which is encoded in a "type functor" $T$, which in its most simple form is an endofunctor on $\mathbf{Set}$.

I've seen people talk about types, using notation like $n: \mathbb{Z}$ to mean $n$ is of the type "integers". I've also seen how we can label things in a fibred(?) way using functors: for a functor $F: C \to D$ we can say $c \in C$ has label (type?) $d$ if $c \in F^{-1}(d)$. Is this the kind of functor you are talking about here?

Now, in order to define a modal logic for our transition systems (which are $T$-coalgebras), we need a propositional logic together with modalities. Skipping over some of the details of how the propositional logic is defined (and how the modalities are added precisely), we need a way to define the semantics of modalities.

I had not heard of modal logic before! Checking the nlab, it looks like it's a setting for doing logic with additional fancy operators that encode more complicated properties of a statement (e.g. $p$ could be true; $p$ will eventually be true). That's really cool!

The approach of coalgebra considers modal formulas $\heartsuit \varphi$ to be "propositions/predicates on the possible one-step transitions of a transition system".

Let's see. Say $\varphi$ is a statement in a given state (it is either true or false in that state). Then as we move to another state, its truth value could change in some way. If I understand, a modal formula is a statement about how this change in truth values can occur. (e.g. $\heartsuit \varphi$ could be: If $\varphi$ was true in state $A$, it becomes false in state $B$).

This fits in with what is done in e.g. basic modal logic over Kripke frames (which can be treated as coalgebras for the covariant powerset functor $\mathcal{P}$), where asserting $\Box \varphi$ means $\varphi$ is true at all successor states (which are all one-step transitions from the original state).

I see. Here $\Box \varphi$ is a bit more complicated, in that it talks about how the truth value of $\varphi$ in numerous immediate successor states is related to its truth value in the starting state.

Maybe I'll pause here before trying to understand the rest, to give people a chance to elaborate/clarify, should they wish.

Nima Motamed (Feb 10 2022 at 10:40):

David Egolf said:

I assure you the example is not too simple, for me at least! This application really grabs my interest. Transitioning between different states, where different statements are true in different states, sounds like something I want to learn more about. To relate this to image reconstruction - which is my big area of interest - different states could corresponds to having collected different observations of an unknown object, and the statements (with varying truth values across states) could be along the lines of "Given the observations obtained in this state, the unknown object could have property $x$".

Yes, this sounds like a perfect example of what coalgebra, modal logic and therefore coalgebraic modal logic is equipped to handle. Nice one!

I would like to try and understand what you said. Some of my questions may be a bit basic. I welcome any explanations you are willing and able to share!

I would be glad to; though it might be best to talk about the basics and specifics of modal logic, coalgebra and coalgebraic logic in a different topic, so the focus here can stay on applications of the Yoneda lemma. I'll answer the following here though, just for clarity :)

I've seen people talk about types, using notation like $n: \mathbb{Z}$ to mean $n$ is of the type "integers". I've also seen how we can label things in a fibred(?) way using functors: for a functor $F: C \to D$ we can say $c \in C$ has label (type?) $d$ if $c \in F^{-1}(d)$. Is this the kind of functor you are talking about here?

Not precisely: I am using "type" in quite a loose sense, as something describing the transition structures we are interested in. The functor $T$ is really just any endofunctor, though sometimes we make assumptions abouts its properties if needed. The functor $T$ can be considered to represent all of the different ways a single step of transitions can look like in the transition structure we're interested in. Take Kripke frames, which are just unlabelled non-deterministic transition systems, or more simply just binary relations $R$ on a set $S$. Such a binary relation $R$ can equivalently be treated as a function $r: S \to \mathcal{P} S$, with $r(s) = \{t \in S \mid sRt\}$, i.e. the set of all successor states of $s$. A single step of transitions in a Kripke frame really is just a set of successor states. So Kripke frames are $\mathcal{P}$-coalgebras.

If you would be interested in deterministic automata for some alphabet $\Sigma$, then you can verify that these are precisely coalgebras for the functor $TX = X^\Sigma \times 2$, ignoring the requirements of a finite set of states and a distinguished initial state.