cats.tex

% !TEX TS-program = LuaLaTeX
% !TEX encoding = UTF-8 Unicode
\documentclass[a5paper,oneside,11pt]{article}
\usepackage[a5paper,margin=1.5cm]{geometry}
\usepackage[pdfusetitle]{hyperref}
%\usepackage{fontspec}
%\usepackage{unicode-math}
\usepackage{tikz-cd}
\usepackage{quiver}
\usetikzlibrary{cd}
\usepackage{float}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}

\title{Category theory notes and exercises}
\author{Tito Sacchi}

\newtheorem{ex}{Exercise}
\newtheorem{defn}{Definition}
\newtheorem{thm}{Theorem}
\newcommand\id{\mathord{\mathrm{id}}}
\newcommand\Id{\mathord{\mathrm{Id}}}
\newcommand\1{\mathord{\mathrm{1}}}
\newcommand\power[1]{\mathcal{P}(#1)}
\newcommand\cat[1]{\mathbf{#1}}
\newcommand\op{\mathrm{op}}
\newcommand\Hom[3]{\mathop{\mathsf{Hom}_{\cat{#1}}(#2, #3)}}
\newcommand\dom{\mathop{\mathsf{dom}}}
\newcommand\cod{\mathop{\mathsf{cod}}}
\newcommand\fcat[2]{[\cat{#1}, \cat{#2}]}
\font\maljapanese=dmjhira at 2.8ex
\newcommand\yo{\text{\maljapanese\char"47}\!}
\newcommand\coyo{\raisebox{-0.16em}{\rotatebox[origin=c]{180}{\text{\maljapanese\char"47}}}\!\!}
\begin{document}
\maketitle

\section{Categories and morphisms}
\begin{defn}
\label{defn:monoepi}
A morphism $f : X \rightarrow Y$ is:
\begin{itemize}
    \item a \textbf{monomorphism} if $ f \circ g_1 = f \circ g_2 \implies g_1 = g_2$
        for any $g_1, g_2 : W \rightarrow X$ (we write $f : A \rightarrowtail B$);
    \item a \textbf{epimorphism}  if $ g_1 \circ f = g_2 \circ f \implies g_1 = g_2$
        for any $g_1, g_2 : Y \rightarrow Z$ (we write $f : A \twoheadrightarrow B$);
    \item a \textbf{isomorphism} if there exists another morphism $f^{-1} : Y \rightarrow X$
        such that $f^{-1} \circ f = \id_X$ and $f \circ f^{-1} = \id_Y$ (we write $X \simeq Y$).
\end{itemize}
\end{defn}
\begin{defn}
\label{defn:split}
Two morphisms $s : X \rightarrow Y$ and $r : Y \rightarrow X$ such that
$r \circ s = \id_A$ express $B$ as a \textbf{retract} of $A$. $s$ is
a \textbf{split monomorphism} and a right inverse or section to $r$,
while r is a \textbf{split epimorphism} and a left inverse or retraction to $s$.
$s \circ r$ is a \textbf{split idempotent}.
\end{defn}

The axiom of choice states that every epimorphism in the category $\cat{Set}$ of
sets and functions is a split epimorphism.

\begin{ex}
    Prove that a morphism $f$ that is both a monomorphism and a split
    epimorphism is necessarily an isomorphism.
    Argue by duality that a split monomorphism that is an epimorphism is also
    an isomorphism.
\end{ex}
\begin{proof}
    Let $g$ be the section of $f$.
    $f \circ g = \id$ because $r$ is a split epi; therefore,
    $f \circ g \circ f = f \circ \id$.
    But we can apply the left cancellation law because $f$ is a mono: $g \circ f = \id$.
    $f$ and $g$ witness the existence of an isomorphism.
    The second argument follows by duality.
\end{proof}

\begin{ex}
    Show that a morphism $f : X \rightarrow Y$ is a split epimorphism in a category
    $\mathbf{C}$ if and only if for all $W \in \cat{C}$, the post-composition function
    $f_\star~:~\Hom{C}{W}{X} \rightarrow \Hom{C}{W}{Y}$ is surjective.

    By duality, a morphism $f : X \rightarrow Y$ is a split monomorphism iff
    for all $W \in \cat{C}$ the pre-composition function $f^\star$ is surjective.
\end{ex}
\begin{proof}
    Assume $f$ is a split epi and let $g : Y \rightarrowtail X$
    be the section of the splitting.
    We can assign to each $h : W \rightarrow Y$ the morphism
    $g \circ h : W \rightarrow X$ which is a preimage of $h$ under $f_\star$ because
    $f \circ g \circ h = \id \circ h = h$.

    Now, assume that $f_\star$ is surjective.
    Let $g : Y \rightarrow X$ be the preimage of $\id_Y$ under $f_\star$:
    therefore $f$ and $g$ witness a splitting that expresses $X$ as a retract of $Y$,
    with $f$ and $g$ being the retraction and the section respectively.
\end{proof}
Interestingly, a morphism $f : X \rightarrow Y$ is a (not necessarily split) monomorphism
iff the post-composition function $f_\star$ is injective, and f is a (not necessarily split)
epimorphism iff the pre-composition function $f^\star$ is injective.

\begin{defn}
    \label{defn:slice}
    For a category $\cat{C}$ and object $C \in \cat{C}$, there is a category $C/\cat{C}$
    called the \textbf{slice category} of $\cat{C}$ under $C$ whose objects are
    morphisms $f : C \rightarrow X$ and morphisms between morphisms
    $f : C \rightarrow X$ and $g : C \rightarrow Y$ are maps $h : X \rightarrow Y$
    such that $h \circ f = g$.
\end{defn}
The slice category of $\cat{C}$ over $C$ ($\cat{C}/C$) is defined as ${(C/\cat{C}^\op)}^\op$.
Sometimes the slice category under $C$ is also called coslice category.
\begin{ex}
    Show that the category axioms hold for the slice categories $C/\cat{C}$ and $\cat{C}/C$.
\end{ex}

\section{Functors and natural transformations}
\begin{defn}
\label{defn:functor}
A \textbf{functor} $F : \cat{C} \longrightarrow \cat{D}$ between categories $\cat{C}$
and $\cat{D}$ is defined by:
\begin{itemize}
    \item an object $F X \in \cat{D}$ for each object $X \in \cat{C}$;
    \item a morphism $F f : F X \rightarrow F Y$ for each morphism $f: X \rightarrow Y$.
\end{itemize}
\end{defn}
The mapping should respect function composition and identity morphisms.
A functor $F : \cat{C}^{\op} \longrightarrow \cat{D}$ is also called a contravariant functor
between $\cat{C}$ and $\cat{D}$, while functors $F : \cat{C} \longrightarrow \cat{D}$ are
covariant. Functors may not preserve monomorphisms or epimorphisms, but they
necessarily preserve split monomorphisms, split epimorphisms, and isomorphisms.
Functor can be composed in the obvious way:
small categories (i.e. whose collections of objects and morphisms are sets) and functors
between them define the category $\cat{Cat}$.

\begin{defn}
\label{defn:hom}
Every locally small category $\cat{C}$ (i.e. whose hom-sets are actually sets and not proper
classes) defines for each object $X \in \cat{C}$ a pair of covariant and contravariant
functors $\Hom{C}{X}{-} : \cat{C} \longrightarrow \cat{Set}$ and
$\Hom{C}{-}{X} : \cat{C}^{\op} \longrightarrow \cat{Set}$.
The \textbf{hom-functors} map each object to a set of morphisms, and a morphism
$f : Y \rightarrow Z$ is subject to the following mappings:
\begin{itemize}
    \item $\Hom{C}{X}{f}$ is the post-composition function $f_\star$, which
        maps each morphism $g \in \Hom{C}{X}{Y}$ to the composite~$f \circ g \in \Hom{C}{X}{Z}$;
    \item $\Hom{C}{f}{X}$ is the pre-composition function $f^\star$, which
        maps each morphism $g \in \Hom{C}{Z}{X}$ to the composite
        $g \circ f \in \Hom{C}{Y}{X}$.
\end{itemize}
\end{defn}
These two functors together define a bifunctor $$\Hom{C}{-}{-} : \cat{C}^\op \times \cat{C}
\longrightarrow \cat{Set}$$ from the product category $\cat{C}^\op \times \cat{C}$ to
the category $\cat{Set}$ of sets and functions between them.

\begin{ex}
    Show that the hom-functors satisfy the functoriality axioms.
\end{ex}
\begin{proof}
        We have that $\Hom{C}{X}{\id_Y} = \id_{\Hom{C}{X}{Y}}$ because the post-composition
            func\-tion $\id_\star$ is the identity by the category axioms; the same
            holds for $\Hom{C}{\id_Y}{X}$.
        $\Hom{C}{X}{f \circ g} = (f \circ g)_\star = f_\star \circ g_\star =
            \Hom{C}{X}{f} \circ \Hom{C}{X}{g}$ follows from the associativity of composition;
            the same holds for $\Hom{C}{f \circ g}{X}$.
\end{proof}

Every functor $F : \cat{C} \longrightarrow \cat{D}$ automatically defines another functor
$F : \cat{C}^\op \longrightarrow \cat{D}^\op$.

\begin{defn}
\label{defn:comma}
Given functors $F : \cat{D} \longrightarrow \cat{C}$ and $G : \cat{E} \longrightarrow \cat{C}$,
the \textbf{comma category} $F \downarrow G$ has
\begin{itemize}
    \item as objects, triples $(D \in \cat{D}, E \in \cat{E}, f : F D  \rightarrow G E)$;
    \item as morphisms $(D, E, f) \rightarrow (D', E', f')$, a pair
        $(h : D \rightarrow D', k : E \rightarrow E')$, such that the following diagram
        commutes.
        \begin{figure}[H]
            \centering
            \begin{tikzcd}
                F D \arrow[dd, "F h"'] \arrow[rr, "f"] &  & GE \arrow[dd, "G k"] \\
                                                       &  &                      \\
                F D' \arrow[rr, "f'"']                 &  & GE'                 
            \end{tikzcd}
        \end{figure}
\end{itemize}
Identity morphisms are $(\id_D, \id_E)$.
Composition of morphisms is defined in the obvious way, by stacking commutative
squares vertically.
\end{defn}
The functor $\dom : F \downarrow G \longrightarrow \cat{D}$ maps each object
$(D \in \cat{D}, E \in \cat{E}, f)$ to $D$ and
each morphism $(h, g)$ to $h$; the functor $\cod : F \downarrow G \longrightarrow \cat{E}$
maps each object $(D, E)$ to $E$ and each morphism $(h, g)$ to $g$.
The functoriality axioms are satisfied trivially.

\begin{ex}
    Define functors to construct the slice categories $C/\cat{C}$ and $\cat{C}/C$
    (Definition \ref{defn:slice}) as special cases of comma categories.
    What are the projection functors?
\end{ex}
\begin{proof}
    $C/\cat{C}$ can be expressed as the comma category $\Id \downarrow \1_C$, where
    $\Id : \cat{C} \longrightarrow \cat{C}$ is the identity functor on $\cat{C}$ and
    $\1_C : \cat{1} \longrightarrow \cat{C}$ is the functor from the trivial category
    $\cat{1}$ to $\cat{C}$ that maps the only object of $\cat{1}$ to $C$.
    $\cat{C}/C$ by duality is the comma category $\1_C \downarrow \Id$.
\end{proof}

In the same way as a functor is a mapping between categories, a natural transformation
is a structure-preserving mapping between functors.
\begin{defn}
    \label{defn:natural}
    A \textbf{natural transformation} $\alpha : F \Longrightarrow G$
    between functors $F : \cat{C} \longrightarrow \cat{D}$
    and $G : \cat{C} \longrightarrow \cat{D}$ is a mapping $\alpha_X$, called
    the component of $\alpha$ at $X$, for each $X \in \cat{C}$ such that for each
    morphism $f : X \rightarrow X'$ in $\cat{C}$ the
    following diagram commutes.
    \begin{figure}[H]
        \centering
        \begin{tikzcd}
            F X \arrow[dd, "Ff"'] \arrow[rr, "\alpha_X"] &  & GX \arrow[dd, "Gf"] \\
                                                         &  &                     \\
            F X' \arrow[rr, "\alpha_{X'}"']              &  & GX'
        \end{tikzcd}
    \end{figure}
\end{defn}
A natural transformation is usually specified implicitly using its components, by
saying that morphisms $\alpha_X$ are natural. If a variable $X$ is being used
to index the $\alpha_X$, one may say that the arrows $\alpha$ are natural in $X$,
with $X$ ranging in the domain category of the functors.

Natural transformations can be composed in the obvious way, by composing the
respective components. Therefore functors between two categories $\cat{C}$
and $\cat{D}$ form the \textbf{functor category}, denoted $\fcat{C}{D}$.

Let $\cat{2}$ denote the category with two objects, denoted $0$ and $1$, and a
single non-identity arrow $m : 0 \rightarrow 1$. There are two functors
$i_0, i_1 : \cat{1} \longrightarrow \cat{2}$ that map the single object $*$
to $0$ and $1$ respectively.
\begin{ex}
    Fixing a parallel pair of functors $F, G : \cat{C} \longrightarrow \cat{D}$, natural
    transformations $\alpha : F \Longrightarrow G$ correspond bijectively to functors
    $H : \cat{C} \times \cat{2} \longrightarrow \cat{D}$ such that $H$ restricts along
    $i_0$ and $i_1$ (mappings $C \mapsto (C, 0)$ and $C \mapsto (C, 1)$) to the functors
    $F$ and $G$, i.e., so that the following diagram commutes.
    \begin{figure}[H]
        \centering
        \begin{tikzcd}
            \cat{C} \arrow[r, "i_0"] \arrow[rd, "F"'] & \cat{C} \times \cat{2} \arrow[d, "H"]
                                                      & \cat{C} \arrow[l, "i_1"'] \arrow[ld, "G"] \\
                                                      & \cat{D}                               &
        \end{tikzcd}
    \end{figure}
\end{ex}
\begin{proof}
    Given a natural transformation $\alpha$, we can define the functor $H$ as follows:
    \begin{itemize}
        \item its action on objects is $(X, 0) \mapsto FX$, $(X, 1) \mapsto GX$
        \item its action on morphisms $(f : X \longrightarrow Y, g)$ is:
            \begin{itemize}
                \item $Ff$ if $g = \id_0$,
                \item $Gf$ if $g = \id_1$,
                \item $\alpha_Y \circ Ff = Gf \circ \alpha_X$ (by the naturality of $\alpha$)
                    if $g = m$.
            \end{itemize}
    \end{itemize}
    The commutativity of the diagram above is trivial.

    $H\id_{(X, M)} = H(\id_X, \id_M)$ is necessarily $\id$ by the functoriality of $F$ and $G$.
    By the definition of $H$ it follows that
    $$H(f \circ g, \id_0) = F(f \circ g) = Ff \circ Fg = H(f, \id_0) \circ H(g, \id_0);$$ the same
    argument applies for $H(f \circ g, \id_1)$.
    For $g : X \rightarrow Y$ and $f : Y \rightarrow Z$, we also have that
    $$H(f \circ g, m) = G(f \circ g) \circ \alpha_X = Gf \circ (Gg \circ \alpha_X) =
    H(f, \id_1) \circ H(g, m);$$ this is sufficient to complete the proof of the functoriality
    of $H$ (note that there is no pair of non-identity composable morphisms in $\cat{2}$).

    We have constructed the required functor from a natural transformation; we shall proceed by
    exhibiting the components of a natural transformation $\alpha$
    from a functor $H$ that fulfills the above requirements.
    We define the component $\alpha_X : FX \rightarrow GX$, with $X \in \cat{C}$ as $H(\id_X, m)$.
    Then
    \begin{equation*}
        \begin{split}
            Gf \circ \alpha_X &= Gf \circ H(\id_X, m) \\ &= H(f, \id_1) \circ H(\id_X, m) =
            H(f, m) \\ &= H(\id_Y, m) \circ H(f, \id_0) \\ &= \alpha_Y \circ Ff;
        \end{split}
    \end{equation*}
    this proves the naturality of $\alpha$.

    It follows easily that the constructed mappings between natural
    transformations $\alpha$ and functors $H$ are inverses to each other.
\end{proof}

A natural transformations whose components are isomorphisms is called a
\textbf{natural isomorphism} $\alpha : F \cong G$, and gives another natural
transformation $\alpha^{-1}$ whose components are inverses to the components of $\alpha$.

The functions $f_\star$ and $f^\star$ for a
morphism $f : X \rightarrow Y$ in $\cat{C}$ are the components of two natural transformations
\begin{equation*}
    \begin{split}
        f_\star : \Hom{C}{-}{X} & \Longrightarrow \Hom{C}{-}{Y} \\
        f^\star : \Hom{C}{Y}{-} & \Longrightarrow \Hom{C}{X}{-} \\
    \end{split}
\end{equation*}

\begin{ex}
    Recall the definition of the comma category of two functors
    $F : \cat{D} \longrightarrow \cat{C}$ and $G : \cat{E} \longrightarrow \cat{C}$
    (Definition \ref{defn:comma}). Construct a canonical natural transformation
    $\alpha : F \circ \dom \Longrightarrow G \circ \cod$.
\end{ex}
\begin{proof}
    The component of the natural transformation at the object
    $(D, E, f) \in F \downarrow G$ is given by $f$ itself.
    Then, $(F \circ \dom)(D, E, f) = FD$, $(G \circ \cod)(D, E, f) = GE$,
    $(F \circ \dom)(h, k) = Fh$ and $(G \circ \cod)(h, k) = k$.
    The naturality condition for $\alpha$ is exactly the same as the commuting square
    for the morphisms in the comma category.
\end{proof}

\begin{defn}
    \label{defn:cateq}
    An \textbf{equivalence of categories} is defined by two functors
    $F : \cat{C} \longrightarrow \cat{D}$ and $G : \cat{D} \longrightarrow \cat{C}$
    together with two natural isomorphisms $\eta : G \circ F \cong \Id_\cat{C}$ and
    $\epsilon : F \circ G \cong \Id_\cat{D}$.
\end{defn}

\begin{defn}
    \label{defn:funcprops}
    A functor $F : \cat{C} \longrightarrow \cat{D}$ is called:
    \begin{itemize}
        \item \textbf{faithful} if the function
            $$F(-) : \Hom{C}{X}{Y} \rightarrow \Hom{D}{FX}{FY}$$ is injective;
        \item \textbf{full} if $F(-)$ is surjective;
        \item \textbf{essentially surjective on objects} if for every object
            $Y \in \cat{D}$ there exists an object $X \in \cat{C}$ such that
            $FX$ is isomorphic to $Y$.
    \end{itemize}
\end{defn}
Note that fullness and faithfulness are local properties, i.e.,
a faithful functor need not be injective on objects or morphisms,
and a full functor need not be surjective on objects or morphisms.
A faithful functor that is injective on objects (and therefore on morphisms)
defines an \textbf{embedding} of $\cat{C}$ into $\cat{D}$; a fully faithful functor
that is injective on objects defines a \textbf{full embedding} of $\cat{C}$ as a
full subcategory of $\cat{D}$.

\begin{thm}
    \label{thm:cateq}
    A functor that determines an equivalence of categories is full, faithful and
    essentially surjective on objects.
    Assuming the axiom of choice, conversely, any functor with these properties
    defines an equivalence of categories.
\end{thm}
\begin{proof}
    Assume that $F : \cat{C} \longrightarrow \cat{D}$ and $G : \cat{D} \longrightarrow \cat{C}$
    determine an equivalence of categories via natural isomorphisms $\eta : G \circ F \cong \Id_\cat{C}$
    and $\epsilon : F \circ G \cong \Id_\cat{D}$.
    The fact that $F$ is essentially surjective is easily proved by observing that $D \simeq FGD$
    for all $D \in \cat{D}$ with the component $\epsilon_D$ as the witness of the isomorphism.

    Now note that for any morphism $f, g : X \rightarrow Y$ and fixed isomorphisms $X \simeq X'$,
    $Y \simeq Y'$, there is a unique morphism $f'$ such that the following diagram commutes.
    \begin{figure}[H]
        \centering
        \begin{tikzcd}
            X \arrow[d, "f"'] \arrow[r, "\simeq"] & X' \arrow[d, "\exists!f'"] \\
            Y \arrow[r, "\simeq"']                & Y'
        \end{tikzcd}
    \end{figure}
    Suppose that $Ff = Fg$, with $f, g : X \rightarrow Y$: then $GFf = GFg$. The
    components $\eta_X$, $\eta_Y$ act as the isomorphisms to construct the
    diagram
    \begin{figure}[H]
        \centering
        \begin{tikzcd}
            GFX \arrow[d, "GFf=GFg"'] \arrow[r, "\eta_X"] & X \arrow[d, "f\ \text{or}\ g"] \\
            GFY \arrow[r, "\eta_Y"']                     & Y
        \end{tikzcd}
    \end{figure}
    that commutes by the naturality of $\eta$.
    Both $f$ and $g$ make the diagram commute, and the uniqueness property guarantees
    that $f = g$.
    This proves the faithfulness of $F$ and, by symmetry, of $G$.

    Now assume $k : FX \rightarrow FY$. The following diagram shows the existence
    of a unique $h : X \rightarrow Y$ such that both $Gk$ and $GFh$ make the square commute:
    \begin{figure}[H]
        \centering
        \begin{tikzcd}
            X \arrow[d, "h"'] \arrow[r, "\eta_X"] & GFX \arrow[d, "GFh\ \text{or}\ Gk"] \\
            Y \arrow[r, "\eta_{Y}"']               & GFY
        \end{tikzcd}
    \end{figure}
    Therefore $GFh = Gk$, whence, by faithfulness of $G$, $Fh = k$.
    Thus $F$ is full, faithful and essentially surjective.

    For the converse, suppose that $F$ is a fully faithful essentially surjective functor.
    We shall first construct a functor $G$ in the following way:
    \begin{itemize}
        \item $GD$, with $D \in \cat{D}$, is chosen from the $C \in \cat{C}$ such that
            $FC \simeq D$.
            The existence of at least one such $C$ is guaranteed because $F$ is essentially
            surjective.
        \item $Gf$, with $f : X \rightarrow Y$ in $\cat{D}$, is constructed by composing $f$ with
            isomorphisms $\epsilon_X : X \simeq FGX$ and $\epsilon_Y : Y \simeq FGY$ given by the
            construction of $G$ and then taking the preimage of the resulting morphism
            $FGX \rightarrow FGY$ under $F$, whose existence is guaranteed by the fullness of $F$.
    \end{itemize}
    We need to prove the functoriality of $G$.
    Its action on identity morphisms is clear: to each object $X \in \cat{D}$ is assigned a single
    isomorphism $\epsilon_X : X \simeq FGX$; the application of $G$ to the identity morphism $\id_X$
    yields the preimage under $F$ of
    $\epsilon_X \circ \id_X \circ \epsilon_X^{-1} = \epsilon_X \circ \epsilon_X^{-1} = \id_{FGX}$.
    This preimage must be unique by the faithfulness of $F$ and therefore must be exactly $\id_{GX}$.

    $G(f \circ g)$ with $f : Y \rightarrow Z$ and
    $g : X \rightarrow Y$ is $F^{-1}(\epsilon_Z \circ f \circ g \circ \epsilon_X^{-1})$ (we use
    the notation $F^{-1}$ to indicate the inverse of the bijection estabilished by $F$ on each
    hom-set).
    But then
    \begin{equation*}
        \begin{split}
            F(Gf \circ Gg) &=
            F(F^{-1}(\epsilon_Z \circ f \circ \epsilon_Y^{-1}) \circ
            F^{-1}(\epsilon_Y \circ g \circ \epsilon_X^{-1})) \\
            &= F(F^{-1}(\epsilon_Z \circ f \circ \epsilon_Y^{-1})) \circ
            F(F^{-1}(\epsilon_Y \circ g \circ \epsilon_X^{-1})) \\
            &= (\epsilon_Z \circ f \circ \epsilon_Y^{-1}) \circ (\epsilon_Y \circ g \circ \epsilon_X^{-1}) \\
            &= \epsilon_Z \circ f \circ g \circ \epsilon_X^{-1}.
        \end{split}
    \end{equation*}
    Thus $G(f \circ g)$ and $Gf \circ Gg$ are both valid preimages of
    $\epsilon_Z \circ f \circ g \circ \epsilon_X^{-1}$; by the faithfulness of $F$, these are equal
    and the functoriality of $G$ is proven.

    The isomorphisms $\epsilon_X$ are by definition the components of a natural isomorphism
    $F \circ G \cong \Id_\cat{D}$.
    It remains to exhibit a natural isomorphism $\eta : G \circ F \cong \Id_\cat{C}$.
    $F$ is full and faithful, so we may define the components $\eta_X$ as $F^{-1}\epsilon^{-1}_{FX}$.
    The preimage is guaranteed to exist because $\epsilon_{FX} : FX \simeq FGFX$.
    Fully faithful functors ``reflect'' isomorphisms, meaning that if $Ff$ is an isomorphism
    in $\cat{D}$, $f$ is necessarily an isomorphism in $\cat{C}$; this guarantees that components
    $\eta_X$ are isomorphisms. It remains to prove the naturality of $\eta$.

    Note that in a diagram constructed as follows, if the left square commutes and the entire rectangle
    commutes, it is easily shown that the right square commutes too (because $\gamma_1$ is an
    isomorphism and thus is also an epimorphism).
    \begin{figure}[H]
    \centering
    \begin{tikzcd}
        A \arrow[d, "f"'] \arrow[r, "\stackrel{\gamma_1}{\simeq}"] &
        B \arrow[d, "g"] \arrow[r, "\stackrel{\gamma_2}{\simeq}"] & C \arrow[d, "h"] \\
        A' \arrow[r, "\stackrel{\gamma'_1}{\simeq}"']              &
        B' \arrow[r, "\stackrel{\gamma'_2}{\simeq}"']             & C'
    \end{tikzcd}
    \end{figure}
    Now consider the following diagram in $\cat{D}$:
    \begin{figure}[H]
        \centering
        \begin{tikzcd}
            FX \arrow[d, "Ff"] \arrow[r, "\epsilon_{FX}"] &
            FGFX \arrow[r, "F\eta_X"] \arrow[d, "FGFf"] & FX \arrow[d, "Ff"] \\
            FY \arrow[r, "\epsilon_{FY}"']                &
            FGFY \arrow[r, "F\eta_Y"']                  & FY
        \end{tikzcd}
    \end{figure}
    The square on the left commutes by the naturality of $\epsilon_{FX}$ and the rectangle
    commutes by the definition of $\eta_X$. Therefore the right square commutes as
    well; the faithfulness of $F$ proves that $\eta_Y \circ GFf = f \circ \eta_X$,
    i.e., $\eta$ is natural.
\end{proof}

\begin{ex}
    $\cat{\Gamma}$ is the category whose objects are all finite sets, and whose morphisms
    from $S$ to $T$ are the maps $\theta : S \rightarrow \power{T}$ such that $\theta(a)$
    and $\theta(b)$ are disjoint when $a \neq b$. The composite of
    $\theta : S \rightarrow \power{T}$ and $\phi : T \rightarrow \power{U}$ is
    $\psi : S \rightarrow \power{U}$ where $\phi(a) = \bigcup_{b \in \theta(a)} \phi(b)$.

    Prove that $\cat{\Gamma}$ is equivalent to the opposite of the category $\cat{Fin_*}$
    of finite pointed sets and basepoint preserving functions.
\end{ex}
\begin{proof}
    The equivalence is proven by constructing a fully faithful essentially surjective on objects
    functor $F : \cat{Fin_*} \longrightarrow \cat{\Gamma}^\op$.
    The functor $F$ is defined as follows:
    \begin{itemize}
        \item $F(S)$ with $\bullet \in S$ being the basepoint, is the set $S \backslash \{\bullet\}$.
        \item $F(f)$, with $f : A \rightarrow B$, assigns to each $b \in B \backslash \{\bullet\}$
            its set of non-basepoint preimages $\{a \in A \backslash \{\bullet\}\ |\ f(a) = b\}$.
    \end{itemize}
    Note that $F(g \circ f)$, with $f : A \rightarrow B$ and $g : B \rightarrow C$, is the mapping
    $c \mapsto \{a \in A \backslash \{\bullet\}\ |\ g(f(a)) = c\}$. This coincides with the set
    $\{a \in A \backslash \{\bullet\}\ |\ (\exists b \in B \backslash \{\bullet\}\ |\ f(a) = b \wedge g(b) = c)\} =
    \bigcup_{b \in Fg(c)} Ff(b) = Ff \circ Fg$.
    It is easy to check that $F$ preserves identity arrows; therefore $F$ is a proper functor.

    The faithfulness of $F$ follows from the fact that for a pair of distinct parallel morphisms
    $f, g : A \rightarrow B$ there has to be at least an element $a \in A \backslash \{\bullet\}$
    such that $f(a) \neq g(a)$. But then $a \in Ff(f(a)) \wedge a \notin Fg(f(a))$: therefore the
    two functions $Ff$ and $Fg$ are distinct.

    $F$ is full because to each mapping $f : A \backslash \{\bullet\} \rightarrow \power{B \backslash \{\bullet\}}$
    in $\cat{\Gamma}$ we can assign a function that maps each $b \in B \backslash \{\bullet\}$ to the unique (because of
    the disjointness of images under $f$) $a \in A \backslash \{\bullet\}$ such that $b \in f(a)$, or to the the basepoint
    $\bullet \in A$ if such a preimage does not exist.

    Finally, $F$ is essentially surjective since each set $A$ can be equipped with a basepoint $\bullet$
    to obtain a pointed set that is brought to $A$ under the action of $F$.
\end{proof}

\section{Representable functors and Yoneda lemma}
\begin{defn}
    \label{defn:repr}
    A functor $F : \cat{C} \longrightarrow \cat{Set}$ is \textbf{representable} iff it is naturally isomorphic to
    a covariant hom-functor of the appropriate variance represented by some object $X$ in the locally small
    category $\cat{C}$.
    In other words, a covariant functor $F : \cat{C} \longrightarrow \cat{Set}$ is represented by $X$ iff
    $F \cong \Hom{C}{X}{-}$.
    A contravariant functor $F : \cat{C}^\op \longrightarrow \cat{Set}$ is represented by $X$ iff
    $F \cong \Hom{C}{-}{X}$.
\end{defn}
The adjective ``free'' usually denotes an object that represents a covariant functor.
As an example, the free group on a single generator ($\mathbb{Z}$) represents the covariant forgetful
functor $\cat{Grp} \longrightarrow \cat{Set}$ that brings a group to its set of elements, for a
group homomorphism $\mathbb{Z} \rightarrow G$ is uniquely determined by the image of the generator $1$.
The free unital ring $\mathbb{Z}[x]$ represents the forgetful functor $\cat{Ring} \longrightarrow \cat{Set}$.

\begin{ex}
    Suppose $F : \cat{C} \longrightarrow \cat{Set}$ is equivalent to $G : \cat{D} \longrightarrow \cat{Set}$ in the
    sense that there is an equivalence of categories $H : \cat{C} \longrightarrow \cat{D}$ such that there exists a
    natural isomorphism $F \cong GH$.
    \begin{enumerate}
        \item If $F$ is representable, then is $G$ representable?
        \item If $G$ is representable, then is $F$ representable?
    \end{enumerate}
\end{ex}
\begin{proof}
    Let $\mu : F \cong GH$, $\alpha : F \cong \Hom{C}{M}{-}$, $\epsilon : HH^{-1} \cong \Id_D$.
    We prove that the functor $G$ is represented by the object $HM \in \cat{D}$.
    First, note that both $H(-)$ and $H^{-1}(-)$, as mappings between hom-sets, are bijections as a result
    of Theorem \ref{thm:cateq} and that any isomorphism $f$ in a category defines necessarily bijective
    pre- and post-composition functions $f^*$ and $f_*$.
    We define the components of the natural isomorphism $\beta : G \cong \Hom{D}{HX}{-}$ as the dashed
    composites in the following diagram.
    \begin{figure}[H]
        \centering
        \resizebox{\linewidth}{!}{%
            % https://q.uiver.app/?q=WzAsMTIsWzEsMSwiXFxIb217Q317TX17SF57LTF9WH0iXSxbMiwxLCJcXEhvbXtEfXtITX17SEheey0xfVh9Il0sWzMsMSwiXFxIb217RH17SE19e1h9Il0sWzEsMiwiXFxIb217Q317TX17SF57LTF9WX0iXSxbMiwyLCJcXEhvbXtEfXtITX17SEheey0xfVl9Il0sWzMsMiwiXFxIb217RH17SE19e1l9Il0sWzAsMCwiRkheey0xfVgiXSxbMCwzLCJGSF57LTF9WSJdLFsyLDAsIkdISF57LTF9WCJdLFs0LDAsIkdYIl0sWzIsMywiR0hIXnstMX1ZIl0sWzQsMywiR1kiXSxbMCwxLCJILSIsMCx7InN0eWxlIjp7InRhaWwiOnsibmFtZSI6ImFycm93aGVhZCJ9fX1dLFszLDQsIkgtIiwyLHsic3R5bGUiOnsidGFpbCI6eyJuYW1lIjoiYXJyb3doZWFkIn19fV0sWzQsNSwiKFxcZXBzaWxvbl9YKV8qIiwyLHsic3R5bGUiOnsidGFpbCI6eyJuYW1lIjoiYXJyb3doZWFkIn19fV0sWzAsMywiKEheey0xfWYpXyoiLDJdLFsyLDUsImZfKiJdLFs2LDcsIkZIXnstMX1mIiwyXSxbMCw2LCJcXGFscGhhX3tIXnstMX1YfSIsMCx7InN0eWxlIjp7InRhaWwiOnsibmFtZSI6ImFycm93aGVhZCJ9fX1dLFs3LDMsIlxcYWxwaGFfe0heey0xfVl9IiwwLHsic3R5bGUiOnsidGFpbCI6eyJuYW1lIjoiYXJyb3doZWFkIn19fV0sWzYsOCwiXFxtdV97SF57LTF9WH0iLDAseyJzdHlsZSI6eyJ0YWlsIjp7Im5hbWUiOiJhcnJvd2hlYWQifX19XSxbOCw5LCJHXFxlcHNpbG9uX1giLDAseyJzdHlsZSI6eyJ0YWlsIjp7Im5hbWUiOiJhcnJvd2hlYWQifX19XSxbNywxMCwiXFxtdV97SF57LTF9WX0iLDIseyJzdHlsZSI6eyJ0YWlsIjp7Im5hbWUiOiJhcnJvd2hlYWQifX19XSxbMTAsMTEsIkdcXGVwc2lsb25fWSIsMix7InN0eWxlIjp7InRhaWwiOnsibmFtZSI6ImFycm93aGVhZCJ9fX1dLFs5LDExLCJmIl0sWzIsOSwiXFxiZXRhX1giLDIseyJzdHlsZSI6eyJ0YWlsIjp7Im5hbWUiOiJhcnJvd2hlYWQifSwiYm9keSI6eyJuYW1lIjoiZGFzaGVkIn19fV0sWzUsMTEsIlxcYmV0YV9ZIiwwLHsic3R5bGUiOnsidGFpbCI6eyJuYW1lIjoiYXJyb3doZWFkIn0sImJvZHkiOnsibmFtZSI6ImRhc2hlZCJ9fX1dLFsxLDQsIihISF57LTF9ZilfKiIsMl0sWzEsMiwiKFxcZXBzaWxvbl9YKV8qIiwwLHsic3R5bGUiOnsidGFpbCI6eyJuYW1lIjoiYXJyb3doZWFkIn19fV1d
            \begin{tikzcd}[ampersand replacement=\&]
                {FH^{-1}X} \&\& {GHH^{-1}X} \&\& GX \\
                \& {\Hom{C}{M}{H^{-1}X}} \& {\Hom{D}{HM}{HH^{-1}X}} \& {\Hom{D}{HM}{X}} \\
                \& {\Hom{C}{M}{H^{-1}Y}} \& {\Hom{D}{HM}{HH^{-1}Y}} \& {\Hom{D}{HM}{Y}} \\
                {FH^{-1}Y} \&\& {GHH^{-1}Y} \&\& GY
                \arrow["{H(-)}", tail reversed, from=2-2, to=2-3]
                \arrow["{H(-)}"', tail reversed, from=3-2, to=3-3]
                \arrow["{(\epsilon_X)_*}"', tail reversed, from=3-3, to=3-4]
                \arrow["{(H^{-1}f)_*}"', from=2-2, to=3-2]
                \arrow["{f_*}", from=2-4, to=3-4]
                \arrow["{FH^{-1}f}"', from=1-1, to=4-1]
                \arrow["{\alpha_{H^{-1}X}}", tail reversed, from=2-2, to=1-1]
                \arrow["{\alpha_{H^{-1}Y}}", tail reversed, from=4-1, to=3-2]
                \arrow["{\mu_{H^{-1}X}}", tail reversed, from=1-1, to=1-3]
                \arrow["{G\epsilon_X}", tail reversed, from=1-3, to=1-5]
                \arrow["{\mu_{H^{-1}Y}}"', tail reversed, from=4-1, to=4-3]
                \arrow["{G\epsilon_Y}"', tail reversed, from=4-3, to=4-5]
                \arrow["Gf", from=1-5, to=4-5]
                \arrow["{\beta_X}"', dashed, tail reversed, from=2-4, to=1-5]
                \arrow["{\beta_Y}", dashed, tail reversed, from=3-4, to=4-5]
                \arrow["{(HH^{-1}f)_*}"', from=2-3, to=3-3]
                \arrow["{(\epsilon_X)_*}", tail reversed, from=2-3, to=2-4]
            \end{tikzcd}%
        }
    \end{figure}
    The two inner squares commute by the naturality of $\epsilon$ and functoriality of $H$.
    The outer rectangle commutes by the naturality of $\mu$ and $\epsilon$ and the square
    on the left side commutes by the naturality of $\alpha$.
    Therefore the entire diagram commutes as well, and the naturality of $\beta$ (on the right)
    is proven.

    The proof of Part 2 follows directly by noting that a na\-tu\-ral iso\-mor\-phism $FH^{-1} \cong G$
    can be constructed as the composition of $\mu$ and $\epsilon$ and by repeating the same construction
    with $F$ and $G$ interchanged and $H^{-1}$ instead of $H$.
\end{proof}

\begin{defn}
    \label{defn:subfunctor}
    A functor $F$ defines a \textbf{subfunctor} of $G$ is there is a natural transformation
    $\alpha : F \Longrightarrow G$ whose components are monomorphisms.
\end{defn}
\begin{ex}
    In the case of $G : \cat{C}^\op \longrightarrow \cat{Set}$, a subfunctor is given by a collection of subsets
    $FX \subseteq GX$ so that each $Gf : GY \rightarrow GX$ restricts to a function $Ff : FY \rightarrow FX$.
    Characterize those subsets that assemble into a subfunctor of the represented functor $\Hom{C}{-}{C}$.
\end{ex}

What follows is the most important result in category theory, which is a vast generalisation of the
result widely known in group theory as Cayley's theorem.
\begin{thm}[Yoneda lemma]
    \label{thm:yoneda}
    The set of natural transformations $\alpha : \Hom{C}{M}{-} \Longrightarrow F$ is
    in bijective correspondence with elements $x \in FM$ under the mapping $\alpha \mapsto \alpha_M(\id_M)$.
    $$\Hom{\fcat{C}{Set}}{\Hom{C}{M}{-}}{F} \cong FM$$
    Moreover, this bijective mapping is natural in $M$ and $F$.
\end{thm}
\end{document}