Iš Gvildenu svetainės

Book: YonedaLemma

See: Math notebook, Category theory, Understanding Yoneda Lemma, Learning Yoneda Lemma, Yoneda Lemma ideas, Walks

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

米田引理 Lema de Yoneda

Read about the Yoneda lemma:


Think through and write up





{$$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:

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}$}.

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.


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".


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:


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:


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.

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.

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)$}).


Conceptual ideas

Key points:

Foursome: Whether, What, How, Why

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

Relate to ways of figuring things out:

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.

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.


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".


Natural transformation has four levels:

Objectification of morphisms

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

Four programming paradigms:

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