Sam Auyeung

Sam Auyeung

The Yoneda Lemma

7 minute read

Published:

In math, we often study an object indirectly. For example, if we have a group $G$, one way to study it is to study representations $G \to GL(V)$. Or if we want to study a ring $R$, we can instead study $R$-modules. We can go further and create categories such as the category of $R$-modules.

So say the object we want to study is a category $C$. If the morphisms in $C$ form sets, then we can study “representations” which are just functors $C \to \text{Set}$. We pick $\text{Set}$ partly because we understand it fairly well and also because many categories are enrichments of $\text{Set}$; e.g. a group is a set that has some additional structure. In a way, if we want a general theorem to apply to a lot of categories, then $\text{Set}$ is a natural option and requiring that the morphisms of $C$ form sets seems resonable to me. We wouldn’t pick $\text{Grp}$, for example, because lots of categories aren’t set up to interact well with $\text{Grp}$.

Similar to how a ring $R$ is an $R$-module over itself and so will show up in the category of $R$-modules as a special object ($R$ is special since $R$-$\text{Mod}$ has a monoidal structure which is tensoring over $R$) we might similarly want to have the category $C$ itself show up among the functor category. The easiest thing to do is just to send $X$ to $\hom(X,-)$ or $\hom(-,X)$ and a morphism $f:X \to Y$ easily defines a natural transformation between the hom functors. In this sense, we’re embedding $C$ into the category of functors $C \to \text{Set}$ so we have the original $C$ to study within this expansion. This embedding should not only embed objects but also morphisms. Note that at this stage, it’s essential to have the structure of sets so that the notion of injective morphisms even makes sense.

Formalism

It’s time to be more formal. We’ll frame this contravariantly though we could approach it covariantly. Let’s first make the assumption that our category $C$ of interest is locally small. This just means that $\hom(X,Y)$ is truly a set for all pairs of objects $X,Y$ rather than being too big (like the set of all sets or some other paradoxical thing). Also, let $\text{Set}^{C^\text{op}}$ be the category whose objects are functors $C \to \text{Set}$ and whose morphisms are natural transformations.

Recall that if $F,G:C \to D$ are two functors, then a natural transformation $\eta:F \to G$ is a lot of data. For each object $X \in C$, we have a $\eta_X:F(X) \to G(X)$ and it should be compatible with how $F,G$ treats morphisms of $C$. That is, if $\psi:X \to Y$ is a morphism of $C$, then $\eta_Y \circ F(\psi) = G(\psi) \circ \eta_X$. If every $\eta_X$ is an isomorphism, then we say $\eta$ is a natural isomorphism.

Let’s have $F = \hom(-,Y)$ where $Y$ is an object of $C$. Then, the Yoneda Lemma tells us that $F(X)$ is in bijection with $\text{Nat}(\hom(-,X),F)$. Except, the Yoneda Lemma doesn’t require $F$ to be $\hom(-,Y)$. $F:C \to \text{Set}$ can be any functor at all so long as $C$ is locally small.

Theorem (Yoneda Lemma): Let $C$ be a locally small category and $F:C \to \text{Set}$ is any functor. Let $X$ be any object in $C$. Then the set $F(X)$ is in bijection with the set $\text{Nat}(\hom(-,X),F)$; i.e. the set of natural transformations is in bijection with the set $F(X)$.

Proof: Let $c \in F(X)$ (this makes sense since $F(X)$ is a set). Define $\eta^c:\hom(-,X) \to F$ by $\eta^c_Y:\hom(Y,X) \to F(Y)$ which sends $g \mapsto F(g)[c]$. So we have a mapping $c \mapsto \eta^c$. On the other hand, let $\eta$ be any natural transformation. Note that $\eta_X:\hom(X,X) \to F(X)$ gives an element in $F(X)$ since at least $\text{id}_X \in \hom(X,X)$. So we have a second mapping $\eta \mapsto \eta_X(\text{id}_X)$. Then, one can see that these two mappings are inverses. For $c \mapsto \eta^c \mapsto \eta^c_X(\text{id}_X)$ and $\eta^c_X(\text{id}_X) = F(\text{id}_X)[c]$. But $F(\text{id}_X) = \text{id}_{F(X)}$ by definition of functors. We can check the other way easily. $\square$

Corollary 1: The Yoneda embedding $\mathscr{Y}:C \to \text{Set}^{C^\text{op}}$ is fully faithful; i.e. is surjective and injective when applied to morphism sets.

Corollary 2: $X \cong Y$ in $C$ if and only if the represented functors $\hom(-,X) \cong \hom(-,Y)$.

Commentary

The Yoneda Lemma then establishes a maxim for us. In order to understand an object $X$ in the context of its category $C$, we need no more or less than to study all its morphisms with other objects in the category. Actually, we don’t even need all the morphisms; we can pick if we want morphisms to other objects or morphisms from other objects (pick covariant or contravariant). Put more colloquially, if we think of morphisms as relations, then the maxim is “Show me who your friends are and I’ll tell you who you are.” The internet doesn’t seem to have consensus on who said this but it’s been said in various ways.

So to recap a bit and use a covariant presentation for variety: The context of the Yoneda Lemma is to first capture all the morphisms as an object $X$ of study in its own right: $\hom(X,-)$. We then contextualize this object by placing in its own category $\text{Set}^{C^\text{op}}$. The lemma tells us that if we do the “placing” correctly, it is an embedding not only of objects but also bijections on morphisms. Thus, we can think of the category $\text{Set}^{C^\text{op}}$ as an expansion of the original category $C$. In the expansion, we have extra functors $F:C \to \text{Set}$ which aren’t represented as $\hom(X,-)$. Since there are a lot of functors $C\to \text{Set}$ because sets have very little structure, our category is enlarged quite a bit. The Yoneda Lemma tells us that it is still the case that for any object $A$, $F(A)$ is in “natural” bijection with $\text{Nat}(\hom(A,-), F)$.

Appendix: Language

I don’t know much about how category theory might show up in the study of either natural language or coding languages but I have heard it mentioned before. It’s rather interesting to think about a language as a category where either words or tokens are the objects and there are relations between tokens which serve as morphisms. An example of a functor would be translation. We want to map tokens to tokens and relations to relations. But this can be quite a challenge. Say we’re trying to translate Latin to English. Word order is rather important in English and clues us into the relations between words. But word order is less stringent in Latin and writers have freedom to choose word order for different emphasis. So how do you map a word-order dependent relation to a word-order independent relation? There are many different possible translations (many different functors).

This category-theoretic view of language might not be that fruitful but it’s at least a fun example for me to apply some category-theoretic thinking to subjects which don’t normally receive such application.

You May Also Enjoy

The Entropic Central Limit Theorem and Berry-Esseen Theorem

3 minute read

Published:

In this post, I’ll revisit the Central Limit Theorem again, this time with a focus on entropy. I’ll state a few results at the end without proof including the Berry-Esseen Theorem which tells us about the convergence of the usual Central Limit Theorem. We’ll work with continuous random variables and their density functions. Recall that for a random variable $X:(\Omega,\mu) \to \mathbb{R}$ with density $f$, the entropy is defined as $H[f] = -\int_\Omega f(x) \ln f(x)\,d\mu$. We’ll just work with $\Omega = \mathbb{R}$ and the usual Lebesgue measure.

Efficiency and Sufficiency with an Appendix on Muon Decay, Chirality, and Parity-Violation

16 minute read

Published:

Recall that the mean squared error for an estimator $\hat{\theta}$ for a population parameter $\theta$ is simply $\text{MSE}(\hat{\theta}) = E[(\hat{\theta}-\theta)^2]$ and we can decompose this into $\text{MSE}(\hat{\theta}) = \text{Var}(\hat{\theta})+\text{Bias}(\hat{\theta})^2$ where $\text{Var}(\hat{\theta}) = E[\hat{\theta}^2]-E[\hat{\theta}]^2$ and $\text{Bias}(\hat{\theta}) = E[\hat{\theta}] - \theta$. This works because $E[\theta]$ and $E[\theta^2]$ are just (unknown) numbers. If the estimator is unbiased, then this bias term is 0 and the mean squared error is simply the variance. In a variety of situations, a biased estimator can be made unbiased simply by scalar multiplication by a well-chosen factor.

Time Series Data

19 minute read

Published:

A time series is a sequence of data points $(\vec{x}_1, y_1), (\vec{x}_2, y_2), \dots (\vec{x}_t, y_t) \dots$ where $\vec{x}_t$ represents a collection of $p$ features and $y_t$ represents a numeric variable of interest at time $t$. We often assume that our time steps are evenly spaced. Depending on the model and data set we may make additional assumptions on the $\vec{x}_t$ and $y_t$. It’s possible that we don’t actually have the $\vec{x}_t$ (which I will lazily just write as $x_t$ from now on). For example, we might just have $y_t$ which is a count of the number of sunspots observed on the sun at a given time $t$. We could also have, say, interest rates and inflation and we want to do predictions about inflation. So the interest rates are the features $x_t$ and inflation rates are $y_t$.

Basics of Linear Regression

22 minute read

Published:

These are notes I made while learning about the subject from my former colleague Victor Churchill’s lecture notes. Regression is a type of supervised learning that models the relationship between one or more independent variables (features) and a continuous dependent variable (target). The goal of regression is to predict the value of the dependent variable based on the values of the independent variables. The main example we look at here is linear regression.