Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

January 25, 2008

The Yoneda Embedding as a Reflection

Posted by John Baez

Guest post by Mike Stay

In my last post I explained how the Yoneda embedding was secretly the same as the ‘continuation passing transform’. Here’s a nice pictorial way to think about it.

We can write any expression like f(g(x,y))f(g(x,y)) as a full binary tree where the nodes denote evaluation of the left child at the right, and the leaves are values:

(1) ev ↙ ↘ f ev ↙ ↘ ev y ↙ ↘ g x\array{&&ev\\&\swarrow&&\searrow\\f&&&&ev\\&&&\swarrow&&\searrow\\&&ev&&&&y\\&\swarrow&&\searrow\\g&&&&x}
(2)Figure1:f(g(x)(y))Figure 1: f(g(x)(y))

[In the caption of figure 1, the expression is slightly different; when using trees, it’s more convenient to curry all the functions—that is, replace every comma “,” by back-to-back parens: “)(” .]

The continuation passing transform (Yoneda embedding) first reflects the tree across the vertical axis and then replaces the root and all the left children with their continuized form—a value xx gets replaced with a function value x¯=(f↦f(x)):\overline{x} = (f \mapsto f(x)):

(3) ev¯ ↙ ↘ ev¯ f ↙ ↘ y¯ ev ↙ ↘ x¯ g\array{&&&&\overline{ev}\\&&&\swarrow&&\searrow\\&&\overline{ev}&&&&f\\&\swarrow&&\searrow\\\overline{y}&&&&ev\\&&&\swarrow&&\searrow\\&&\overline{x}&&&&g}
(4)Figure2:y¯(x¯(g))¯(f)¯Figure 2: \overline{\overline{ \overline{y}(\overline{x}(g)) } (f)}

What does this evaluate to? Well,

(5) y¯(x¯(g))¯(f)¯ = f(y¯(x¯(g)))¯ = f(x¯(g)(y))¯ = f(g(x)(y))¯\array{ & \overline{\overline{ \overline{y}(\overline{x}(g)) } (f) }\\ = & \overline{f(\overline{y}(\overline{x}(g)))} \\ = & \overline{f(\overline{x}(g)(y))} \\ = & \overline{f(g(x)(y))} }

As we hoped, it’s the continuization (Yoneda embedding) of the original expression. Iterating, we get

(6) ev¯¯ ↙ ↘ f¯ ev¯ ↙ ↘ ev¯ y¯ ↙ ↘ g¯ x¯\array{&&\overline{\overline{ev}}\\&\swarrow&&\searrow\\\overline{f}&&&&\overline{ev}\\&&&\swarrow&&\searrow\\&&\overline{ev}&&&&\overline{y}\\&\swarrow&&\searrow\\\overline{g}&&&&\overline{x}}
(7)Figure3:f¯(g¯(x¯)¯(y¯)¯)¯¯Figure 3: \overline{\overline{\overline{f}\left(\overline{\overline{\overline{g}\left(\overline{x}\right)}\left(\overline{y}\right)}\right)}}

At this point, we get an enormous simplification: we can get rid of overlines whenever the left and right branch both have them. For instance,

(8)g¯(x¯)=x¯(g)=g(x).\overline{g}(\overline{x}) = \overline{x}(g) = g(x).

Actually working out the whole expression would mean lots of epicycular reductions like this one, but taking the shortcut, we just get rid of all the lines except at the root. That means that we end up with

(9)f(g(x)(y))¯¯\overline{\overline{f(g(x)(y))}}

for our final expression. However, if this expression is just part of a larger one—if what we’re calling the “root” is really the child of some other node—then the cancellation of lines on siblings applies to our “root” and its sibling, and we really do get back to where we started!

Posted at January 25, 2008 11:36 PM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/1580



14 Comments & 0 Trackbacks

Re: The Yoneda Embedding as a Reflection

I like that. When I was young and even more naive than I am now, I wrote a Java program which handled trees like that, built from spans like that, whose top would be either

ev \mathrm{ev}

or

λ \lambda

So, for instance, λx.f(x)\lambda x . f(x) would have corresponded to

λ ↙ ↘ x ev ↙ ↘ f x. \array{ && \lambda \\ & \swarrow && \searrow \\ x &&&& \mathrm{ev} \\ &&& \swarrow && \searrow \\ && f &&&& x } \,.

I believe I didn’t get anywhere much further with this idea, because looking at this picture made me want to understand what it would mean to have compound expressions on the left leg of a λ\lambda-tree. I wanted to get a notion of invertibility into the game this way, but failed horribly.

Posted by: Urs Schreiber on January 28, 2008 2:32 PM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

I did something very much like that in my binary encoding of lambda calculus that I called “Keraia.” It’s described in chapter 1 of my master’s thesis.

Keraia has two combinators, named 0 and 1. ’ is a prefix application operator a la Unlambda.

(1)F→FB | ′[F][B] F→ϵ | [0] B→0 | λc′cInterpret B→1 | λcλA′AλaλB′Bλb′c′′Pairab \array{ F \to F B & | & '[F][B] \\ F \to \epsilon & | & [0] \\ B \to 0 & | & \lambda c\quad 'c \quad Interpret \\ B \to 1 & | & \lambda c \quad \lambda A \quad 'A \quad \lambda a \quad \lambda B \quad 'B \quad \lambda b \quad 'c \quad ' 'Pair \quad a \quad b}

The empty string at the start of a program invokes an interpreter on the binary tree data structure constructed by the 1s. It’s at least possible under this to reflect the tree, but it doesn’t give anything very useful. Interpreting the tree doesn’t even give the same result under alpha substitution.

So I agree that it doesn’t make much sense to reflect around a lambda.

Posted by: Mike Stay on January 28, 2008 8:13 PM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

So I agree that it doesn’t make much sense to reflect around a lambda.

There is a beautiful would-be interpretation of

λ ↙ ↘ ev x ↙ ↘ f x \array{ &&&& \lambda \\ &&& \swarrow && \searrow \\ && ev &&&& x \\ & \swarrow && \searrow \\ f &&&& x }

: a machine which reads in an argument, checks if it is of the form f(x)f(x) for some xx, and then spits out this xx.

So it’s the inverse of ff! Except, of course, that it isn’t. But then, maybe we are just not being clever enough in interpreting this. Maybe each xx should be read as a set of possible vales, so that the above machine would be the pre-image operation.

I don’t know. I never got anywhere with this. If you should ever do, let me know.

Posted by: Urs Schreiber on January 28, 2008 8:34 PM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

Hmm… That looks very much like the work of Abramsky (and Coecke?) on traced categories; I intended to getting around to understanding them after finishing this paper.

I think the idea is that if we have a morphism f:X→Yf:X\to Y in a compact monoidal closed category, then we also get f *:Y *→X *f^*:Y^* \to X^*. Given (f⊗g *):X⊗X *→Y⊗Y *(f\otimes g^*):X \otimes X^* \to Y \otimes Y^*, you can precompose with the cap and compose with the cup to get a scalar, related somehow to the trace.

I think what you drew is f *f^*.

Posted by: Mike Stay on January 28, 2008 10:15 PM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

What does the Yoneda embedding look like when applied to a string diagram? Composition is dual to tensor under the reflection of an application tree, so a diagram like

(1)x y z w ↘ ↓ ↙ ↓ f g ↘ ↙ h ↓ \array{x && y && z &&& w\\&\searrow&\downarrow&\swarrow&&&&\downarrow \\ &&f&&&&&g \\ &&&\searrow&&\swarrow \\ &&&&h \\ &&&& \downarrow}

becomes

(2) f ↓ x ↓ y h ↓ ↙ g z ↘ ↓ w ↓ \array{&&f\\&&\downarrow\\&&x\\&&\downarrow\\&&y&&h\\&&\downarrow&\swarrow\\g&&z\\&\searrow&\downarrow\\&&w\\&&\downarrow\\}

which doesn’t have an immediately obvious topological interpretation (aside from the tree reflection).

Posted by: Mike Stay on February 1, 2008 12:45 AM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

Aren’t you just saying that the evaluation of f at x is the evaluation of x at f?

Expressed slightly differently, ev (f, x) as a (heterogeneous) binary operator can be written as its (unique) converse cev (x, f).

But if that renders the Yoneda embedding trivial, then why on earth does category theory use such complicated constructions to get to that point?

Question: as a concrete example, what are the images of the Yoneda embeddings of the (linear) poset categories 0, 1, 2, 3, …, n ?

Posted by: Geoffrey Tobin on May 1, 2009 12:09 AM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

Please don’t blame category theory for the fact that Mike Stay is having fun playing around with it. The Yoneda embedding theorem is indeed trivial, but it doesn’t just say that f(x)f(x) can be rewritten as x(f)x(f). It says that you know everything there is to know about an object if you know everything about the morphisms into it. More precisely, you know everything about x∈Cx \in C if you know the functor hom(−,x):C op→Sethom(-,x) : C^{op} \to Set. More precisely, this trick provides a full and faithful embedding of any category CC into the category of functors from C opC^{op} to SetSet. This reduces to some other famous theorem when CC is a poset.

Posted by: John Baez on May 1, 2009 6:33 PM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

Point taken. I find Mike’s explanation much clearer and more direct than any of those by Saunders MacLane, Robert Goldblatt, Wikipedia, and the summary on Toby Bartels’ website.

But I still wonder why complicated explanations are given, requiring large quantities of background research?

Mac Lane and Lawvere claim that the purpose of category theory is to unify and simplify mathematics. By removing its insights to such a distance from other mathematical practitioners, let alone from the curious public, many presentations of category theory are achieving the very opposite of that aim.

When reduced to algebra, the category theory description of the Yoneda embedding boils down to the partial map of morphisms Y(f,g,h) = fgh, and the map of objects Y(a,b) = Hom(a,b).

If only to make the results meaningful to the non-specialist, why don’t accounts include a line or two stating (a precise but clear statement of) that?

Posted by: Geoffrey Tobin on June 8, 2009 4:29 AM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

I find Mike’s explanation much clearer and more direct than any of those by Saunders MacLane, Robert Goldblatt, Wikipedia, and the summary on Toby Bartels’ website.

Not to suggest that everything that I write is clear and direct, but I don't think that there is an explanation of the Yoneda Lemma on my website.

Posted by: Toby Bartels on June 9, 2009 2:24 AM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

Geoffrey wrote:

But I still wonder why complicated explanations are given, requiring large quantities of background research?

Most mathematicians are really lousy at explaining things in a way that’s clear to the largest possible audience — they either don’t care to do so, or they don’t know how. This is one reason most people hate math, and most mathematicians hate category theory (very similar phenomena).

If only to make the results meaningful to the non-specialist, why don’t accounts include a line or two stating (a precise but clear statement of) that?

If I ever write a book on category theory that explains the Yoneda embedding, of course I’ll say this!

Posted by: John Baez on June 8, 2009 5:01 AM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

I almost had a Eureka moment, but not quite. Just enough to tease me. I like this description. Maybe one day I’ll get it.

Posted by: Eric on June 8, 2009 5:50 AM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

“Eurek… huh??”

It’s ultimately very simple, Eric: to know an object is to know all the morphisms out of it.

Posted by: John Baez on June 8, 2009 11:17 PM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

That sounds very Zen, but don’t underestimate my ability to not understand simple things :)

The Yoneda embedding stuff is high on my list of things I want to understand. When I get to a point where I can spend the requisite minutes to think about it, I’ll likely ask some questions. I like your description though and it seems within the realm of possibility that I will be able to understand it.

Posted by: Eric on June 8, 2009 11:31 PM | Permalink | Reply to this

Re: The Yoneda Embedding as a Reflection

As you’re all talking about Yoneda, anyone have thoughts on my observation that it’s a 2-coalgebra for an endo-2-functor on CatCat?

Posted by: David Corfield on June 9, 2009 8:45 AM | Permalink | Reply to this

Post a New Comment