yoneda.tex

\documentclass[10pt,letterpaper]{article}
\DeclareSymbolFont{AMSb}{U}{msb}{m}{n}
\DeclareMathAlphabet{\mathbbm}{U}{bbm}{m}{n}

\usepackage{amsmath,amssymb,amsthm,latexsym}
\usepackage{fancyhdr}
\usepackage[tiny,center,compact,sc]{titlesec}
\usepackage[cm]{fullpage}
\usepackage{pstricks}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{bm}
\usepackage{ifthen}
\usepackage{epsfig}
\usepackage[all]{xypic}
\usepackage{textcomp}
\usepackage{url}
\usepackage{multirow}
\usepackage{hyperref}
\usepackage{breakurl}

\renewcommand{\baselinestretch}{0.9}

%\newtheorem{thm}{Thm}[section]
%\newtheorem{dfn}{Def}[section]

\setlength{\parindent}{0pt}
\setlength{\parskip}{3pt}

%Scalable bracket-like
\newcommand{\paren}[1]{\left({#1}\right)}
\newcommand{\brak}[1]{\left[{#1}\right]}
\newcommand{\abs}[1]{\left\lvert{#1}\right\rvert}
\newcommand{\ang}[1]{\left\langle{#1}\right\rangle}
\newcommand{\set}[1]{\left\{#1\right\}}

%Mathematics
\newcommand{\condexp}[1]{\ifthenelse{\equal{#1}{false}}{}{^{#1}}}
\newcommand{\dd}[3][false]{\frac{d\condexp{#1}{#2}}{d{#3}\condexp{#1}}}
\newcommand{\pd}[3][false]{\frac{\partial\condexp{#1}{#2}}{\partial{#3}\condexp{#1}}}

\newcommand{\ifrac}[2]{{#1}/{#2}}

%Quantum Mechanics
\newcommand{\ket}[1]{\left\lvert{#1}\right\rangle}
\newcommand{\bra}[1]{\left\langle{#1}\right\rvert}
\newcommand{\braket}[2]{\left\langle{#1}\middle\vert{#2}\right\rangle}
\newcommand{\Braket}[3]{\left\langle{#1}\middle\vert{#2}\middle\vert{#3}\right\rangle}
\newcommand{\dyad}[2]{\left\lvert{#1}\middle\rangle\middle\langle{#2}\right\rvert}

\DeclareMathOperator{\mm}{\mid\mid}

\newcommand{\defn}[1]{{\bf #1}}

\begin{document}

\section{Covariant Hom functors}

These are defined in \S3.20.4, but a longer example never hurt anybody, right?

Suppose $a^2 = id_A$, $b^2 = id_{B'}$, and $f' = g \circ f$ in this category $\mathbf{A}$.
\[ \xymatrix@C=1in{
                                                           & B \ar[d]^g \ar@(dr,ur)_{id_B} \\
  A \ar@(dr,d)^{id_A} \ar@(dl,l)^{a} \ar[ru]^f \ar[r]^{f'} & B' \ar@(dl,d)_{b} \ar@(dr,r)_{id_{B'}} \\
  } \]

If we actually draw out all the arrows, we get this diagram:
\[ \xymatrix@C=1in{
     & B \ar@<1pt>[d]_{b \circ g} \ar@<-1pt>[d]^g  \ar@(dr,ur)_{id_B} \\
  A \ar@(dr,d)^{id_A} \ar@(dl,l)^{a}
    \ar@<1pt>[ru]^f \ar@<-1pt>[ru]_{f \circ a}
    \ar@<3pt>[r] \ar@<1pt>[r] \ar@<-1pt>[r] \ar@<-3pt>[r]
     & B' \ar@(dl,d)_{b} \ar@(dr,r)_{id_{B'}} \\
  } \]
where the four arrows from $A$ to $B'$ are $\set{f', f' \circ a, b \circ f', b \circ f' \circ a}$.

$\mbox{hom}(A,-)$ is the following full subcategory of $\mathbf{Set}$; please
note the similarities---the {\em representation} of the structure reachable from $A$:
\[ \xymatrix@C=1in{
    & \set{f, f \circ a} \ar@<1pt>[d] \ar@<-1pt>[d] \\
  \set{id_A, a} \ar@<1pt>[ru] \ar@<-1pt>[ru]
                \ar@<3pt>[r] \ar@<1pt>[r] \ar@<-1pt>[r] \ar@<-3pt>[r]
    & \txt{$\{f', f' \circ a,$\\ $b \circ f', b \circ f' \circ a\}$} \\
} \]
The two arrows from $\mbox{hom}(A,A) = \set{id_A, a}$ to $\mbox{hom}(A,B)
= \set{f, f \circ a}$ are obtained by post-composition:
\begin{align*}
  \mbox{hom}(A,f) &= \set{ id_A \mapsto f, a \mapsto f \circ a } \\
  \mbox{hom}(A,f \circ a) &= \set{ id_a \mapsto f \circ a, a \mapsto f }
\end{align*}
(the last entry holds because $(f \circ a) \circ a = f \circ (a \circ a) = f
\circ id_A = f$).  The four arrows from $\mbox{hom}(A,A)$ to
$\mbox{hom}(A,B') = \set{f', f' \circ a, b \circ f', b \circ f' \circ a}$ are
again obtained by post-composition:
\begin{align*}
  \mbox{hom}(A,f') &= \set{id_A \mapsto f', a \mapsto f' \circ a} \\
  \mbox{hom}(A,f' \circ a) &= \set{id_a \mapsto f' \circ a, a \mapsto f'} \\
  \mbox{hom}(A,b \circ f') &= \set{id_a \mapsto b \circ f', a \mapsto b \circ f' \circ a} \\
  \mbox{hom}(A,b \circ f' \circ a) &= \set{id_a \mapsto b \circ f' \circ a, a \mapsto b \circ f'}
\end{align*}
The two vertical arrows are (again by post-composition, and recall that $f' = g \circ f$):
\begin{align*}
  \mbox{hom}(A,g) &= \set{f \mapsto f', f \circ a \mapsto f' \circ a} \\
  \mbox{hom}(A,b \circ g) &= \set{f \mapsto b \circ f', f \circ a \mapsto b \circ f' \circ a}
\end{align*}
It is easy to check that, indeed, composition still holds: the four horizontal
arrows are each the result of composition of a choice of vertical and diagonal arrows,
and we haven't missed any.

\pagebreak
\section{Proposition 6.18 and The Yoneda Lemma}

Let's restrict our attention to this category $\mathbf{A}$
(to truly appreciate the significance of this result, I encourage you to work out
the details in full for a slightly larger category!):
\[ \xymatrix{ A \ar[r]^f & B } \]

The image of this in $\mathbf{Set}$ under $\mbox{hom}(A,-)$ is just
\[ \xymatrix@C=.5in{ \set{id_A} \ar[r]^{\mbox{hom}(A,f)} & \set{f} } \]

Now suppose we have some other functor $F : \mathbf{A} \to \mathbf{Set}$,
whose image is
\[ \xymatrix@C=.5in{ \set{a_0, \dots} \ar[r]^{Ff} & \set{b_0, \dots} } \]
(where $FA = \set{a_0, \dots}$ and $FB = \set{b_0, \dots}$.)

Now, the claim of Proposition 6.18 is that there exists a unique natural
transformation $\tau : \mbox{hom}(A,-) \stackrel{\cdot}{\to} F$ if we additionally
constrain $\tau_A(id_A) = a_0$.  OK, so, first off: what does that mean? $\tau$ being
natural means $\forall B,C,g : B \to C$, this commutes:
\[ \xymatrix{
  \mbox{hom}(A,B) \ar[r]^{\tau_B} \ar[d]_{\mbox{hom}(A,g)} & FB \ar[d]^{Fg} \\
  \mbox{hom}(A,C) \ar[r]^{\tau_C} & FC 
} \]
or more specifically, at $A,B,f$ (first generically, then expanding some computations):
\[ \xymatrix{
  \mbox{hom}(A,A) \ar[r]^{\tau_A} \ar[d]_{\mbox{hom}(A,f)} & FA \ar[d]^{Ff} \\
  \mbox{hom}(A,B) \ar[r]^{\tau_B} & FB 
} \qquad \xymatrix{
  \set{id_A} \ar[r]^{\tau_A} \ar[d]_{\set{id_A \mapsto f}} & \set{a_0,\dots} \ar[d]^{Ff} \\
  \set{f} \ar[r]^{\tau_B} & \set{b_0,\dots}
} \]
and so requiring $\tau_A(id_A) = a_0$ makes sense.  If this is to be natural, it
must be the case (for all $B$ and $f : A \to B$; note that this works even to
define $\tau_A$ at inputs other than $id_A$ just as well!) that
\begin{align*}
  \tau_B(f) &= \tau_B(f \circ id_A) \\
            &= \tau_B(\mbox{hom}(A,f)(id_A)) & \forall_x . f \circ x = \mbox{hom}(A,f)(x) \\
            &= F(f)(\tau_A(id_A))            & \text{naturality of $\tau$} \\
            &= F(f)(a_0)                     & \text{requirement}
\end{align*}
So $\tau$ is fully determined by naturality and the requirement given,
precisely because $\mbox{hom}(A,-)$ on arrows captures post-composition.
So: given a choice of $a_0 \in FA$, we can fully specify a natural transformation $\tau$.


Conversely, given a $\tau'$, it must pick out some $\tau_A(id_A) \in FA$.  Therefore,
the Yoneda lemma:

\begin{quote}{\em
  Given a functor $F : \mathbf{A} \to \mathbf{Set}$, the set
  $\set{\tau \middle\vert \tau : \mbox{hom}(A,-) \stackrel{\cdot}{\to} F}$
  is isomorphic (in $\mathbf{Set}$) to $FA$.
  The isomorphism is witnessed by the function $Y(\tau) = \tau_A(id_A)$.
}\end{quote}

\end{document}