Exercises 3: Graph and Yoneda Lemma

EX 1: The Yoneda Lemma

\[Gr = 𝒢 ≝ \begin{xy} \xymatrix{ \ast \ar@/^/[d]^t \ar@/_/[d]_s \\ \ast } \end{xy}\] \[\hat{𝒞} = Set^𝒞\]

1.

\[Y_0 = (\lbrace e \rbrace, ∅)\]

A graph homorphism from $Y_0$ to $G = (V, E)$ corresponds to picking a vertex in $G$, and conversely any such vertex defines a morphism from $Y_0$ to $G$.

One defines the graph

\[Y_1 ≝ v_1 \overset{f}{⟶} v_2\]

Similarly, a graph homorphism from $Y_1$ to $G = (V, E)$ corresponds to picking an edge in $G$, and conversely any edge defines a morphism from $Y_1$ to $G$.

2.

We want to construct a functor

\[Y: \begin{cases} 𝒢 ⟶ \hat{𝒢} = \text{Graphs} \\ 0 ⟼ Y_0 \\ 1 ⟼ Y_1 \end{cases}\]

but for any category $𝒞$, now.

The Yoneda functor:

\[Y: \begin{cases} 𝒞 ⟶ \hat{𝒞} ≝ Set^{𝒞^{op}} \\ A ⟼ 𝒞(\_, A) \end{cases}\]

3.

With \(𝒞 = Gr ≝ \begin{xy} \xymatrix{ 0 \ar@/^/[d]^t \ar@/_/[d]_s \\ 1 } \end{xy}\)

If $G ∈ \hat{𝒢}$ is a graph with

• $G_0$ as vertices
• $G_1$ as edges
• $G_s$ as source function
• $G_t$ as target function

With the Yoneda functor:

• $Y(0)$:

  • vertices: $Y(0)(0) = 𝒞(0, 0) = \lbrace id_0 \rbrace$
  • edges: $Y(0)(1) = 𝒞(1, 0) = ∅$

• $Y(1)$:

  • vertices: $Y(1)(0) = 𝒞(0, 1) = \lbrace s, t \rbrace$
  • edges: $Y(1)(1) = 𝒞(1, 1) = \lbrace id_1 \rbrace$

• source of $id_1$: $Y1s(id_1) = id_1 \circ s = s$

• source of $id_1$: $Y1t(id_1) = id_1 \circ t = t$

4.

\[\begin{cases} \hat{𝒞}(YA, P) &≃ P(A) \\ θ &⟼ θ_A(id_A) \end{cases}\]

and

\[\begin{cases} P(A) &≃ \hat{𝒞}(YA, P) \\ x &⟼ θ \text{ defined by } θ_B(f) = Pf(x) \end{cases}\]

5.

$Y: 𝒞 ⟶ \hat{𝒞}$ is full and faithful: for all $A, B∈𝒞$,

\[\hat{𝒞}(YA, YB) ≃ YBA = 𝒞(A, B)\]

by the Yoenda lemma