\setcounter{chapter}{-1}
\chapter{Categories}
\label{categorychapter}


The language of categories is not strictly necessary to understand the basics
of  commutative
algebra. Nonetheless, it is extremely convenient and powerful. It will clarify
many of the constructions made in the future when we can freely use terms like
``universal property'' or ``adjoint functor.'' As a result, we begin this book
with a brief introduction to category theory. We only scratch the surface; the
interested reader can pursue further study in \cite{Ma98} or \cite{KS05}.


Nonetheless, the reader is advised not to take the present chapter too
seriously; skipping it for the moment to chapter 1 and returning here as a
reference could be quite reasonable.

\section{Introduction}

\subsection{Definitions}

Categories are supposed to be places where mathematical objects live.
Intuitively, to any given type of structure (e.g. groups, rings, etc.),
there should be a
category of objects with that structure. These are not, of course, the only
type of categories, but they will be the primary ones of concern to us in this
book.


The basic idea of a category is that there should be objects, and that one
should be able to map between objects. These mappings could be functions, and
they often are, but they don't have to be. Next, one has to be able to compose
mappings, and associativity and unit conditions are required. Nothing else is required.

\begin{definition}
A \textbf{category} $\mathcal{C}$ consists of:
\begin{enumerate}
\item  A collection of \textbf{objects},
$\ob \mathcal{C}$.
\item For each pair of objects $X, Y \in
\ob \mathcal{C}$, a set
of \textbf{morphisms} $\hom_{\mathcal{C}}(X, Y)$ (abbreviated $\hom(X,Y)$).
\item For each object $X \in \ob\mathcal{C}$, there is an \textbf{identity
morphism}
$1_X \in \hom_{\mathcal{C}}(X, X)$ (often just abbreviated to $1$).
\item There is a \textbf{composition law}
$\circ: \hom_{\mathcal{C}}(X, Y) \times \hom_{\mathcal{C}}(Y, Z) \to
\hom_{\mathcal{C}}(X, Z), (g, f) \to g
\circ f$ for every
triple $X, Y, Z$ of objects.
\item  The composition law is unital  and associative.
In other words, if $f \in \hom_{\mathcal{C}}(X, Y)$, then $1_Y \circ f = f
\circ 1_X = f$. Moreover, if $g \in \hom_{\mathcal{C}}(Y, Z)$ and $h \in
\hom_{\mathcal{\mathcal{C}}}(Z, W)$ for objects $Z, Y, W$, then
\[ h \circ (g \circ f) = (h \circ g) \circ f \in \hom_{\mathcal{C}}(X, W).   \]
\end{enumerate}
\end{definition}

We shall write $f: X \to Y$ to denote an element of $\hom_{\mathcal{C}}(X, Y)$.
In practice, $\mathcal{C}$ will often be the storehouse for mathematical objects: groups, Lie algebras,
rings, etc., in which case these ``morphisms'' will just be ordinary functions.

Here is a simple list of examples.
\begin{example}[Categories of structured sets]
\begin{enumerate}
\item $\mathcal{C}  = \mathbf{Sets}$; the objects are sets, and the morphisms
are functions.
\item $\mathcal{C} = \mathbf{Grps}$; the objects are groups, and the morphisms
are maps of groups (i.e. homomorphisms).
\item $\mathcal{C} = \mathbf{LieAlg}$; the objects are Lie algebras, and the
morphisms are maps of Lie algebras (i.e. homomorphisms).\footnote{Feel free to
omit if the notion of Lie algebra is unfamiliar.}
\item  $\mathcal{C} = \mathbf{Vect}_k$; the objects are vector spaces over a
field $k$, and the morphisms are linear maps.
\item $\mathcal{C} = \mathbf{Top}$; the objects are topological spaces, and the
morphisms are continuous maps.
\item  This example is slightly more subtle. Here the category $\mathcal{C}$
has objects consisting of topological spaces, but the morphisms between two
topological spaces $X,Y$ are the \emph{homotopy classes} of maps $X \to Y$.
Since composition respects homotopy classes, this is well-defined.
\end{enumerate}
\end{example}



In general, the objects of a category do not have to form a set; they can
be too large for
that.
For instance, the collection of objects in $\mathbf{Sets}$ does not form a set.


\begin{definition}
A category is \textbf{small} if the collection of objects is a set.
\end{definition}

The standard examples of categories are the ones above: structured sets
together with structure-preserving maps. Nonetheless, one can easily give
other examples that are not of this form.

\begin{example}[Groups as categories] \label{BG}
Let $G$ be a finite group. Then we can make a category $B_G$ where the objects
just consist of one element $\ast$ and the maps $\ast \to \ast$ are the elements
 $g \in G$. The identity is the identity of $G$ and composition is multiplication
in the group.

In this case, the category does not represent much of  a class of objects, but
instead we think of the composition law as the key thing. So a group is a
special kind of (small) category.
\end{example}

\begin{example}[Monoids as categories]
A monoid is precisely a category with one object. Recall that a \textbf{monoid}
is a set together with  an associative and unital multiplication (but which
need not have inverses).
\end{example}


\begin{example}[Posets as categories] \label{posetcategory} Let $(P, \leq)$ be a partially ordered
 (or even preordered) set (i.e. poset). Then $P$ can be regarded as a (small) category, where the objects are the elements
$p \in P$, and $$\hom_P(p, q) = \begin{cases} 
\ast & \text{if } p \leq q \\
\emptyset & \text{otherwise}
 \end{cases} $$
\end{example} 

There is, however, a major difference between category theory and set theory.
There is \textbf{nothing} in the language of categories that lets one look
\emph{inside} an object. We think of vector spaces having elements, spaces
having points, etc.
By contrast, categories treat these kinds of things as invisible. There
is nothing ``inside'' of an object $X \in \mathcal{C}$; the only way to
understand $X$ is
to understand the ways one can map into and out of $X$.
Even if one is working with  a category of ``structured sets,'' the underlying
set of an object in this category is not part of the categorical data.
However, there are instances in which the ``underlying set'' can be recovered
as a $\hom$-set.

\begin{example}
In the category $\mathbf{Top}$ of topological spaces, one can in fact recover the
``underlying set'' of a topological space via the hom-sets. Namely, for each
topological space, the points of $X$ are the same thing as the mappings from a
one-point space into $X$. 
That is, we have
\[ |X| = \hom_{\mathbf{Top}}(\ast, X),  \]
where $\ast$ is the one-point space.

Later we will say that the functor assigning to each
space its underlying set is \emph{corepresentable.}
\end{example}

\begin{example} 
Let $\mathbf{Ab}$ be the category of abelian groups and group-homomorphisms. Again, the claim is that
using only this category, one can recover the underlying set of a given abelian
group $A$. This is because the elements of $A$ can be canonically identified
with \emph{morphisms} $\mathbb{Z} \to A$ (based on where $1 \in \mathbb{Z}$
maps). 
\end{example} 


\begin{definition} 
We say that $\mathcal{C}$ is a \textbf{subcategory} of the category
$\mathcal{D}$ if the collection of objects of $\mathcal{C}$ is a subclass of
the collection of objects of $\mathcal{D}$, and if whenever
$X, Y \in \mathcal{C}$, we have
\[ \hom_{\mathcal{C}}(X, Y) \subset \hom_{\mathcal{D}}(X, Y)  \]
with the laws of composition in $\mathcal{C}$ induced by that in $\mathcal{D}$.

$\mathcal{C}$ is called a \textbf{full subcategory} if $\hom_{\mathcal{C}}(X,
Y) = \hom_{\mathcal{D}}(X, Y)$ whenever $X, Y \in \mathcal{C}$.
\end{definition} 


\begin{example} 
The category of abelian groups is a full subcategory of the category of groups.
\end{example} 


\subsection{The language of commutative diagrams}

While the language of categories is, of course, purely algebraic, it will be
convenient for psychological reasons to visualize categorical arguments
through diagrams.
We shall introduce this notation here.

Let $\mathcal{C}$ be a category, and let $X, Y$ be objects in $\mathcal{C}$.
If $f \in \hom(X, Y)$, we shall sometimes write $f$ as an arrow
\[ f: X \to Y  \]
or
\[ X \stackrel{f}{\to} Y \]
as if $f$ were an actual function.
If $X \stackrel{f}{\to} Y$ and $Y \stackrel{g}{\to} Z$ are morphisms,
composition $g \circ f: X \to Z$ can be visualized by the picture
\[ X \stackrel{f}{\to} Y \stackrel{g}{\to} Z.\]

Finally, when we work with several objects, we shall often draw collections of
morphisms into diagrams, where arrows indicate morphisms between two objects.
\begin{definition}
A diagram will be said to \textbf{commute} if whenever one goes from one
object in the diagram to another by following the arrows in the right order,
one obtains the same morphism.
For instance, the commutativity of the diagram
\[ \xymatrix{
X \ar[d]^f \ar[r]^{f'} &  W \ar[d]^g \\
Y \ar[r]^{g'} &  Z
}\]
is equivalent to the assertion that
\[ g \circ f' = g' \circ f \in \hom(X, Z).  \]
\end{definition}


As an example, the assertion that the associative law holds in a category
$\mathcal{C}$ can be stated as follows. For every quadruple $X, Y, Z, W \in
\mathcal{C}$, the following diagram (of \emph{sets}) commutes:
\[ \xymatrix{
\hom(X, Y) \times \hom(Y, Z) \times \hom(Z, W) \ar[r] \ar[d]  & \hom(X, Z)
\times \hom(Z, W) \ar[d]  \\
\hom(X,Y) \times \hom(Y, W) \ar[r] &  \hom(X, W).
}\]
Here the maps are all given by the composition laws in $\mathcal{C}$. 
For instance, the downward map to the left is the product of the identity on
$\hom(X, Y)$ with the composition law $\hom(Y, Z) \times \hom(Z, W) \to \hom(Y,
W)$. 
\subsection{Isomorphisms}

Classically, one can define an isomorphism of groups as a bijection that
preserves the group structure. This does not generalize well to categories, as
we do not have a notion of ``bijection,'' as there is no way (in general) to
talk about the ``underlying set'' of an object.
Moreover, this definition does not generalize well to topological spaces:
there, an isomorphism should not just be a bijection, but something which
preserves the topology (in a strong sense), i.e. a homeomorphism.


Thus we make:

\begin{definition}
An \textbf{isomorphism} between objects $X, Y$ in a category $\mathcal{C}$ is a
map $f: X \to Y$ such that there exists $g: Y \to X$ with
\[ g \circ f = 1_X, \quad f \circ g = 1_Y.  \]

Such a $g$ is called an \textbf{inverse} to $f$. \end{definition}

\begin{remark}
It is easy to check that the inverse $g$ is
unique. Indeed, suppose $g, g'$ both were inverses to $f$. Then 
\[ g' = g' \circ 1_Y = g' \circ (f \circ g) = (g' \circ f) \circ g = 1_X
\circ g = g.  \]
\end{remark}

This notion is isomorphism is more correct than the idea of being one-to-one and onto. A bijection of
topological spaces is not necessarily a homeomorphism.


\begin{example} 
It is easy to check that an isomorphism in the category $\mathbf{Grp}$ is an
isomorphism of groups, that an isomorphism in the category $\mathbf{Set}$ is a
bijection, and so on. 
\end{example} 

We are supposed to be able to identify isomorphic objects. In the categorical
sense, this means mapping into $X$ should be the same as mapping into $Y$, if
$X, Y$ are isomorphic, via an isomorphism $f: X \to Y$.
Indeed, let 
$Z$ be another object of $\mathcal{C}$.
Then we can define a map
\[ \hom_{\mathcal{C}}(Z, X) \to \hom_{\mathcal{C}}(Z, Y)  \]
given by post-composition with $f$. This is a \emph{bijection} if $f$ is an
isomorphism (the inverse is given by postcomposition with the inverse to $f$).
Similarly, one can easily see that mapping \emph{out of} $X$ is essentially the
same as mapping out of $Y$. 
Anything in general category theory that is true for $X$ should be true for $Y$
(as general category theory can only try to understand $X$ in terms of maps
into or out of it!). 

\begin{exercise} 
The relation ``$X, Y$ are isomorphic'' is an equivalence relation on the class
of objects of a category $\mathcal{C}$.
\end{exercise} 

\begin{exercise} 
Let $P$ be a preordered set, and make $P$ into a category as in
\cref{posetcategory}. Then $P$ is a poset if and only if two isomorphic objects
are equal.
\end{exercise} 

For the next exercise, we need:
\begin{definition}
A \textbf{groupoid} is a category where every morphism is an isomorphism.
\end{definition}
\begin{exercise} 
 The
sets $\hom_{\mathcal{C}}(A, A)$ are \emph{groups} if $\mathcal{C}$ is a
groupoid and $A \in \mathcal{C}$. A group is essentially the same as a groupoid
with one object. 
\end{exercise}

\begin{exercise}

Show that the following is a groupoid. Let $X$ be a topological space, and let
$\Pi_1(X)$ be the category defined as follows: the objects are elements of $X$,
and morphisms $x \to y$ (for $x,y \in X$) are homotopy classes of maps $[0,1]
\to X$ (i.e. paths) that send $0 \mapsto x, 1 \mapsto y$. Composition of maps
is given by concatenation of paths.
(Check that, because one is working with \emph{homotopy classes} of paths,
composition is associative.)

$\Pi_1(X)$ is called the \textbf{fundamental groupoid} of $X$. Note that
$\hom_{\Pi_1(X)}(x, x)$ is the \textbf{fundamental group} $\pi_1(X, x)$.
\end{exercise} 

\section{Functors}

A functor is a way of mapping from one category to another: each object is sent
to another object, and each morphism is sent to another morphism. We shall
study many functors in the sequel: localization, the tensor product, $\hom$,
and fancier ones like $\tor, \ext$, and local cohomology functors.
The main benefit of a functor is that it doesn't simply send objects to
other objects, but also morphisms to morphisms: this allows one to get new commutative
diagrams from old ones.
This will turn out to be a powerful tool.


\subsection{Covariant functors}
Let $\mathcal{C}, \mathcal{D}$ be categories. If $\mathcal{C}, \mathcal{D}$
are categories of structured sets (of possibly different types), there may be a
way to associate objects in $\mathcal{D}$ to objects in $\mathcal{C}$. For
instance, to every group $G$ we can associate its \emph{group ring}
$\mathbb{Z}[G]$
 (which we do not define here); to each topological space we can associate its
 \emph{singular chain complex}, and so on.
In many cases, given a map between objects in $\mathcal{C}$ preserving the
relevant structure, there will be an induced map on the corresponding objects
in $\mathcal{D}$. It is from here that we define a \emph{functor.}

\begin{definition} \label{covfunc}
A \textbf{functor} $F: \mathcal{C} \to \mathcal{D}$ consists of a function $F:
\mathcal{C} \to  \mathcal{D}$ (that is, a rule that assigns to each object
in $\mathcal{C}$ an object of $\mathcal{D}$) and, for each pair $X, Y \in
\mathcal{C}$,
a map
$F: \hom_{\mathcal{C}}(X, Y) \to \hom_{\mathcal{D}}(FX, FY)$, which preserves
the identity
maps and composition.

In detail, the last two conditions state the following. 
\begin{enumerate}
\item  If $X \in
\mathcal{C}$, then $F(1_X)$ is the identity morphism $1_{F(X)}: F(X) \to
F(X)$.
\item  If $A \stackrel{f}{\to} B \stackrel{g}{\to} C$ are
morphisms in $\mathcal{C}$,
then $F(g \circ f) = F(g) \circ F(f)$ as morphisms $F(A) \to F(C)$.
Alternatively, we can say that $F$ \emph{preserves commutative diagrams.}
\end{enumerate}
\end{definition}

In the last statement of the definition, note that if 
\[ \xymatrix{
X \ar[rd]^h \ar[r]^f &  Y \ar[d]^g \\
 & Z
}\]
is a commutative diagram in $\mathcal{C}$, then the diagram obtained by
applying the functor $F$, namely
\[ \xymatrix{
F(X) \ar[rd]^{F(h)} \ar[r]^{F(f)} &  F(Y) \ar[d]^{F(g)} \\
 & F(Z)
}\]
also commutes. It follows that applying $F$ to more complicated commutative
diagrams also yields new commutative diagrams. 


Let us give a few examples of functors.

\begin{example}
There is a functor from $\mathbf{Sets} \to \mathbf{AbelianGrp}$ sending a set
$S$ to the free abelian group on the set. (For the definition of a free abelian
group, or more generally a free $R$-module over a ring $R$, see
\cref{freemoduledef}.)
\end{example}

\begin{example} \label{pi0}
Let $X$ be a topological space. Then to it we can associate the set $\pi_0(X)$
of \emph{connected components} of $X$. 

Recall that the continuous image of a
connected set is connected, so if $f: X \to Y$ is a continuous map and $X'
\subset X$ connected, $f(X')$ is contained in a connected component of $Y$. It
follows that $\pi_0$ is a functor $\mathbf{Top} \to \mathbf{Sets}$.
In fact, it is a functor on the \emph{homotopy category} as well, because
homotopic maps induce the same maps on $\pi_0$.
\end{example} 


\begin{example}
Fix $n$.
There is a functor from $\mathbf{Top} \to \mathbf{AbGrp}$
(categories of topological spaces and abelian groups) sending a
space $X$ to its  $n$th homology group $H_n(X)$. We know that given a map of spaces
$f: X \to Y$,
we get a map of abelian groups $f_*: H_n(X) \to H_n(Y)$. See \cite{Ha02}, for
instance.
\end{example}

We shall often need to compose functors. For instance, we will want to see, for
instance, that the \emph{tensor product} (to be defined later, see
\cref{sec:tensorprod}) is
associative, which is really a statement about composing functors. The
following (mostly self-explanatory) definition elucidates this.

\begin{definition}\label{composefunctors}
If $\mathcal{C}, \mathcal{D}, \mathcal{E}$ are categories, $F: \mathcal{C} \to
\mathcal{D}, G: \mathcal{D} \to \mathcal{E}$ are covariant functors, then one
can define a \textbf{composite functor}
\[ F \circ G: \mathcal{C}  \to \mathcal{E}  \]
This sends an object $X \in \mathcal{C}$ to $G(F(X))$.
Similarly, a morphism $f :X \to Y$ is sent to $G(F(f)): G(F(X)) \to G(F(Y))$.
We leave the reader to check that this is well-defined.
\end{definition}




\begin{example}\label{categoryofcats}
In fact, because we can compose functors, there is a \emph{category of
categories.} Let $\mathbf{Cat}$ have objects as the small categories, and
morphisms as functors. Composition is defined as in \cref{composefunctors}.
\end{example}


\begin{example}[Group actions] \label{groupact} Fix a group $G$. 
Let us understand what  a functor $B_G \stackrel{}{\to} \mathbf{Sets}$ is. Here $B_G$ is the
category  of \cref{BG}.

The unique object $\ast$ of $B_G$ goes to some set $X$. For each element $g \in G$, we
get a map $g: \ast \to \ast$ and thus a map $X \to X$. This is supposed to
preserve the composition law (which in $G$ is just multiplication), as well as
identities.

In particular, we get maps $i_g: X \to X$ corresponding to each $g \in G$, such
that the following diagram commutes for each $g_1, g_2 \in G$:
\[ \xymatrix{
X \ar[r]^{i_{g_1}} \ar[rd]_{i_{g_1g_2}} & X \ar[d]^{i_{g_2}} \\ & X.
}\]
Moreover, if $e \in G$ is the identity, then $i_e = 1_X$.
So a functor $B_G \to \mathbf{Sets}$ is just a left $G$-action on a set $X$.
\end{example}



An important example of functors is given by the following. Let $\mathcal{C}$
be a category of ``structured sets.'' Then, there is a functor $F: \mathcal{C}
\to \textbf{Sets}$ that sends  a structured set to the underlying set. For
instance, there is a functor from groups to sets that forgets the group
structure.
More generally, suppose given two categories $\mathcal{C}, \mathcal{D}$, such
that $\mathcal{C}$ can be regarded as ``structured objects in $\mathcal{D}$.''
Then there is a functor $\mathcal{C} \to \mathcal{D}$ that forgets the
structure.
Such examples are called \emph{forgetful functors.}

\subsection{Contravariant functors}
Sometimes what we have described above are called \textit{covariant functors}.
Indeed, we shall also be interested in similar objects that reverse the
arrows, such as duality functors:

\begin{definition}
A \textbf{contravariant functor}  $\mathcal{C}
\stackrel{F}{\to}\mathcal{D}$ (between categories $\mathcal{C}, \mathcal{D}$)
is similar
data as in \cref{covfunc} except that now a map $X \stackrel{f}{\to} Y$ now
goes to a map $F(Y)
\stackrel{F(f)}{\to} F(X)$. Composites
are required to be preserved, albeit in the other direction.
In other words, if $X \stackrel{f}{\to} Y, Y \stackrel{g}{\to} Z$ are
morphisms, then we require
\[ F ( g \circ f) = F(f) \circ F(g): F(Z) \to F(X).  \]
\end{definition}

We shall sometimes  say just ``functor'' for \emph{covariant functor}. When we are
dealing with a contravariant functor, we will always say the word
``contravariant.''


A contravariant functor also preserves commutative diagrams, except that the
arrows have to be reversed. For instance, if $F: \mathcal{C} \to \mathcal{D}$
is contravariant and the diagram
\[ \xymatrix{
A \ar[d] \ar[r] &  C\\
B \ar[ru]
}\]
is commutative in $\mathcal{C}$, then the diagram
\[ \xymatrix{
F(A)   & \ar[l] \ar[ld] F(C)\\
F(B) \ar[u]
}\]
commutes in $\mathcal{D}$.

One can, of course, compose contravariant functors as in \cref{composefunctors}. But the composition of two
contravariant functors will be \emph{covariant.} So there is no ``category of
categories'' where the morphisms between categories are contravariant functors. 

Similarly as in \cref{groupact}, we have:

\begin{example}
A \textbf{contravariant} functor from $B_G$ (defined as in \cref{BG}) to $\mathbf{Sets}$ corresponds to a
set with a \emph{right} $G$-action.
\end{example}

\begin{example}[Singular cohomology]
In algebraic topology, one encounters contravariant functors on the homotopy
category of topological spaces via the \emph{singular cohomology} functors $X
\mapsto H^n(X; \mathbb{Z})$. Given a continuous map $f: X \to Y$, there is a
homomorphism of groups
\[ f^* : H^n(Y; \mathbb{Z}) \to H^n(X; \mathbb{Z}).  \]
\end{example} 

\begin{example}[Duality for vector spaces] \label{dualspace}
On the category $\mathbf{Vect}$ of vector spaces over a field $k$, we
have
the contravariant functor
\[ V \mapsto V^{\vee}.  \]
sending a vector space to its dual $V^{\vee} = \hom(V,k)$.
Given a map $V \to W$ of vector spaces, there is an induced map
\[ W^{\vee} \to V^{\vee}  \]
given by the transpose.
\end{example}

\begin{example}
If we map $B_G \to B_G$ sending $\ast \mapsto \ast$ and $g \mapsto g^{-1}$, we
get a
contravariant functor.
\end{example}

We now give a useful (linguistic) device for translating between covariance and
contravariance. 

\begin{definition}[The opposite category] \label{oppositecategory}
Let $\mathcal{C}$ be a category. Define the \textbf{opposite category}
$\mathcal{C}^{op}$ of $\mathcal{C}$ to have the same objects as
$\mathcal{C}$  but such that the morphisms between $X,Y$ in
$\mathcal{C}^{op}$
are those between $Y$ and $X$ in $\mathcal{C}$.
\end{definition}

There is a contravariant functor $\mathcal{C} \to
\mathcal{C}^{op}$.
In fact, contravariant functors out of $\mathcal{C}$ are the \emph{same} as
covariant functors out of $\mathcal{C}^{op}$.

As a result, when results are often stated for both covariant and contravariant
functors, for instance, we can often reduce to the covariant case by using the
opposite category.

\begin{exercise} 
A map that is an isomorphism in $\mathcal{C}$ corresponds to an isomorphism in
$\mathcal{C}^{op}$.
\end{exercise} 
\subsection{Functors and isomorphisms}
Now we want to prove a simple and intuitive fact: if isomorphisms allow one to
say that one object in a category is ``essentially the same'' as another,
functors should be expected to preserve this.
\begin{proposition}
If $f: X \to Y$ is a map in $\mathcal{C}$, and $F: \mathcal{C} \to \mathcal{D}$
is a functor, then $F(f): FX \to FY$ is an isomorphism.
\end{proposition}

The proof is quite straightforward, though there is an important point here.
Note that the analogous result holds for \emph{contravariant} functors too.

\begin{proof}
If we have maps $f: X \to Y$ and $g : Y \to X$ such that the composites both
ways are identities, then we can apply the functor $F$ to this, and we find
that since
\[ f \circ g = 1_Y, \quad g \circ f = 1_X,   \]
it must hold that
\[ F(f) \circ F(g) = 1_{F(Y)}, \quad F(g) \circ F(f) = 1_{F(X)}.  \]
We have used the fact that functors preserve composition and identities. This
implies that $F(f)$ is an isomorphism, with inverse $F(g)$.
\end{proof}

Categories have a way of making things so general that are trivial. Hence,
this material is called general abstract nonsense.
Moreover, there is another philosophical point about category theory to
be made here: often, it is the definitions, and not the proofs, that matter.
For instance, what matters here is not the theorem, but the \emph{definition of
an
isomorphism.} It is a categorical one, and much more general than the usual
notion via injectivity and surjectivity.


\begin{example} 
As a simple example, $\left\{0,1\right\}$ and $[0,1]$ are not isomorphic in the
homotopy category of topological spaces (i.e. are not homotopy equivalent)
because $\pi_0([0,1]) = \ast$ while $\pi_0(\left\{0,1\right\}) $ has two
elements.
\end{example} 

\begin{example} 
More generally, the higher homotopy group functors  $\pi_n$ (see \cite{Ha02}) can be used to show
that the $n$-sphere $S^n$ is not homotopy equivalent to a point. For then
$\pi_n(S^n, \ast)$ would be trivial, and it is not.
\end{example} 


There is room, nevertheless, for something else. Instead of having
something that sends objects to other objects, one could have something that
sends an object to a map.



\subsection{Natural transformations}



Suppose $F, G: \mathcal{C} \to \mathcal{D}$ are functors.

\begin{definition}
A \textbf{natural transformation} $T: F \to G$ consists of the following data.
For each $X \in C$, there is a morphism $TX: FX \to GX$ satisfying the
following
condition. Whenever $f: X \to Y$ is a morphism, the following diagram must
commute:
\[ \xymatrix{
FX \ar[d]^{TX }\ar[r]^{F(f)} &  FY \ar[d]^{TY}  \\
GX \ar[r]^{G(f)} &  GY
}.\]

If $TX$ is an isomorphism for each $X$, then we shall say that $T$ is a
\textbf{natural isomorphism.}
\end{definition}

It is similarly possible to define the notion of a natural transformation
between \emph{contravariant} functors. 

When we say that things are ``natural'' in the future, we will mean that the
transformation between functors is natural in this sense.
We shall use this language to state theorems conveniently.

\begin{example}[The double dual]
Here is the canonical example of ``naturality.''
Let $\mathcal{C}$ be the category of finite-dimensional vector spaces over a
given field $k$. Let us further restrict the category such that the only
morphisms are the \emph{isomorphisms} of vector spaces.
For each $V \in \mathcal{C}$, we know that there is an isomorphism
\[ V \simeq V^{\vee} = \hom_k(V, k),  \]
because both have the same dimension. 

Moreover, the maps $V \mapsto V, V \mapsto V^{\vee}$ are both covariant functors on
$\mathcal{C}$.\footnote{Note that the dual $\vee$ was defined as a
\emph{contravariant} functor in \cref{dualspace}.} The first is the identity functor; for the second, if $f: V \to
W$ is an isomorphism, then there is induced a transpose map $f^t: W^{\vee} \to V^{\vee}$
(defined by sending a map $W \to k$ to the precomposition $V \stackrel{f}{\to}
W \to k$), which is an isomorphism; we can take its inverse.
So we have two functors from $\mathcal{C}$ to itself, the identity and the
dual, and we know that $V \simeq V^{\vee}$ for each $V$ (though we have not
chosen any particular set of isomorphisms).


However, the isomorphism $V \simeq
V^{\vee}$ \emph{cannot} be made natural. That is, there is no way of choosing
isomorphisms
\[ T_V: V \simeq V^{\vee}  \]
such that, 
whenever $f: V \to W$ is an isomorphism of vector spaces, the following diagram
commutes:
\[ \xymatrix{
V \ar[r]^{f} \ar[d]^{T_V}  &  W \ar[d]^{T_W} \\
V^{\vee} \ar[r]^{(f^t)^{-1}} &  W^{\vee}.
}\]
Indeed, fix $d>1$, and choose $V = k^d$. 
Identify $V^{\vee}$ with $k^d$, and so the map $T_V$ is a $d$-by-$d$ matrix $M$
with coefficients in $k$. The requirement is that for each \emph{invertible}
$d$-by-$d$ matrix $N$, we have
\[ (N^t)^{-1}M = MN,  \]
by considering the above diagram with $V = W = k^d$, and $f$ corresponding to
the matrix $N$.
This is impossible unless $M = 0$, by elementary linear algebra.

Nonetheless, it \emph{is} possible to choose a natural isomorphism
\[ V \simeq V^{\vee \vee}.  \]
To do this, given $V$, recall that $V^{\vee \vee}$ is the collection of maps
$V^{\vee} \to k$. To give a map $V \to V^{\vee \vee}$ is thus the same as
giving linear functions $l_v, v \in V$ such that $l_v: V \to k$ is linear in
$v$. We can do this by letting $l_v$ be ``evaluation at $v$.''
That is, $l_v$ sends a linear functional $\ell: V \to k$ to $\ell(v) \in k$. We
leave it to the reader to check (easily) that this defines a homomorphism $V
\to V^{\vee \vee}$, and that everything is natural.
\end{example}





\begin{exercise}
 Suppose there are  two functors $B_G \to
\mathbf{Sets}$, i.e. $G$-sets. What is a natural transformation between them?
\end{exercise}


Natural transformations can be \emph{composed}. Suppose given functors $F, G,
H: \mathcal{C} \to \mathcal{D}$ a natural
transformation $T: F \to G$ and a natural transformation $U: G \to H$. 
Then, for each $X \in \mathcal{C}$, we have maps $TX: FX \to GX, UX: GX \to
HY$. We can compose $U$ with $T$ to get a natural transformation $U \circ T: F
\to H$. 

In fact, we can thus define a \emph{category} of functors
$\mathrm{Fun}(\mathcal{C}, \mathcal{D})$ (at least if $\mathcal{C},
\mathcal{D}$ are small). The objects of this category are the functors $F:
\mathcal{C} \to \mathcal{D}$. The morphisms are natural transformations between
functors. Composition of morphisms is as above. 

\subsection{Equivalences of categories}

Often we want to say that two categories $\mathcal{C}, \mathcal{D}$ are ``essentially the same.'' One way
of formulating this precisely is to say that $\mathcal{C}, \mathcal{D}$ are
\emph{isomorphic} in the category of categories. Unwinding the definitions,
this means that there exist functors
\[ F: \mathcal{C} \to \mathcal{D}, \quad G: \mathcal{D} \to \mathcal{C} \]
such that $F \circ G = 1_{\mathcal{D}}, G \circ F = 1_{\mathcal{C}}$.
This notion, of \emph{isomorphism} of categories, is generally far too
restrictive.

For instance, we could consider the category of all finite-dimensional vector
spaces over a given field $k$, and we could consider the full subcategory
of vector spaces of the form $k^n$. Clearly both categories encode essentially
the same mathematics, in some sense, but they are not isomorphic: one has a
countable set of objects, while the other has an uncountable set of objects.
Thus, we need  a more refined way of saying that two categories are
``essentially the same.''

\begin{definition} 
Two categories $\mathcal{C}, \mathcal{D}$ are called \textbf{equivalent} if
there are functors
\[ F: \mathcal{C} \to \mathcal{D}, \quad G: \mathcal{D} \to \mathcal{C}  \]
and natural isomorphisms
\[ F G \simeq 1_{\mathcal{D}}, \quad GF \simeq 1_{\mathcal{C}}.  \]
\end{definition} 

For instance, the category of all vector spaces of the form $k^n$ is equivalent
to the category of all finite-dimensional vector spaces. 
One functor is the inclusion from vector spaces of the form $k^n$; the other
functor maps a finite-dimensional vector space $V$ to $k^{\dim V}$. Defining
the second functor properly is, however, a little more subtle. 
The next criterion will be useful.

\begin{definition} 
A functor $F: \mathcal{C} \to \mathcal{D}$ is \textbf{fully faithful} if $F:
\hom_{\mathcal{C}}(X, Y) \to \hom_{\mathcal{D}}(FX, FY)$ is a bijection for each pair of objects $X, Y \in
\mathcal{C}$.
$F$ is called \textbf{essentially surjective} if every element of $\mathcal{D}$
is isomorphic to an object in the image of $F$. 
\end{definition} 

So, for instance, the inclusion of a full subcategory is fully faithful (by
definition). The forgetful functor from groups to sets is not fully faithful,
because not all functions between groups are automatically homomorphisms. 


\begin{proposition} 
A functor $F: \mathcal{C} \to \mathcal{D}$ induces an equivalence of categories
if and only if it is fully faithful and essentially surjective.
\end{proposition} 
\begin{proof} 
\add{this proof, and the definitions in the statement.}
\end{proof} 

\section{Various universal constructions}

Now that we have introduced the idea of a category and showed that a functor
takes isomorphisms to isomorphisms, we shall take various steps to characterize objects in terms of
maps (the most complete of which is the Yoneda lemma, \cref{yonedalemma}). In
general category
theory, this is generally all we \emph{can} do, since this is all the data we
are given.
We shall describe objects satisfying certain ``universal properties'' here.


As motivation, we first discuss the concept of the ``product'' in terms of a
universal property.

\subsection{Products}
Recall that if we have two sets $X$ and $Y$, the product $X\times Y$ is the set
of all elements of the form $(x,y)$ where $x\in X$ and $y\in Y$. The product is
also equipped with natural projections $p_1: X \times Y \to X$ and $p_2: X
\times Y \to Y$ that take $(x,y)$ to $x$
and $y$ respectively. Thus any element of $X\times Y$ is uniquely determined by
where they project to on $X$ and $Y$. In fact, this is the case more generally; if
we have an index set $I$ and a product $X=\prod_{i\in I} X_i$, then an element
$x\in X$ determined uniquely by where where the projections $p_i(x)$ land in
$X_i$. 

To get into the categorical spirit, we should speak not of elements but of maps
to $X$. Here is the general observation: if we have any other set $S$ with maps
$f_i:S\rightarrow X_i$ then there is a unique map $S\rightarrow X=\prod_{i\in
I}X_i$ given by sending $s\in S$ to the element $\{ f_i(s)\}_{i\in I}$. This
leads to the following characterization of a product using only ``mapping
properties.''

\begin{definition} Let $\{X_i\}_{i\in I}$ be a collection of objects in some
category $\mathcal{C}$. Then an object $P \in \mathcal{C}$ with projections $p_i: P\rightarrow X_i$
is said to be the \textbf{product} $\prod_{i\in I} X_i$ if the following ``universal
property'' holds:
let $S$ be any other object in $\mathcal{C}$ with maps $f_i:S\rightarrow X_i$.
Then there is a unique morphism $f:S\rightarrow P$ such that $p_i f = f_i$.
\end{definition}

In other words, to map into $X$ is the same as mapping into all the
$\left\{X_i\right\}$ at once. We have thus given a precise description of how
to map into $X$.
Note that, however, the product need not exist! 
If it does, however, we can express the above formalism by the following
natural isomorphism
of contravariant functors
\[ \hom(\cdot, \prod_I X_i) \simeq \prod_I \hom(\cdot, X_i).  \]
This is precisely the meaning of the last part of the definition. Note that
this observation shows that products in the category of \emph{sets} are really
fundamental to the idea of products in any category.

\begin{example} One of the benefits of this construction is that an actual
category is not specified; thus when we take $\mathcal{C}$ to be
$\mathbf{Sets}$, we
recover the cartesian product notion of sets, but if we take $\mathcal{C}$ to
be $\mathbf{Grp}$, we achieve the regular notion of the product of groups (the reader is
invited to check these statements). \end{example}

The categorical product is not unique, but it is as close to being so as
possible.

\begin{proposition}[Uniqueness of products]\label{produnique}
Any two products of the collection $\left\{X_i\right\}$ in $\mathcal{C}$ are
isomorphic by a unique isomorphism commuting with the projections.
\end{proposition} 

This is a special case of a general ``abstract nonsense'' type result that we
shall see many more of in the sequel.
The precise statement is the following: let $X$ be a product of the
$\left\{X_i\right\}$ with projections $p_i : X \to X_i$, and let $Y$ be a
product of them too, with projections $q_i: Y \to X_i$. 
Then the claim is that there is a \emph{unique} isomorphism
\[ f: X \to Y  \]
such that the diagrams below commute for each $i \in I$:
\begin{equation} \label{prodcommutative} \xymatrix{
X \ar[rd]^{p_i}  \ar[rr]^f &  & Y \ar[ld]_{q_i} \\
& X_i. 
}\end{equation}
\begin{proof} 
This is a ``trivial'' result, and is part of a general fact that objects
with the same universal property are always canonically isomorphic. Indeed, note that the projections $p_i: X \to
X_i$ and the fact that mapping into $Y$ is the same as mapping into all the
$X_i$ gives a unique map $f: X \to Y$ making the diagrams
\eqref{prodcommutative} commute. The same reasoning (applied to the $q_i: Y \to
X_i$) gives a map $g:  Y \to X$ making the diagrams
\begin{equation} \label{prodcommutative2} \xymatrix{
Y \ar[rd]^{q_i}  \ar[rr]^g &  & X \ar[ld]_{p_i} \\
& X_i 
}\end{equation}
commute. By piecing the two diagrams together, it follows that the composite $g \circ f$ makes the diagram
\begin{equation} \label{prodcommutative3} \xymatrix{
X \ar[rd]^{p_i}  \ar[rr]^{g \circ f} &  & X \ar[ld]_{p_i} \\
& X_i 
}\end{equation}
commute. 
But the identity $1_X: X \to X$ also would make \eqref{prodcommutative3}
commute, and the \emph{uniqueness} assertion in the definition of the product
shows that $g \circ f = 1_X$. Similarly, $f \circ g = 1_Y$. We are done.
\end{proof} 
\begin{remark}
 If we reverse the arrows in the above construction, 
the universal property obtained (known as the ``coproduct'') characterizes
disjoint unions in the category of sets and free products in the category of
groups.
That is, to map \emph{out} of a  coproduct of objects $\left\{X_i\right\}$ is the same as
mapping out of each of these. We shall later study this construction more
generally.
\end{remark}


\begin{exercise} 
Let $P$ be a poset, and make $P$ into a category as in \cref{posetcategory}.
Fix $x, y \in P$. Show that the \emph{product} of $x,y$ is the greatest lower 
bound of $\left\{x,y\right\}$ (if it exists). This claim holds more generally
for arbitrary subsets of $P$.

In particular, consider the poset of subsets of a given set $S$. Then the
``product'' in this category corresponds to the intersection of subsets.
\end{exercise} 

We shall, in this section, investigate this notion of ``universality''
more thoroughly.


\subsection{Initial and terminal objects}

We now introduce another example of universality, which is simpler but more
abstract than the products introduced in the previous section.

\begin{definition}
Let $\mathcal{C}$ be a category. An \textbf{initial object} in $\mathcal{C}$ is an
object $X \in \mathcal{C}$ with the property that $\hom_{\mathcal{C}}(X, Y)$ has one
element for all $Y \in \mathcal{C}$.

\end{definition}

So there is a unique map out of $X$ into each $Y \in \mathcal{C}$.
Note that this idea is faithful to the categorical spirit of describing objects
in terms of their mapping properties. Initial objects are very easy to map
\emph{out} of.


\begin{example}
If $\mathcal{C}$ is $\mathbf{Sets}$, then the empty set $\emptyset$ is an
initial object. There is a unique map from the empty set into any other set;
one has to make no decisions about where elements are to map when
constructing a map $\emptyset \to X$.
\end{example}

\begin{example} 
In the category $\mathbf{Grp}$ of groups, the group consisting of one element
is an initial object.
\end{example} 

Note that the initial object in $\mathbf{Grp}$ is \emph{not} that in
$\mathbf{Sets}$. This should not be too surprising, because $\emptyset$ cannot
be a group.

\begin{example} 
Let $P$ be a poset, and make it into a category as in \cref{posetcategory}.
Then it is easy to see that an initial object of $P$ is the smallest object in
$P$ (if it exists). Note that this is equivalently the product of all the
objects in $P$. In general, the initial object of a category is not the product
of all objects in $\mathcal{C}$ (this does not even make sense for a large
category).
\end{example} 

There is a dual notion, called a \textit{terminal object}, where every object
can map into it in precisely one way.
\begin{definition}
A \textbf{terminal object} in a category $\mathcal{C}$ is an object $Y \in
\mathcal{C}$ such that $\hom_{\mathcal{C}}(X, Y) = \ast$ for each $X \in \mathcal{C}$.
\end{definition}

Note that an initial object in $\mathcal{C}$ is the same as a terminal object
in $\mathcal{C}^{op}$, and vice versa. As a result, it suffices to prove 
results about initial objects, and the corresponding results for terminal
objects will follow formally.
But there is a fundamental difference between initial and terminal objects.
Initial objects are characterized by how one maps \emph{out of} them, while
terminal objects are characterized by how one maps \emph{into} them. 
\begin{example}
The one point set is a terminal object in $\mathbf{Sets}$.
\end{example}



The important thing about the next ``theorems'' is the conceptual framework.
\begin{proposition}[Uniqueness of the initial (or terminal) object]
\label{initialunique}
Any two initial (resp. terminal) objects in $\mathcal{C}$ are isomorphic by a
unique isomorphism.
\end{proposition}
\begin{proof}
The proof is easy. We do it for terminal objects. Say $Y, Y'$ are
terminal objects. Then $\hom(Y, Y')$ and $\hom(Y', Y)$ are one
point sets. So there are unique maps $f: Y \to Y', g: Y' \to Y$, whose composites
must be the identities: we know that $\hom(Y, Y) , \hom(Y', Y')$
are one-point sets, so the composites have no other choice to be the
identities. This means that the maps $f: Y \to Y', g: Y' \to Y$ are
isomorphisms.
\end{proof}

There is a philosophical point to be made here. We have characterized an object
uniquely in terms of mapping properties. We have characterized it
\emph{uniquely up to unique isomorphism,} which is really the best one can do
in mathematics. Two sets are not generally the ``same,'' but they may be
isomorphic up to unique isomorphism. They are different,
but the sets are isomorphic up
to unique isomorphism.
Note also that the argument was essentially similar to that of \cref{produnique}.

In fact, we could interpret  \cref{produnique} as a special case of
\cref{initialunique}.
If $\mathcal{C}$ is a category and $\left\{X_i\right\}_{i \in I}$ is a family
of objects in $\mathcal{C}$, then we can define a category $\mathcal{D}$ as
follows. An object of $\mathcal{D}$ is the data of an object $Y \in
\mathcal{C}$ and morphisms $f_i: Y \to X_i$ for all $i \in I$. 
A morphism between objects $(Y, \left\{f_i: Y \to X_i\right\})$ and $(Z,
\left\{g_i: Z \to X_i\right\})$ is 
a map $Y \to Z$ making the obvious diagrams commute. Then a product $\prod X_i$
in $\mathcal{C}$ is the same thing as a terminal object in $\mathcal{D}$, as
one easily checks from the definitions. 

\subsection{Push-outs and pull-backs}

Let $\mathcal{C}$ be a category.

Now we are going to talk about more  examples of universal constructions, which can all be
phrased via initial or terminal objects in some category. This,
therefore, is the proof for the uniqueness up to unique
isomorphism of \emph{everything} we will do in this
section. Later we will present these in more generality.


Suppose we have objects $A, B, C, X \in \mathcal{C}$. 

\begin{definition}
A commutative square 
\[
\xymatrix{
A \ar[d] \ar[r] &  B \ar[d] \\
C \ar[r] &  X}.
\]
is a \textbf{pushout square} (and $X$ is called the \textbf{push-out}) if,
given a commutative diagram
\[ \xymatrix{
A \ar[r] \ar[d]  &  B \ar[d] \\
C \ar[r] & Y  \\
}\]
there is a unique map $X \to Y$ making the following diagram commute:
\[
\xymatrix{
A \ar[d] \ar[r] &  B \ar[d] \ar[rdd] \\
C \ar[r] \ar[rrd] &  X \ar[rd] \\
& & Y'}
\]
Sometimes push-outs are also called \textbf{fibered coproducts}.
We shall also write $X = C \sqcup_A B$.
\end{definition}

In other words, to map out of $X = C \sqcup_A B$ into some object $Y$ is to
give maps $B \to Y, C \to Y$ whose restrictions to $A$ are the same.


The next few examples will rely on notions to be introduced later.
\begin{example}
The following is a pushout square in the category of abelian groups:
\[ \xymatrix{
\mathbb{Z}/2 \ar[r] \ar[d]  &  \mathbb{Z}/4 \ar[d]  \\
\mathbb{Z}/6 \ar[r] &  \mathbb{Z}/12
}\]
In the category of groups, the push-out is actually
$\mathrm{SL}_2(\mathbb{Z})$, though we do not prove it. The point is that
the property of a square's being a
push-out is actually dependent on the category.

In general, to construct a push-out of groups $C \sqcup_A B$, one constructs
the direct sum $C \oplus B$ and quotients by the subgroup generated by
$(a, a)$ (where $a \in A$ is identified with its image in $C \oplus B$).
We shall discuss this later, more thoroughly, for modules over a ring.
\end{example}

\begin{example}
Let $R$ be a commutative ring and let $S$ and $Q$ be two commutative
$R$-algebras. In other words, suppose
we have two maps of rings $s:R\rightarrow S$ and $q:R\rightarrow Q$. Then we
can fit this information together
into a pushout square:

\[ \xymatrix{
R \ar[r] \ar[d]  &  S \ar[d]   \\
Q \ar[r] &X
}\]
It turns out that the pushout in this case is the tensor product of algebras
$S\otimes_R Q$ (see \cref{tensprodalg} for the construction). This is particularly important
in algebraic geometry as the dual construction will give the correct notion of
``products'' in the category of ``schemes'' over
a field.\end{example}

\begin{proposition}
Let $\mathcal{C}$ be any category.
If the push-out of
the diagram
\[ \xymatrix{
A \ar[d] \ar[r] & B \\
C
}\]
exists, it is unique up to unique isomorphism.
\end{proposition}
\begin{proof}
We can prove this in two ways. One is to suppose that there were two pushout
squares:
\[
\xymatrix{
A \ar[d] \ar[r] &  B \ar[d]  \\
C \ar[r]  &  X \\
} 
\quad \quad
\xymatrix{
A \ar[d] \ar[r] &  B \ar[d]  \\
C \ar[r]  &  X' \\
} 
\]
Then there are unique maps $f:X \to X', g: X' \to X$ from the universal property.
In detail, these maps fit into commutative diagrams
\[
\xymatrix{
A \ar[d] \ar[r] &  B \ar[d] \ar[rdd] \\
C \ar[r] \ar[rrd]  &  X  \ar[rd]^f\\
 & & X'
} 
\quad \quad
\xymatrix{
A \ar[d] \ar[r] &  B \ar[d] \ar[rdd] \\
C \ar[r] \ar[rrd]  &  X' \ar[rd]^g\\
 & & X
} 
\]
Then $g \circ f$ and $f \circ g$ are the identities of $X, X'$ again by
\emph{uniqueness} of the map in the definition of the push-out. 

Alternatively, we can phrase push-outs in terms of initial objects. We could
consider the category of all diagrams as above,
\[ \xymatrix{
A \ar[d] \ar[r] &  B \ar[d]  \\
C \ar[r] &  D
},\]
where $A \to B, A \to C$ are fixed and $D$ varies. 
The morphisms in this category of diagrams consist of commutative
diagrams. Then the initial
object in this category is the push-out, as one easily checks.
\end{proof}

Often when studying categorical constructions, one can create a kind of
``dual''construction by reversing the direction of the arrows. This is exactly
the
relationship between the push-out construction and the pull-back
construction to be described below.
So suppose we have two morphisms $A \to C$ and $B\to C$, forming a diagram
\[ \xymatrix{
& B \ar[d] \\
A \ar[r] &  C.
}\]
\begin{definition}
The \textbf{pull-back} or \textbf{fibered product} of the above
diagram is an object $P$ with two morphisms $P\to B$ and $P\to
C$ such that the following diagram commutes:
\[ \xymatrix {
P \ar[d] \ar[r] & B \ar[d]\\
A\ar[r] & C }\]
Moreover, the object $P$ is required  to be universal in the following sense: given any $P'$
and maps $P'\to A$ and $P'\to B$ making the square commute, there is a
unique map
$P'\to P$ making the following diagram commute:
\[
\xymatrix{
 P' \ar[rd] \ar[rrd] \ar[ddr] \\
& P \ar[d] \ar[r] &  B \ar[d] \\
& A \ar[r] &  C }\]
We shall also write $P = B \times_C A$.
\end{definition}


\begin{example} 
In the category $\mathbf{Set}$ of sets, if we have sets $A, B, C$ with maps $f:
A \to C, g: B \to C$, then the fibered product $A \times_C B$ consists of
pairs $(a,b) \in A \times B$ such that $f(a) = g(b)$.  
\end{example} 

\begin{example}[Requires prerequisites not developed yet] The next example may
be omitted without loss of continuity.

As said above, the fact that the tensor product of algebras is
a push-out in the category of
commutative $R$-algebras allows for the correct notion of the ``product'' of
schemes. We now elaborate on this example: naively one would think that we
could pick the underlying space of the product scheme to just be the topological
product of two Zariski topologies. However, it is an easy exercise to check
that the product of two Zariski topologies in general is not Zariski! This
motivates
the need for a different concept.

Suppose we have a field $k$ and two $k$-algebras $A$ and $B$ and let
$X=\spec(A)$and $Y=\spec(B)$ be the affine $k$-schemes corresponding to $A$ and
$B$. Consider the following pull-back diagram:
\[
\xymatrix{
X\times_{\spec(k)} Y \ar[d] \ar[r] &X \ar[d]\\
Y \ar[r] &\spec(k) }\]

Now, since $\spec$ is a contravariant functor, the arrows in this pull-back
diagram have been flipped; so in fact, $X\times_{\spec(k)} Y$ is actually
$\spec(A\otimes _k B)$. This construction is motivated by the following example:
let $A=k[x]$ and $B=k[y]$. Then $\spec(A)$ and $\spec(B)$ are both affine lines
$\mathbb{A}^1_k$ so we want a suitable notion of product that makes the product
of $\spec(A)$ and $\spec(B)$ the affine plane. The pull-back construction is the
correct one since $\spec(A)\times_{\spec(k)} \spec(B)=\spec(A\otimes_k
B)=\spec(k[x,y])=\mathbb{A}^2_k$.
\end{example}


\subsection{Colimits}


We now want to generalize the push-out.
Instead of a shape with $A,B,C$, we do something more general.
Start with a small category $I$: recall that \emph{smallness} means that the objects of $I$
form a set. $I$ is to be called  the  \textbf{indexing
category}. One is supposed to picture
is that $I$ is something like the category
\[
\xymatrix{
\ast \ar[d] \ar[r] &  \ast \\
\ast
}
\]
or the category
\[ \ast \rightrightarrows \ast.  \]
We will formulate the notion of a \textbf{colimit} which will specialize to the
push-out when $I$ is the first case. 


So we will look at functors
\[ F: I \to \mathcal{C},  \]
which in the case of the three-element category, will just
 correspond to
diagrams
\[ \xymatrix{A \ar[d]  \ar[r] &  B \\ C}.  \]

We will call a \textbf{cone} on $F$ (this is an ambiguous term) an object $X
\in \mathcal{C}$ equipped with maps $F_i \to X, \forall i \in I$ such that for
all maps $i \to
i' \in I$, the diagram below commutes:
\[ \xymatrix{
F_i \ar[d] \ar[r] &  X \\
F_{i'} \ar[ru]
}.\]

An example would be a cone on the three-element category above: then
this is just a commutative diagram
\[ \xymatrix{
A \ar[r]\ar[d]  &  B \ar[d]  \\
C \ar[r] &  D
}.\]

\newcommand{\colim}{\mathrm{colim}}

\begin{definition}
The \textbf{colimit} of the diagram $F: I \to \mathcal{C}$, written as $\colim
F$ or $\colim_I F $ or $\varinjlim_I F$, if it exists, is a cone $F \to X$ with
the property that if $F \to Y$ is any other cone, then there is a unique map $X
\to Y$ making the diagram
\[ \xymatrix{
F  \ar[rd] \ar[r] &  X \ar[d]  \\
& Y
}\]
commute. (This means that the corresponding diagram with $F_i$ replacing $F$
commutes for each $i \in I$.)
\end{definition}

We could form a category $\mathcal{D}$ where the objects are the cones $F \to
X$, and the morphisms from $F \to X$ and $F \to Y$ are the maps $X \to Y$ that
make all the obvious diagrams commute. In this case, it is easy to see that a
\emph{colimit} of the diagram is just an initial object in $\mathcal{D}$.

 In any case, we see:

\begin{proposition}
$\colim F$, if it exists, is unique up to unique isomorphism.
\end{proposition}

Let us go through some examples. We already looked at push-outs.

\begin{example}
Consider the category $I$ visualized as
\[ \ast, \ast, \ast, \ast.  \]
So $I$ consists of four objects with no non-identity morphisms.
A functor $F: I \to \mathbf{Sets}$ is just a list of four sets $A, B, C, D$.
The colimit is just the disjoint union $A \sqcup B \sqcup C \sqcup D$. This is
the universal property of the disjoint union. To map out of the disjoint union
is the same thing as mapping out of each piece.
\end{example}


\begin{example}
Suppose we had the same category $I$ but the functor $F$ took values in the
category of abelian groups. Then $F$
corresponds, again, to a list of four abelian groups. The colimit is the direct
sum. Again, the direct sum is characterized by the same universal property.
\end{example}

\begin{example}
Suppose we had the same $I$ ($\ast, \ast, \ast, \ast$) the functor took its
value in the category of groups. Then the colimit is the
free product of the four groups.
\end{example}

\begin{example}
Suppose we had the same $I$ and the category $\mathcal{C}$ was of commutative
rings with unit. Then the colimit is the tensor product.
\end{example}

So the idea of a colimit unifies a whole bunch of constructions.
Now let us take a different example.

\begin{example}
Take
\[ I = \ast \rightrightarrows \ast.  \]
So a functor $I \to \mathbf{Sets}$ is a diagram
\[ A \rightrightarrows B.  \]
Call the two maps $f,g: A \to B$. To get the colimit, we take $B$ and mod out
by the equivalence relation generated by $f(a) \sim g(a)$.
To hom out of this is the same thing as homming  out of $B$ such that the
pullbacks to $A$ are the same.

This is the relation \textbf{generated} as above, not just as above. It can get
tricky.
\end{example}

\begin{definition}
When $I$ is just a bunch of points  $\ast, \ast, \ast, \dots$ with no
non-identity morphisms, then the
colimit over $I$ is called the \textbf{coproduct}.
\end{definition}

We use the coproduct to mean things like direct sums, disjoint unions, and
tensor products.
If $\left\{A_i, i \in I\right\}$ is a collection of objects in some category,
then we find the universal property of the coproduct can be stated succinctly:
\[ \hom_{\mathcal{C}}(\bigsqcup_I A_i, B) = \prod \hom_{\mathcal{C}}(A_i, B).  \]

\begin{definition}
When $I$ is $\ast \rightrightarrows \ast$, the colimit is called the
\textbf{coequalizer}.
\end{definition}

\begin{theorem} \label{coprodcoequalsufficeforcocomplete}
If $\mathcal{C}$ has all coproducts and coequalizers, then it has all colimits.
\end{theorem}

\begin{proof}
Let $F: I \to \mathcal{C}$ be a functor, where $I$ is a small category. We
need to obtain an object $X$ with morphisms
\[ Fi \to X, \quad i \in I  \]
such that for each $f: i \to i'$, the diagram below commutes:
\[
\xymatrix{
Fi \ar[d] \ar[r] &  Fi' \ar[ld] \\
X
}
\]
and such that $X$ is universal among such diagrams.

To give such a diagram, however, is equivalent to giving a collection of maps
\[ Fi \to X  \]
that satisfy some conditions. So $X$ should be thought of as a quotient of the
coproduct $\sqcup_i Fi$.
Let us consider the coproduct $\sqcup_{i \in I, f} Fi$, where $f$ ranges over
all
morphisms in the category $I$ that start from $i$.
We construct two maps
\[ \sqcup_f Fi \rightrightarrows \sqcup_f Fi,  \]
whose coequalizer will be that of $F$. The first map is the identity. The
second map sends a factor
\end{proof}

\subsection{Limits}
As in the example with pull-backs and push-outs and products and coproducts,
one can define a limit by using the exact same universal property above
just with
all the arrows reversed.

\begin{example} The product is an example of a limit where the indexing
category is a small category $I$ with no morphisms other than the identity. This
example
shows the power of universal constructions; by looking at colimits and limits,
a whole variety of seemingly unrelated mathematical constructions are shown
to be
in the same spirit.
\end{example}

\subsection{Filtered colimits}


\emph{Filtered colimits} are colimits
over special indexing categories $I$ which look like totally ordered sets.
These have several convenient properties as compared to general colimits.
For instance, in the category of \emph{modules} over a ring (to be studied in
\rref{foundations}), we shall see that filtered colimits actually
preserve injections and surjections. In fact, they are \emph{exact.} This is
not true in more general categories which are similarly structured.



\begin{definition}
An indexing category is \textbf{filtered} if the following hold:
\begin{enumerate}
\item Given $i_0, i_1 \in I$, there is a third object $i \in I$ such that both
$i_0, i_1$ map into $i$.
So there is a diagram
\[ \xymatrix{
i_0 \ar[rd] \\
& i \\
i_1 \ar[ru]
}.\]
\item Given any two maps $i_0 \rightrightarrows i_1$, there exists $i$ and $i_1
\to i$ such that the two maps $i_0 \rightrightarrows i$ are equal:
intuitively, any two ways
of pushing an object into another can be made into the same eventually.
\end{enumerate}
\end{definition}

\begin{example}
If $I$ is the category
\[ \ast \to \ast \to \ast \to \dots,  \]
i.e. the category generated by the poset $\mathbb{Z}_{\geq 0}$, then that is
filtered.
\end{example}


\begin{example}
If $G$ is a torsion-free abelian group, the category $I$ of finitely generated
subgroups of $G$ and inclusion maps is filtered. We don't actually need the
lack of torsion.
\end{example}

\begin{definition}
Colimits over a filtered category are called \textbf{filtered colimits}.
\end{definition}

\begin{example}
Any torsion-free abelian group is the filtered colimit of its finitely
generated subgroups, which are free abelian groups.
\end{example}
This gives a simple approach for showing that a torsion-free abelian group is
flat.

\begin{proposition}
If $I$ is filtered\footnote{Some people say filtering.} and $\mathcal{C} =
\mathbf{Sets}, \mathbf{Abgrp}, \mathbf{Grps}$, etc., and $F: I \to \mathcal{C}$
is a functor, then $\colim_I F$ exists and is given by the disjoint union of
$F_i, i \in I$ modulo the relation $x \in F_i$ is equivalent to $x' \in F_{i'}$
if $x$ maps to $x'$ under $F_i \to F_{i'}$. This is already an equivalence
relation.
\end{proposition}

The fact that the relation given above is transitive uses the filtering of the
indexing set. Otherwise, we would need to use the relation generated by it.

\begin{example}
Take $\mathbb{Q}$. This is the filtered colimit of the free submodules
$\mathbb{Z}(1/n)$.

Alternatively, choose a sequence of numbers $m_1 , m_2, \dots, $ such that for
all $p, n$, we have $p^n \mid m_i$ for $i \gg 0$. Then we have a sequence of
maps
\[ \mathbb{Z} \stackrel{m_1}{\to} \mathbb{Z} \stackrel{m_2}{\to}\mathbb{Z}
\to \dots.   \]
The colimit of this is $\mathbb{Q}$. There is a quick way of seeing this, which
is left to the reader.
\end{example}

When we have a functor $F: I \to \mathbf{Sets}, \mathbf{Grps},
\mathbf{Modules}$ taking values in a ``nice'' category (e.g. the category of
sets, modules, etc.), one can construct the colimit by taking the union of the
$F_i, i \in I$ and quotienting by the equivalence relation $x \in F_i \sim x'
\in F_{i'}$ if $f: i \to i'$ sends $x$ into $x'$. This is already an
equivalence relation, as one can check.

Another way of saying this is that we have the disjoint union of the $F_i$
modulo the relation that $a \in F_i$ and $b \in F_{i'}$ are equivalent if and
only if there is a later $i''$ with maps $i \to i'', i' \to i''$ such that
$a,b$ both map to the same thing in $F_{i''}$.


One of the key properties of filtered colimits is that, in ``nice'' categories they commute with
finite limits.

\begin{proposition} 
In the category of sets, filtered colimits and finite limits commute with each
other.
\end{proposition} 

The reason this result is so important is that, as we shall see, it will imply
that in categories such as the category of $R$-modules, filtered colimits
preserve \emph{exactness}. 
\begin{proof} 
Let us show that filtered colimits commute with (finite) products in the
category of sets. The case of an equalizer is similar, and finite limits can be
generated from products and equalizers.

So let $I$ be a filtered category, and $\left\{A_i\right\}_{i \in I},
\left\{B_i\right\}_{i \in I}$
be functors from $I \to \mathbf{Sets}$. 
We want to show that 
\[ \varinjlim_I (A_i \times B_i) = \varinjlim_I A_i \times \varinjlim_I B_i . \]
To do this, note first that there is a map in the direction $\to$ because of
the natural maps $\varinjlim_I (A_i \times B_i) \to \varinjlim_I A_i$ and
$\varinjlim_I (A_i \times B_i) \to \varinjlim_I B_i$.
We want to show that this is an isomorphism.

Now we can write the left side as the disjoint union $\bigsqcup_I (A_i \times
B_i)$ modulo the equivalence relation that $(a_i, b_i)$ is related to $(a_j,
b_j)$ if there exist morphisms $i \to k, j \to k$ sending $(a_i, b_i), (a_j,
b_j)$ to the same object in $A_k \times B_k$.
For the left side, we have to work with pairs: that is, an element of 
 $\varinjlim_I A_i \times \varinjlim_I B_i$ consists of a pair $(a_{i_1},
 b_{i_2})$
 with two pairs $(a_{i_1}, b_{i_2}), (a_{j_1}, b_{j_2})$ equivalent if there exist
 morphisms $i_1,j_1 \to k_1 $ and $i_2,  j_2 \to k_2$ such that both have the
 same image in $A_{k_1} \times A_{k_2}$. It is easy to see that these amount to
 the same thing, because of the filtering condition: we can always modify an
 element of $A_{i} \times B_{j}$ to some $A_{k} \times B_k$ for $k$ receiving
 maps from $i, j$.
\end{proof} 

\begin{exercise} 
Let $A$ be an abelian group, $e: A \to A$ an \emph{idempotent} operator, i.e.
one such that $e^2 = e$. Show that $eA$ can be obtained as the filtered colimit
of 
\[ A \stackrel{e}{\to} A \stackrel{e}{\to} A \dots.  \]
\end{exercise} 

\subsection{The initial object theorem}

We now prove a fairly nontrivial result, due to Freyd. This gives a sufficient
condition for the existence of initial objects.
We shall use it in proving the adjoint functor theorem below.

Let $\mathcal{C}$ be a category. Then we recall that $A \in \mathcal{C}$ if
for each $X \in \mathcal{C}$, there is a \emph{unique} $A \to X$.
Let us consider the weaker condition that for each $ X \in \mathcal{C}$, there
exists \emph{a} map $A \to X$.

\begin{definition} Suppose $\mathcal{C}$ has equalizers.
If $A \in \mathcal{C}$ is such that $\hom_{\mathcal{C}}(A, X) \neq \emptyset$
for each $X \in \mathcal{C}$, then $X$ is called \textbf{weakly initial.}
\end{definition}

We now want to get an initial object from a weakly initial object.
To do this, note first that if $A$ is weakly initial and $B$ is any object
with a morphism $B \to A$, then $B$ is weakly initial too. So we are going to
take
our initial object to be a very small subobject of $A$.
It is going to be so small as to guarantee the uniqueness condition of an
initial object. To make it small, we equalize all endomorphisms.

\begin{proposition} \label{weakinitial}
If  $A$ is a weakly initial object in $\mathcal{C}$,
then the equalizer of all endomorphisms $A \to A$ is initial for $\mathcal{C}$.
\end{proposition}
\begin{proof}
Let $A'$ be this equalizer; it is endowed with a morphism $A'\to A$. Then let
us recall what this means. For any two
endomorphisms $A \rightrightarrows A$, the two pull-backs $A'
\rightrightarrows A$ are equal. Moreover, if $B \to A$ is a morphism that has
this property, then $B$ factors uniquely through $A'$.

Now $A' \to A$ is a morphism, so by the remarks above, $A'$ is weakly initial:
to each $X \in \mathcal{C}$, there exists a morphism $A' \to X$.
However, we need to show that it is unique.

So suppose given two maps $f,g: A' \rightrightarrows X$. We are going to show
that they are equal. If not, consider their equalizer $O$.
Then we have a morphism $O \to A'$ such that the post-compositions with $f,g$
are equal. But by weak initialness, there is a map $A \to O$; thus we get a
composite
\[ A \to O \to A'.  \]
We claim that this is a \emph{section} of the embedding $A'\to A$.
This will prove the result. Indeed, we will have constructed a section $A \to
A'$, and since it factors through $O$, the two maps
\[ A \to O \to A' \rightrightarrows X  \]
are equal. Thus, composing each of these with the inclusion $A' \to A$ shows
that $f,g$ were equal in the first place.

Thus we are reduced to proving:
\begin{lemma}
Let $A$ be an object of a category $\mathcal{C}$. Let $A'$ be the equalizer of
all endomorphisms of $A$. Then any morphism $A \to A'$ is a section of the
inclusion $A' \to A$.
\end{lemma}
\begin{proof}
Consider the canonical inclusion $i: A' \to A$. We are given some map $s: A
\to A'$; we must show that $si = 1_{A'}$.
Indeed, consider the composition
\[ A' \stackrel{i}{\to} A \stackrel{s}{\to} A' \stackrel{i}{\to} A .\]
Now $i$ equalizes endomorphisms of $A$; in particular, this composition is the
same as
\[ A' \stackrel{i}{\to} A \stackrel{\mathrm{id}}{\to} A; \]
that is, it equals $i$. So the map $si: A' \to A$ has the property that $isi =
i$ as maps $A' \to A$. But $i$ being a monomorphism, it follows that $si  =
1_{A'}$.
\end{proof}
\end{proof}

\begin{theorem}[Freyd] \label{initialobjectthm}
Let $\mathcal{C}$ be a category admitting all small limits.\footnote{We shall
later call such a category \textbf{complete}.} Then $\mathcal{C}$ has an initial
object if and only if the following \textbf{solution set condition holds:}
there is a set $\left\{X_i, i \in I\right\}$ of objects in $\mathcal{C}$ such
that any $X \in \mathcal{C}$ can be mapped into by one of these.
\end{theorem}

The idea is that the family $\left\{X_i\right\}$ is somehow weakly universal
\emph{together.}
\begin{proof}
If $\mathcal{C}$ has an initial object, we may just consider that as the
family $\left\{X_i\right\}$: we can hom out (uniquely!) from a universal
object into anything, or in other words a universal object is weakly universal.

Suppose we have a ``weakly universal family'' $\left\{X_i\right\}$. Then the
product $\prod X_i$ is weakly universal. Indeed, if $X \in \mathcal{C}$,
choose some $i'$ and a morphism $X_{i'} \to X$ by the hypothesis. Then this map
composed with the projection from the product gives a map  $\prod X_i \to
X_{i'} \to X$.
\cref{weakinitial} now implies that $\mathcal{C}$ has an initial object.
\end{proof}

\subsection{Completeness and cocompleteness}
\begin{definition}\label{completecat} A category $\mathcal{C}$ is said to be \textbf{complete} if for every
functor $F:I\rightarrow \mathcal{C}$ where $I$ is a small category, the limit
$\lim F$ exists (i.e. $\mathcal{C}$ has all small limits). If all colimits exist, then $\mathcal{C}$ is said to be
\textbf{cocomplete}.
\end{definition}

If a category is complete, various nice properties hold.
\begin{proposition} If $\mathcal{C}$ is a complete category, the following
conditions are true:
\begin{enumerate}
\item{all (finite) products exist}
\item{all pull-backs exist}
\item{there is a terminal object}
\end{enumerate}
\end{proposition}
\begin{proof} The proof of the first two properties is trivial since they can
all be expressed as limits; for the proof of the existence of a terminal
object, consider the empty diagram $F:\emptyset \rightarrow \mathcal{C}$. Then
the
terminal object is just $\lim F$.
\end{proof}

Of course, if one dualizes everything we get a theorem about cocomplete
categories which is proved in essentially the same manner. More is true
however; it turns out that finite (co)completeness are equivalent to the
properties above if one requires the finiteness condition for the existence of
(co)products.

\subsection{Continuous and cocontinuous functors}
\subsection{Monomorphisms and epimorphisms}
We now wish to characterize monomorphisms and epimorphisms in a purely
categorical setting. In categories where there is an underlying set the notions
of injectivity and surjectivity makes sense but in category theory, one
does not
in a sense have ``access'' to the internal structure of objects. In this light,
we make the following definition.

\begin{definition}
A morphism $f:X \to Y$ is a \textbf{monomorphism} if for any two morphisms
$g_1:X'\rightarrow X$ and $g_2:X'\rightarrow X$, we have that $f g_1 = f g_2$
implies $g_1=g_2$. A morphism $f:X\rightarrow Y$ is an \textbf{epimorphism} if for any two
maps $g_1:Y\rightarrow Y'$ and $g_2:Y\rightarrow Y'$, we have that $g_1 f = g_2
f$ implies $g_1 = g_2$.
\end{definition}

So $f: X \to Y$ is a monomorphism if whenever $X'$ is another object in
$\mathcal{C}$, the map
\[ \hom_{\mathcal{C}}(X', X) \to \hom_{\mathcal{C}}(X', Y)  \]
is an injection (of sets). Epimorphisms in a category are defined similarly;
note that neither definition makes any reference to \emph{surjections} of sets.


The reader can easily check:

\begin{proposition}  \label{compositeofmono}
The composite of two monomorphisms is a monomorphism, as is the composite of
two epimorphisms.
\end{proposition} 

\begin{exercise} 
Prove \cref{compositeofmono}. 
\end{exercise} 


\begin{exercise} 
The notion of ``monomorphism'' can be detected using only the notions of
fibered product and isomorphism. To see this, suppose $i: X \to Y$ is a
monomorphism. Show that the diagonal
\[ X \to X \times_Y X  \]
is an isomorphism. (The diagonal map is such that the two
projections to $X$ both give the identity.) Conversely, show that if $i: X \to Y$ is any morphism such
that the above diagonal map is an isomorphism, then $i$ is a monomorphism.

Deduce the following consequence: if $F: \mathcal{C} \to \mathcal{D}$ is a
functor that commutes with fibered products, then $F $ takes monomorphisms to
monomorphisms.
\end{exercise} 


\section{Yoneda's lemma}

\add{this section is barely fleshed out}

Let $\mathcal{C}$ be a category.
In general, we have said that there is no way to study an object in  a
category other than by considering maps into and out of it.
We will see that essentially everything about $X \in \mathcal{C}$ can be
recovered from these hom-sets.
We will thus get an embedding of $\mathcal{C}$ into a category of functors.

\subsection{The functors $h_X$}

We now use the structure of a category to construct hom functors.
\begin{definition}
Let $X \in \mathcal{C}$. We define the contravariant functor $h_X: \mathcal{C}
\to \mathbf{Sets}$ via
\[ h_X(Y) = \hom_{\mathcal{C}}(Y, X).  \]
\end{definition}

This is, indeed, a functor. If $g: Y \to Y'$, then precomposition gives a map
of sets
\[ h_X(Y') \to h_X(Y),  \quad f \mapsto f \circ g \]
which satisfies all the usual identities.

As a functor, $h_X$ encodes \emph{all} the information about
how one can map into $X$.
It turns out that one can basically recover $X$ from $h_X$, though.

\subsection{The Yoneda lemma}

Let $X \stackrel{f}{\to} X'$ be a morphism in $\mathcal{C}$.
Then for each $Y \in \mathcal{C}$, composition gives a map
\[ \hom_{\mathcal{C}}(Y, X) \to \hom_{\mathcal{C}}(Y, X').  \]
It is easy to see that this induces a \emph{natural} transformation
\[ h_{X} \to h_{X'}.  \]
Thus we get a map of sets
\[ \hom_{\mathcal{C}}(X, X') \to \hom(h_X, h_{X'}),  \]
where $h_X, h_{X'}$ lie in the category of contravariant functors $\mathcal{C}
\to \mathbf{Sets}$.
In other words, we have defined a \emph{covariant functor}
\[ \mathcal{C} \to \mathbf{Fun}(\mathcal{C}^{op}, \mathbf{Sets}).  \]
This is called the \emph{Yoneda embedding.} The next result states that the
embedding is fully faithful.

\begin{theorem}[Yoneda's lemma]
\label{yonedalemma}
If $X, X' \in \mathcal{C}$, then the map
$\hom_{\mathcal{C}}(X, X') \to \hom(h_X, h_{X'})$ is a bijection. That is,
every natural transformation $h_X \to h_{X'}$ arises in one and only one way
from a morphism $X \to X'$.
\end{theorem}


\begin{theorem}[Strong Yoneda lemma]
\end{theorem}

\subsection{Representable functors}

We use  the same notation of the preceding section: for a category
$\mathcal{C}$ and $X \in \mathcal{C}$, we let $h_X$ be the contravariant
functor $\mathcal{C} \to \mathbf{Sets}$ given by $Y \mapsto
\hom_{\mathcal{C}}(Y, X)$.
\begin{definition}
A contravariant functor $F: \mathcal{C} \to \mathbf{Sets}$ is
\textbf{representable} if it is naturally isomorphic to some $h_X$.
\end{definition}

The point of a representable functor is that it can be realized as maps into a
specific object.
In fact, let us look at a specific feature of the functor $h_X$.
Consider the object $\alpha \in h_X(X)$ that corresponds to the identity.
Then any morphism
\[ Y \to X  \]
factors \emph{uniquely}
as \[ Y \to X \stackrel{\alpha}{\to } X  \]
(this is completely trivial!) so that
any element of $h_X(Y)$ is a $f^*(\alpha)$ for precisely one $f:  Y \to X$.

\begin{definition}
Let $F: \mathcal{C} \to \mathbf{Sets}$ be a contravariant functor. A
\textbf{universal object} for $\mathcal{C}$ is a pair $(X, \alpha)$ where $X
\in \mathcal{C}, \alpha \in F(X)$ such that the following condition holds:
if $Y$ is any object and $\beta \in F(Y)$, then there is a unique $f: Y \to X$
such that $\alpha$ pulls back to $\beta$ under $f$.

In other words, $\beta = f^*(\alpha)$.
\end{definition}

So a functor has a universal object if and only if it is representable.
Indeed, we just say that the identity $X \to X$ is universal for $h_X$, and
conversely if $F$ has a universal object $(X, \alpha)$, then $F$ is naturally
isomorphic to $h_X$ (the isomorphism $h_X \simeq F$ being given by pulling
back $\alpha$ appropriately).


The article \cite{Vi08} by Vistoli contains a good introduction to and several
examples of this theory.
Here is one of them:

\begin{example}
Consider the contravariant functor $F: \mathbf{Sets} \to \mathbf{Sets}$ that
sends any set $S$ to its power set $2^S$ (i.e. the collection of subsets).
This is a contravariant functor: if $f: S \to T$, there is a morphism
\[ 2^T \to 2^S, \quad T' \mapsto f^{-1}(T').  \]

This is a representable functor. Indeed, the universal object can be taken as
the pair
\[ ( \left\{0,1\right\}, \left\{1\right\}).  \]

To understand this, note that a subset $S;$ of $S$ determines its
\emph{characteristic function} $\chi_{S'}: S \to \left\{0,1\right\}$ that
takes the value $1$ on $S$ and $0$ elsewhere.
If we consider $\chi_{S'}$ as a morphism $ S \to \left\{0,1\right\}$, we see
that
\[ S' = \chi_{S'}^{-1}(\{1\}).  \]
Moreover, the set of subsets is in natural bijection with the set of
characteristic functions, which in turn are precisely \emph{all} the maps $S
\to \left\{0,1\right\}$. From this the assertion is clear.
\end{example}

We shall meet some elementary criteria for the representability of
contravariant functors in the next subsection. For now, we note\footnote{The
reader unfamiliar with algebraic topology may omit these remarks.} that in
algebraic topology, one often works with the \emph{homotopy category} of
pointed CW complexes (where morphisms are pointed continuous maps modulo
homotopy), any contravariant functor that satisfies two relatively mild
conditions (a
Mayer-Vietoris condition and a condition on coproducts), is automatically
representable by a theorem of Brown. In particular, this implies that the
singular cohomology functors $H^n(-, G)$ (with coefficients in some group $G$)
are representable; the representing objects are the so-called
Eilenberg-MacLane spaces  $K(G,n)$.  See \cite{Ha02}.


\subsection{Limits as representable functors}

\add{}

\subsection{Criteria for representability}

Let $\mathcal{C}$ be a category.
We saw in the previous subsection that a representable functor must send
colimits to limits. 
We shall now see that there is a converse under certain set-theoretic
conditions.
For simplicity, we start by stating the result for corepresentable functors.

\begin{theorem}[(Co)representability theorem]
Let $\mathcal{C}$ be a complete category, and let $F: \mathcal{C} \to
\mathbf{Sets}$ be a covariant functor. Suppose $F$ preserves limits and satisfies the solution set condition: 
there is a set of objects $\left\{Y_\alpha\right\}$ such that, for any $X \in
\mathcal{C}$ and $x \in F(X)$, there is a morphism
\[ Y_\alpha \to X  \]
carrying some element of $F(Y_\alpha)$ onto $x$.

Then $F$ is corepresentable.
\end{theorem} 
\begin{proof} 
To $F$, we associate the following \emph{category} $\mathcal{D}$. An object of
$\mathcal{D}$ is a pair $(x, X)$ where $x \in F(X)$ and $X \in \mathcal{C}$.
A morphism between $(x, X)$ and $(y, Y)$ is a map
\[ f:X \to Y  \]
that sends $x$ into $y$ (via $F(f): F(X) \to F(Y)$).
It is easy to see that $F$ is corepresentable if and only if there is an initla
object in this category; this initial object is the ``universal object.''

We shall apply the initial object theorem, \cref{initialobjectthm}. Let us first verify that
$\mathcal{D}$ is complete; this follows because $\mathcal{C}$ is and $F$
preserves limits. So, for instance, the product of $(x, X)$ and $(y, Y)$ is
$((x,y), X \times Y)$; here $(x,y)$ is the element of $F(X) \times F(Y) = F(X
\times Y)$.
The solution set condition states that there is a weakly 
initial family of objects, and the initial object theorem now implies that
there is an initial object. 
\end{proof} 
\section{Adjoint functors}

According to MacLane, ``Adjoint functors arise everywhere.'' We shall see
several examples of adjoint functors in this book (such as $\hom$ and the
tensor product). The fact that a functor has an adjoint often immediately
implies useful properties about it (for instance, that it commutes with either
limits or colimits); this will lead, for instance, to conceptual arguments
behind the right-exactness of the tensor product later on.


\subsection{Definition}

Suppose $\mathcal{C}, \mathcal{D}$ are categories, and let $F: \mathcal{C} \to
\mathcal{D}, G: \mathcal{D} \to \mathcal{C}$ be (covariant) functors.

\begin{definition} 
$F, G$ are \textbf{adjoint functors} if there is a natural isomorphism
\[ \hom_{\mathcal{D}}(Fc, d) \simeq \hom_{\mathcal{C}}(c, Gd)  \]
whenever $c \in \mathcal{C}, d \in \mathcal{D}$. $F$ is said to be the
\textbf{right adjoint,} and $G$ is the \textbf{left adjoint.}
\end{definition} 

Here ``natural'' means that the two quantities are supposed to be considered
as functors $\mathcal{C}^{op} \times \mathcal{D} \to \mathbf{Set}$.

\begin{example} 
There is a simple pair of adjoint functors between $\mathbf{Set}$ and $\mathbf{AbGrp}$. Here
$F$ sends  a set $A$ to the free abelian group (see \cref{} for a discussion
of free modules over arbitrary rings) $\mathbb{Z}[A]$, while $G$ is
the ``forgetful'' functor that sends an abelian group to its underlying set. 
Then $F$ and $G$ are adjoints. That is, to give a group-homomorphism
\[ \mathbb{Z}[A] \to G  \]
for some abelian group $G$ 
is the same as giving a map of \emph{sets}
\[ A \to G.  \]
This is precisely the defining property of the free abelian group.
\end{example} 

\begin{example}
In fact, most ``free'' constructions are just left adjoints.
For instance, recall the universal property of the free group $F(S)$ on a set $S$ (see
\cite{La02}): to give a group-homomorphism $F(S) \to G$ for $G$ any group is
the same as choosing an image in $G$ of each $s \in S$.
That is,
\[ \hom_{\mathbf{Grp}}(F(S), G) = \hom_{\mathbf{Sets}}(S, G).  \]
This states that the free functor $S \mapsto F(S)$ is left adjoint to the
forgetful functor from $\mathbf{Grp}$ to $\mathbf{Sets}$.
\end{example}

\begin{example} 
The abelianization functor $G \mapsto G^{ab} = G/[G, G]$ from $\mathbf{Grp}
\to \mathbf{AbGrp}$ is left adjoint to the
inclusion $\mathbf{AbGrp} \to \mathbf{Grp}$.
That is, if $G$ is a group and $A$ an abelian group, there is  a natural
correspondence between homomorphisms $G \to A$ and $G^{ab} \to A$.
Note that $\mathbf{AbGrp}$ is a subcategory of $\mathbf{Grp}$ such that the
inclusion admits a left adjoint; in this situation, the subcategory is called
\textbf{reflective.}
\end{example} 



\subsection{Adjunctions}

The fact that two functors are adjoint is encoded by a simple set of algebraic
data between them. 
To see this, suppose $F: \mathcal{C} \to \mathcal{D}, G: \mathcal{D} \to \mathcal{C}$ are
adjoint functors. 
For any object $c \in \mathcal{C}$, we know that
\[ \hom_{\mathcal{D}}(Fc, Fc) \simeq \hom_{\mathcal{C}}(c, GF c),  \]
so that the identity morphism $Fc \to Fc$ (which is natural in $c$!) corresponds to a map $c \to GFc$
that is natural in $c$, or equivalently a natural
transformation
\[ \eta: 1_{\mathcal{C}} \to GF. \]
Similarly, we get a natural transformation
\[ \epsilon:  FG \to 1_{\mathcal{D}}  \]
where the map $FGd \to d$ corresponds to the identity $Gd \to Gd$ under the
adjoint correspondence.
Here $\eta$ is called the \textbf{unit}, and $\epsilon$ the \textbf{counit.}

These natural transformations $\eta, \epsilon$ are not simply arbitrary.
We are, in fact, going to show that they determine the isomorphism
determine the isomorphism $\hom_{\mathcal{D}}(Fc, d) \simeq
\hom_{\mathcal{C}}(c, Gd)$. This will be a little bit of diagram-chasing.

We know that the isomorphism $\hom_{\mathcal{D}}(Fc, d) \simeq
\hom_{\mathcal{C}}(c, Gd)$ is \emph{natural}. In fact, this is the key point.
Let $\phi: Fc \to d$ be any map.
Then there is a morphism $(c, Fc) \to (c, d) $ in the product category
$\mathcal{C}^{op} \times \mathcal{D}$; by naturality of the adjoint
isomorphism, we get a commutative square of sets
\[ \xymatrix{
\hom_{\mathcal{D}}(Fc, Fc) \ar[r]^{\mathrm{adj}}  \ar[d]^{\phi_*} & \hom_{\mathcal{C}}(c, GF c)
\ar[d]^{G(\phi)_*} \\
\hom_{\mathcal{D}}(Fc, d) \ar[r]^{\mathrm{adj}} &  \hom_{\mathcal{C}}(c, Gd) 
}\]
Here the mark $\mathrm{adj}$ indicates that the adjoint isomorphism is used. 
If we start with the identity $1_{Fc}$ and go down and right, we get the map 
\( c \to Gd  \)
that corresponds under the adjoint correspondence to $Fc \to d$. However, if we
go right and down, we get the natural unit map $\eta(c): c \to GF c$ followed by $G(\phi)$.

Thus, we have a \emph{recipe} for constructing a map $c \to Gd$ given $\phi: Fc \to
d$:
\begin{proposition}[The unit and counit determines everything]
Let $(F, G)$ be a pair of adjoint functors with unit and counit transformations
$\eta, \epsilon$.

Then given $\phi: Fc \to d$, the adjoint map $\psi:c \to Gd$ can be constructed simply as
follows.
Namely, we start with the unit $\eta(c): c \to GF c$ and take
\begin{equation} \label{adj1} \psi =  G(\phi) \circ \eta(c): c \to Gd
\end{equation} (here $G(\phi): GFc \to Fd$).
\end{proposition}

In the same way, if we are given $\psi: c \to Gd$ and want to construct a map
$\phi: Fc \to d$, we construct
\begin{equation} \label{adj2} \epsilon(d) \circ  F(\psi): Fc \to FGd \to   d.
\end{equation}
In particular, we have seen that the \emph{unit and counit morphisms determine
the adjoint isomorphisms.}


Since the adjoint isomorphisms $\hom_{\mathcal{D}}(Fc, d) \to
\hom_{\mathcal{C}}(c, Gd)$ and 
$\hom_{\mathcal{C}}(c, Gd) \to \hom_{\mathcal{D}}(Fc, d) 
$
are (by definition) inverse to each other, we can determine
conditions on the units and counits.

For
instance, the natural transformation $F \circ \eta$ gives a natural
transformation $F \circ \eta: F \to FGF$, while the natural transformation
$\epsilon \circ F$ gives a natural transformation $FGF \to F$.
(These are slightly different forms of composition!)

\begin{lemma}  The composite natural transformation $F \to F$ given by
$(\epsilon \circ F) \circ (F \circ \eta)$ is the identity. 
Similarly, the composite natural transformation
$G \to GFG \to G$ given by $(G \circ \epsilon) \circ (\eta \circ G)$ is the
identity.
\end{lemma} 


\begin{proof} We prove the first assertion; the second is similar.
Given $\phi: Fc \to d$, we know that we must get back to $\phi$ applying the
two constructions above. The first step (going to a map $\psi: c \to Gd$) is by 
\eqref{adj1}
\( \psi = G(\phi) \circ \eta(c);  \) the second step sends $\psi$ to
$\epsilon(d) \circ F(\psi)$, by \eqref{adj2}.
It follows that
\[ \phi = \epsilon(d) \circ F( G(\phi) \circ \eta(c)) = \epsilon(d) \circ
F(G(\phi)) \circ F(\eta(c)). \]
Now suppose we take $d = Fc$ and $\phi: Fc \to Fc $ to be the identity.
We find that $F(G(\phi))$ is the identity $FGFc \to FGFc$, and consequently we
find
\[ \id_{F(c)} = \epsilon(Fc) \circ F(\eta(c)). \]
This proves the claim.
\end{proof} 



\begin{definition} 
Let $F: \mathcal{C} \to \mathcal{D}, G: \mathcal{D} \to \mathcal{C}$ be
covariant functors. An \textbf{adjunction} is the data of two natural
transformations
\[ \eta: 1 \to GF, \quad \epsilon: FG \to 1,  \]
called the \textbf{unit} and \textbf{counit}, respectively, such that the
composites $(\epsilon \circ F) \circ (F \circ \epsilon): F \to F$
and $(G \circ \epsilon) \circ (\eta \circ G)$ are the identity (that is, the
identity natural transformations of $F, G$).
\end{definition} 

We have seen that a pair of adjoint functors gives rise to an adjunction. 
Conversely, an adjunction between $F, G$ ensures that $F, G$ are adjoint, as
one may check: one uses the same formulas \eqref{adj1} and \eqref{adj2} to
define the natural isomorphism.


For any set $S$, let $F(S)$ be the free group on $S$.
So, for instance, the fact that there is a natural map of sets
$S \to F(S)$, for any set $S$, and a natural map of
groups $F(G) \to G$ for any group $G$, determines the adjunction between the
free group functor from $\mathbf{Sets}$ to $\mathbf{Grp}$, and the forgetful
functor $\mathbf{Grp} \to \mathbf{Sets}$.



As another example, we give a criterion for a functor in an adjunction to be
fully faithful.

\begin{proposition} \label{adjfullfaithful}
Let $F, G$ be a pair of adjoint functors between categories $\mathcal{C}, \mathcal{D}$.
Then $G$ is fully faithful if and only if the unit maps $\eta: 1 \to GF$ are
isomorphisms.
\end{proposition} 
\begin{proof} 
We use the recipe \eqref{adj1}.
Namely, we have a map $\hom_{\mathcal{D}}(Fc, d) \to 
\hom_{\mathcal{C}}(c, Gd)$ given by 
$\phi \mapsto G(\phi) \circ \eta(c)$. This is an isomorphism, since we have an
adjunction.
As a result, composition with $\eta$ is an isomorphism of hom-sets if and only if $\phi
\mapsto G(\phi)$ is an isomorphism. From this the result is easy to deduce.
\end{proof} 

\begin{example}
For instance, recall that the inclusion functor from $\mathbf{AbGrp}$ to
$\mathbf{Grp}$ is fully faithful (clear). 
This is a right adjoint to the abelianization functor $G \mapsto G^{ab}$.
As a result, we would expect the unit map of the adjunction to be an
isomorphism, by \cref{adjfullfaithful}.

The unit map sends an abelian group to its abelianization: this is obviously an
isomorphism, as abelianizing an abelian group does nothing.
\end{example}

\subsection{Adjoints and (co)limits}
One very pleasant property of functors that are left (resp. right) adjoints is
that they preserve all colimits (resp. limits).

\begin{proposition} \label{adjlimits}
A left adjoint $F: \mathcal{C} \to \mathcal{D}$ preserves colimits. A right
adjoint $G: \mathcal{D} \to \mathcal{C}$ preserves limits.
\end{proposition} 

As an example, the free functor from $\mathbf{Sets}$ to $\mathbf{AbGrp}$ is a
left adjoint, so it preserves colimits. For instance, it preserves coproducts.
This corresponds to the fact that if $A_1, A_2$ are sets, then $\mathbb{Z}[A_1
\sqcup A_2]$ is naturally isomorphic to $\mathbb{Z}[A_1] \oplus
\mathbb{Z}[A_2]$.

\begin{proof} 
Indeed, this is mostly formal. 
Let $F: \mathcal{C}\to \mathcal{D}$ be a left adjoint functor, with right
adjoint $G$.
Let $f: I \to \mathcal{C}$ be a ``diagram'' where $I$ is a small category. 
Suppose $\colim_I f$ exists as an object of $\mathcal{C}$. The result states
that $\colim_I F \circ f$ exists as an object of $\mathcal{D}$ and can be
computed as 
$F(\colim_I f)$.
To see this, we need to show that mapping out of $F(\colim_I f)$ is what we
want---that is, mapping out of $F(\colim_I f)$ into some $d \in \mathcal{D}$---amounts to
giving compatible $F(f(i)) \to d$ for each $i \in I$.
In other words, we need to show that $\hom_{\mathcal{D}}( F(\colim_I f), d) =
\lim_I \hom_{\mathcal{D}}(
F(f(i)), d)$; this is precisely the defining property of the colimit.

But we have
\[ \hom_{\mathcal{D}}( F(\colim_I f  ), d) = \hom_{\mathcal{C}}(\colim_I f, Gd)
= \lim_I \hom_{\mathcal{C}}(fi, Gd) = \lim_I \hom_{\mathcal{D}}(F(fi), d),
\]
by using adjointness twice. 
This verifies the claim we wanted.
\end{proof} 

The idea is that one can easily map \emph{out} of the value of a left adjoint
functor, just as one can map out of a colimit.



