# Book: YonedaLemma

Challenge: Understand Yoneda's lemma and relate it to the four levels of knowledge: Whether, What, How, Why.

Videos

Think through and write up

• How the properties of the Hom-functor yield Cayley's theorem.
• Alternatively, how the Yoneda lemma yields Cayley's theorem.
• What the Hom-functor means in the case of the Coxeter groups.

Study

• universality, representability, limits, adjunctions, Kan extensions

Questions

• Come up with simple examples of representable functors.
• Given a natural transformation A->B, what does that say about A and B?
• Consider how the form of Yoneda's lemma arises from the form of choices.
• Compare Yoneda's lemma with perspectives, their structure, and the equation of perspectives.
• Relate composition of perspectives with composition by extension and composition by clarification.
• Relate "implicit" and "explicit" with sets and paths and with composition by extension and by clarification.
• Explain how substitution of eigenvalues into symmetric functions can add information. And relate this to the Yoneda lemma where associativity adds information when we go from objects (node-variables) to morphisms (matrix edges).
• Consider the relation between things and actions (as with the natural numbers and addition) and where it shows up here, for example, in actions upon a set.
• What is the variant of Cayley's theorem that applies to the alphabet of letters i, i-bar, and yields Coxeter groups?
• Understand Yoneda's theorem as expressing the difference between God's external perspective (beyond system) and our internal perspective (within system) in four degrees: Whether, What, How, Why.
• How is it that Why is related to the inner structure rather than the external relationships?
• Does the Yoneda lemma presume the Axiom of Choice?

Preliminaries

Functors

• For any functor {$F$}, we have {$F_{id(X)}=id_{F(x)}$}. This is because for all morphisms {$h_{XX}$}:

{$$F(id_X)F(h_{XX}) = F(id_X h_{XX}) = F(h_{XX}) = F(h_{XX}id_X) = F(h_{XX})F(id_X)$$}

Hom-sets and Hom-functors

Given an object {$A$} of {$C$}, define the category {$\mathrm{Hom}(A,*)$} in terms of {$C$} as follows:

• An object is, for some {$X$} of {$C$}, the set {$\mathrm{Hom}(A,X)$} of arrows {$A\overset{*}{\rightarrow}X$}. Note that the initial {$A$} is the same across the entire category, but the final {$X$} is specific to the object.
• An arrow is, for some {$g:X\rightarrow Y$} of {$C$}, a set function {$\mathrm{Hom}(A,–)(g)$} from {$\mathrm{Hom}(A,X)$} to {$\mathrm{Hom}(A,Y)$} which takes an element {$A\overset{h}{\rightarrow}X$} and sends it to the element {$A\overset{h}{\rightarrow}X\overset{g}{\rightarrow}Y$}.
• Given {$X\overset{f}\rightarrow Y$} and {$Y\overset{g}\rightarrow Z$} of {$C$}, composition of {$\mathrm{Hom}(A,–)(f)$} and {$\mathrm{Hom}(A,–)(g)$} yields the set function {$\mathrm{Hom}(A,–)(fg)$} which maps element {$A\overset{h}{\rightarrow}X$} to {$A\overset{h}{\rightarrow}X\overset{f}{\rightarrow}Y\overset{g}{\rightarrow}Z$} and thus clarifies {$g$} by {$f$}.

Extension extends a path with regard to what is outside. Clarification clarifies the inside of the path.

Given an object {$A$} of {$C$}, define the hom-functor {$h^A = \mathrm{Hom}(A,–)$} from {$C$} to {$\mathrm{Set}$}.

• An object {$X$} of {$C$} is sent to {$\mathrm{Hom}(A,X)$}.
• An arrow {$X\overset{f}{\rightarrow}Y$} is sent to the set function {$\mathrm{Hom}(A,–)(f)$}.
• The composition of {$X\overset{f}{\rightarrow}Y$} and {$Y\overset{g}{\rightarrow}Z$} to yield {$X\overset{gf}{\rightarrow}Z$} (where {$g$} extends {$f$}) is sent to the composition of set functions {$\mathrm{Hom}(A,–)(fg)$} which sends an arrow {$A\overset{h}{\rightarrow}X$} to the arrow {$A\overset{h}{\rightarrow}X\overset{f}{\rightarrow}Y\overset{g}{\rightarrow}Z$} (so that {$f$} clarifies {$g$}).

Thus the extension of the ends of paths in {$C$} is mapped to the clarification of the starts of paths in {$\mathrm{Hom}(A,*)$}. An example of this is working backwards in trying to prove a statement true or false.

This describes a sort of duality. If there Exists a path {$g$} that extends path {$f$}, then for All paths that end in {$g$} there will exist those that pass directly from {$f$}.

Consider, for example, natural numbers with the arrows given by addition. Let A be the Zero.

Yoneda Lemma - Statement

{$\mathrm{Hom}(B,C) \leftrightarrow \mathrm{Nat}((C\rightarrow\_),(B\rightarrow\_))$}

{$(\mathrm{How}\rightarrow\mathrm{What}) \rightarrow \mathrm{Nat}((\mathrm{What}\rightarrow\_),(\mathrm{How}\rightarrow\_))$}

Let {$F$} be an arbitrary functor from {$C$} to Set.

Yoneda's lemma says that: For each object {$A$} of {$C$}, the natural transformations from {$h^A$} to {$F$} are in one-to-one correspondence with the elements of {$F(A)$}. That is,

{${Nat} (h^{A},F)\cong F(A)$}

Moreover this isomorphism is natural in A and F when both sides are regarded as functors from SetC x C to Set.

Meaning

Check: This means that paths which start from A, composed by "clarification", are transformed into set functions that start on the element {$\eta(id_A) \in F(A)$} and proceed by "set function composition".

• The Yoneda Lemma asserts that {$C^{op}$} embeds in {${\textbf{Set}}^C$} as a full subcategory.
• In other words, every category embeds in a functor category.
• The functor category {$D^C$} has as objects the functors from C to D and as morphisms the natural transformations of such functors. The Yoneda lemma describes representable functors in functor categories.

Argument

Core of the argument

Given functors {$H:C\rightarrow\mathrm{Set}$} and {$F:C\rightarrow\mathrm{Set}$}, and natural transformation {$\eta:H\rightarrow F$}, then {$\eta_X:H(X)\rightarrow F(X)$} is a set function.

If the functor {$H=\mathrm{Hom}(X,–)$}, then the set {$H(X)=\mathrm{Hom}(X,X)$}. Any morphism {$h_{XX}:X\rightarrow X$} is inside this set: {$h_{XX}\in \mathrm{Hom}(X,X)$} (with composition by extension). But this morphism is also thought of outside as a set function {$\mathrm{Hom}(–,X)(h_{XX}):\mathrm{Hom}(X,X)\rightarrow \mathrm{Hom}(X,X)$} (with composition by clarification).

Consider what happens to the element {$id_X\in\mathrm{Hom}(X,X)$}. The following diagram must commute:

{$(F(h_{XX}))(\eta_X(id_X))=\eta_X(h_{XX}(id_X))$}

Composition by clarification deems that the set function {$h_{XX}(\mathrm{Hom}(X,X))$} outputs the subset of those morphisms in {$\mathrm{Hom}(X,X)$} which start with the morphism {$h_{XX}$} in {$C$}. In particular, this set function maps each morphism {$g_{XX}$} in {$C$} to the morphism {$h_{XX}g_{XX}$} in {$C$}.

Thus, in particular, the set function {$h_{XX}$} maps the elements {$h_{XX}(id_X)=h_{XX}$}. Here again the morphism {$h_{XX}$} is an element (in {$\mathrm{Hom}(X,X)$}) and also thought of as a map (as {$\mathrm{Hom}(–,X)(h_{XX})$} from {$\mathrm{Hom}(X,X)$} to itself). But then:

{$\eta_X(h_{XX})=(F(h_{XX}))(\eta_X(id_X))$}

This means that the values of the set function {$\eta_X$} are all determined by the element {$\eta_X(id_X)\in F(X)$}.

In particular, the identity morphism {$id_X$} is a distinct element of {$\mathrm{Hom}(X,X)$} with composition by extension, and an omnipresent subpath in {$\mathrm{Hom}(\mathrm{Hom}(X,X),\mathrm{Hom}(X,X))$} with composition by clarification. In the first case, it is not implicit, but most be noted explicitly. In the second case, it is always implicit. Consequently, because of the first case, it gets represented by a specific element {$\eta_X(id_X)$}, and because of the second case, it is implicit in every represented path {$\eta_X(h_{XX})$}. Thus that specific element is the initial path in every compositional chain of set functions.

Application: Cayley's theorem

This case with a single object {$E$} in {$C$} is what is needed for Cayley's theorem. Let the morphisms {$E\overset{g}{\rightarrow}E$} be the elements of a group. Note that the group need not be finite.

First of all, Cayley's theorem is given by the fact that {$h^E=\mathrm{Hom}(E,–)$} is a functor.

• The set {$\mathrm{Hom}(E,E)$} is the set of group elements, the morphisms.
• The definition of the functor {$\mathrm{Hom}(E,–)$} shows that when it maps morphisms, it maps the group's elements to set functions from {$\mathrm{Hom}(E,E)$} to itself.
• In general, set functions do not form a group. However, permutations can form a group.
• The first fact to note that the functor {$h^E$} preserves group structure: identity element, inverses, associativity, closure.
• The functor maps the group's identity element {$e$} to the identity set function.
• The fact that inverses exist means that each group element gets mapped to a set function with an inverse. But this means that set function must be surjective and injective, thus a bijection, in other words, a permutation.
• The functor respects associativity and closure.
• The second fact to note is that the functor is injective. Suppose that the functor maps two group elements {$f$} and {$g$} to the same set function {$h^E(f)=h^E(g)$}. Then given a group element {$k{\in}\mathrm{Hom}(E,E)$}, we have {$fk=h^E(f)(k)=h^E(g)(k)=gk$}. But then {$f=fkk^{-1}=gkk^{-1}=g$}.
• Note here that it didn't matter which element {$k$} we used for this argument. The argument works for every {$k$}. That is an important fact that makes groups work and involves a set of conditions. The Yoneda Lemma expresses this internal fact about groups externally, from the categorial point of view, as a set of natural transformations. Thus the same set of conditions appears internally, in the group structure, as a set of equations that can be solved (dividing by k), and externally, in the categorical relations, as a set of actions that can be performed (multiplying by k).

Thus we conclude that {$h^E$} maps group elements to permutations, preserves the group structure, and is injective. Thus the group is embedded in the group of permutations on the elements of the group.

The Yoneda Lemma provides the following perspective on Cayley's theorem.

• Note that we have a natural transformation from the functor {$\mathrm{Hom}_C(–,*)$} to itself, and that the only object in C is {$*$}, thus all four corners of the commutative diagram are the same: {$\mathrm{Hom}_C(*,*)$}, which is the set of group elements. Then we can consider what happens to any element of that set.

More generally

The general case with many objects is not much more complicated. Again, the main idea is that the morphism {$g_{YX}$} is an element (in {$\mathrm{Hom}(X,Y)$}) and also thought of as a map (as {$\mathrm{Hom}(–,X)(g_{XY}^{op})$} from {$\mathrm{Hom}(X,X)$} to {$\mathrm{Hom}(Y,X)$}). Observations

• The notation Hom(X,Y) seems to be ambiguous given that we're working with both C and Cop.
• Hom(A,–) gives the perspectives from A, including perspectives on perspectives.
• F(A) is a set of labels.
• If F is the empty functor, or if F(A) is empty, then there are no natural transformations.

Conceptual ideas

Key points:

• Function composition elementwise mirrors (in the opposite direction) function composition setwise.
• Every object has a morphism to itself.
• Every set function has at least one element in its range.
• Functors take us from more refined (fewer relations, more equivalence classes) to less refined (more relations, fewer equivalence classes). This is counter to the representation of the twosome which takes us from "same" to "different".
• What is left unspoken: Sets are labeled - elements are labels. Categories are unlabelled only structure. Is this related to model theory?
• The properties of an entity correspond to the analogous stances: "This is the essence of the entity, the property that makes it what it is."
• A natural transformation equals a commutative diagram.

Foursome: Whether, What, How, Why

The Yoneda Lemma seems to relate the following levels of knowledge:

• A functor F takes us from a category C [How] (especially the morphisms) to a category F(C) [What] (especially the objects).
• [Whether] describes the external relationships in F(C). (The categorical outlook.)
• [Why] describes the internal structure native to C.

Relate to ways of figuring things out:

• Whether: level and metalevel are equated: proof by contradiction
• What: model
• How: working backwards
• Why: variables

Why expresses taking a stand with regard to everything. And so it is related to taking a stand with regard to one's self, what permeates one's inside entirely, as with a group's internal consistency, whereby each element multiplies to yield a distinct products. So consider how Why comes from one's (universal) relationship with one's self. All four levels (Whether, What, How, Why) express one's relationships with one's self, and the implications.

Note that a Turing machine is built on different kinds of variables, which may imply that it can't be categorified.

• Whether: object A (Accordion)
• What: image F(A)
• How: morphism from A: A->
• Why: all morphisms to A: ->A
• What: Target category. Set of properties. Why: Set of relationships as dictaded by its relationships but especially its relationship with itself (its essence).
• How: Source category. The source category of a functor is a model or blueprint for the target category of a functor.

Yoneda embedding: What=Why defines "meaning". What about other five qualities of signs?

A perspective is defined as a fixed point, namely, the identity morphism, with which we identify ourselves. This is Whether. It is the heart of the Yoneda theorem.

Duality

• Consider the Yoneda Lemma as the duality of set functions and Hom Set maps. Set functions are one-directional. In what sense are Hom Set maps one-directional? And is that duality natural? And what does it mean to have a "natural" duality?
• Consider the Yoneda Lemma as a duality between the conscious mind's questions and the unconscious mind's answers. The assembled questions and the assembled answers can be compared. I can compare this with my own sets of questions and sets of answers in my research. They may group themselves by divisions of everything.

Permutations and Matrices

Consider the duality between permutations/numbers/sets and matrices/vectors/lists/finite-automata.

Permutations are a group. And a group can be thought of as a single object with many relations to itself given by its elements. Whereas a matrix is the diagram of a category and describes relations between many distinct objects.

There is a map between permutations and matrices. How do we think of permutations when the group is described in terms of a single object? It seems then the permutations are described by structure within the group? What does Cayley's theorem say? And the Yoneda lemma?

In the case of a finite automata, we can think of it as a set of states linked by steps where a functor then maps each step (each morphism) to a letter (or word) in an alphabet. That functor thus maps all of the objects to a single object, thus a group. And we look at those paths that start at a start object and end at a final object. (How might they relate to initial and terminal objects?)

A group can be thought of as a single object with the elements as morphisms from it and to it. The identity element is the identity morphism. The actions come in pairs, doing and undoing, yielding the identity morphism. (Under what circumstances is there a canonical way to divide the pairs into "positive" and "negative"?) What makes the actions distinct? A symmetry group requires two points of view, level and metalevel, by which things can be "the same" and yet also "different".

Notes

• B_>C ..... How->What
• External relations -> Internal logic .... (Not What=Why) Hom C -> Hom B (Not How=Whether)
• What does the Yoneda Lemma say concretely about the category of Graphs, Groups, Lists, etc.?
• What would the category of Lists look like? And what would the Yoneda Lemma look like if the functor mapped into the category of Lists?
• Analyze the commutative diagram proving the Yoneda lemma by thinking it, on the one level, as a statement about four sets, but on another level, as a statement about functors and a natural transformation between them. Is there an ambiguity here?
• Eduardo's Yoneda Lemma diagram is the foursome.
• Loss of info from How to What is equal to the Loss of info from "Why for What" to "Why for How".
• How: inner logic. What: external view.
• Yoneda lemma - relates to exponentiation and logarithm
• Category is a collection of examples that satisfy certain conditions. That is why you can have many examples that are essentially identical. And it's essential for the meaning of the Yoneda Lemma, for example. Because two different examples may have the same structure but one example may draw richer meaning from one domain and the other may not have that richer meaning or may have other meaning from another domain.
• Whether (objects), what (morphisms), how (functors), why (natural transformations). Important for defining the same thing, equivalence. If they satisfy the same reason why, then they are the same.
• Representable functors - based on arrows from the same object.
• Is Cayley's theorem (Yoneda lemma) a contentless theorem? What makes a theorem useful as a tool for discoveries?
• Show why there is no n-category theory because it folds up into the foursome.
• Understand the Yoneda lemma. Relate it to the four ways of looking at a triangle.
• The Yoneda Lemma: the Why of the external relationships leads to the Whether of the objects in the set. The latter are considered as a set of truth statements.
• Executing an entire subroutine is in addition to executing individual steps. It is the use of a new parser at a second level. What would it mean on a further level?
• Moving from How (arrows) to What (objects).
• The movement of time: where the entire system moves forwards in that the final state becomes a new initial state. Whereas the other perspective you can have an opposite category.
• How does the "null activity" relate to the "do nothing action"?
• In the Yoneda lemma, the natural transformation on the left hand side seems to coordinate vertical and horizontal composition.
• The crucial point of the Yoneda lemma is that the set function is on an object A and not on a morphism.
• The four levels Whether, What, How, Why differ in how they focus on objects or morphisms.
• alpha theta Hom(f,_) takes as input the entire morphism: what value it goes to X and where that goes to in Y
• Does the Yoneda lemma suppose commutativity of summation? as with multiplication?
• Yoneda Lemma: Acting on the identity is acting on doing nothing. God as a mirror. The limits of my mind. The divisions of everything. What would the foursome look like as actions taking place on doing nothing, on the nullsome? Or is it the fact that the foursome is consciousness of the onesome?
• Functors from C to Set include many forgetful functors, such as from Group to Set. The functor C(c,_) from C to Set reduces the object d to a set of the arrows from c to d. It reduces an arrow f:a to b to a set function from (c,a) to (c,b). Every functor is about forgetting, and the least forgetful functor is simply an isomorphism. But the category Set has very little explicit information, so in some sense it is the space of greatest forgetting, it is a blank slate.
• Yoneda lemma models determinism: If you know where the root of the tree goes, then you know where everything goes.
• The left side of the Yoneda lemma relates the concepts of forgetful and free.
• Math Stack Exchange: Basic example of Yoneda lemma mentions subroutines.
• 维基百科: Continuation passing style: CPS transform is conceptually a Yoneda embedding.
• Bartosz Milewski. The Yoneda Lemma.
• Bartosz Milewski. Yoneda Embedding.
• [https://www.cs.ox.ac.uk/jeremy.gibbons/publications/proyo.pdf | What You Needa Know about Yoneda. Profunctor Optics and the Yoneda Lemma. (Functional Pearl)]] Guillaume Boisseau, Jeremy Gibbons. Mention the preorder example as proofs by indirect equality.
• Category theory notes 16: Yoneda lemma (Part 3) Linguist Chenchen (Julio) Song works through the details in his own way.
• Yoneda lemma: A set of actions becomes an object.
• Yoneda lemma: A natural transformation F->G splits a morphism=computation f in C into two perspectives: the execution F(f) and the outcomes G(f).
• "Does nothing" means that it has never has any effect on other actions upon composition with them. An action does something if it takes one action into another action. (Not whether it takes an object into another object.) Thus actions are maps on actions.
• Yoneda Lemma expresses the "symmetry group" at the heart of the ways of figuring things out in math. This relates a system and a pre-system. Thus it sets up the point where the pre-system becomes a system (a subsystem). And it can do this by distinguishing objects - those identity morphisms that do nothing - they get segregated into the subsystem and understood as such.
• Yoneda Lemma explains what happens in the gap between consciousness and the unconscious, the tipping point at which the conscious gets dealt with, one way or another.
• Analyze the Yoneda Lemma in terms of the arithmetical hierarchy. Express its statements in terms of existential and universal quantifiers.

Natural transformation has four levels:

• Why: f:x->y in C
• How: F(f):F(x)->F(y) in F(C)
• What: G(f):G(x)->G(y) in G(C)
• Whether: F(x)->G(y)

Objectification of morphisms

• center - whether - identity morphism
• balance - what - "from and to"
• set - how - *elements* in a set
• list - why - *list* of items

Are these all internal structures? But what about external relationships? Are they given by analysis?

• Procedural (imperative, top-down) - Fortran, C, Cobol. Statements are structured into procedures, subroutines, functions, they make procedure calls.
• Logical (declarative) - Prolog. Statements express facts (assertions), rules (inferences) and queries about problems within a system. Rules are logical clauses with a head and a body. Expresses knowledge independently of implementation. Knowledge separated from use. Programs can be more flexible, compressed, understandable.
• Functional - Haskell, Lisp. Computation is an evaluation of mathematical functions. Pure functions are those that take an argument list as input and output a return value. They do not depend on global data or class member's data. No side effects. Input not affected. A function can recursively call itself. Referentially transparent expressions can be replaced by their value without changing the program's behavior. Functions are first-class, they can be treated as any other variable: they can be used as input, returned as output, or be assigned to a variable. Variables are immutable, they can't be modified after initialization.
• Object-oriented - Ruby, Java, C++, Python. Real world entities are represented by Classes. Objects are instances of classes such that each object encapsulates a state (fields, attributes) and behavior (methods, what you do with the object). Objects interact with each other by passing messages.
• Encapsulation: Classes bundle the data and methods, hide the internal representation, and provide a simple and clear interface.
• Inheritance: A hierarchy of classes by which one class derives from another class.
• Data abstraction: Interface shows essential information, hides details.
• Polymorphism: A variable, function or object may take on multiple forms.
• In a category, if two objects have morphisms into each other, than they are isomorphic. So if we are only interested in nonisomorphic objects, then we can consider equivalence classes. And we can see that the maps only go in one way, so they are naturally partially ordered.
• Functors have an ambiguity - they are morphisms (simple, external) but they also have rich internal structure. In a sense, every morphism has this ambiguity, more or less.
• Isomorphism of C and D consists of four facts: a morphism f from C to D, and a morphism g from D to C, and and the fact that fg = 1_C and gf = 1_D.
• In category theory, how do we distinguish cardinalities? How can we distinguish countable and second countable?
• The identity morphism falls out as a special morphism among the possible morphisms from B to B. It is the basis for Graziano's awareness schema.
• So the identity morphism, which seemed optional or arbitary, become absolutely essential. The reason it becomes essential is because of its role in composition. And composition makes sense when you have a set of morphisms from B to B and if you know them all then you know How they compose. But to really make sense of it you need to be able to think in terms of the equivalences, the possibilities for external objects with morphisms too and from them. So Why requires the notion of objects which seemed superfluous. And the idea that there are Other objects, not just B. This gives meaning to the identity morphism, which distinguishes B from the others.

Relate Yoneda Lemma to this logical tautology: {$(P \Rightarrow Q) \Rightarrow R) \Rightarrow ((P \Rightarrow Q) \Rightarrow (P \Rightarrow R))$}

Parsiųstas iš http://www.ms.lt/sodas/Book/YonedaLemma
Puslapis paskutinį kartą pakeistas 2020 gegužės 19 d., 14:45