ctcheat.tex

% Header <<<
\RequirePackage[l2tabu,orthodox]{nag}
\RequirePackage{fixltx2e}

\documentclass[10pt,twocolumn,letterpaper]{article}
\DeclareSymbolFont{AMSb}{U}{msb}{m}{n}
\DeclareMathAlphabet{\mathbbm}{U}{bbm}{m}{n}
\title{Category Theory Cheat Sheet}
%\author{Nathaniel Wesley Filardo}

\usepackage{xparse}
\usepackage{amsmath,amssymb,amsthm,latexsym}
\usepackage{fancyhdr}
\usepackage{titlesec} % [tiny,center,compact,sc] 
\usepackage[cm]{fullpage}
\usepackage{pstricks}
\usepackage{graphicx}
\usepackage{verbatim}
\usepackage{bm}
\usepackage{ifthen}
\usepackage[all]{xypic}
\usepackage{textcomp}
\usepackage{url}
\usepackage{multirow}
\usepackage{enumitem}
\usepackage{etoolbox}
\usepackage{hyperref}
\hypersetup{
    colorlinks,
    linkcolor={red!50!black},
    citecolor={blue!50!black},
    urlcolor={blue!80!black}
}
\usepackage{makeidx}\makeindex

%\setlist{nolistsep}

%http://tex.stackexchange.com/questions/126750/how-can-i-number-paragraphs-without-higher-level-counters
\usepackage{chngcntr}
\counterwithout{paragraph}{subsubsection}
\renewcommand{\theparagraph}{{\tiny\P}{\small\arabic{paragraph}}}
\titleformat{\paragraph}[runin]{\normalfont\bfseries}{\theparagraph}{\wordsep}{}
\titlespacing{\paragraph}{0pt}{3.25ex plus 1ex minus .2ex}{\wordsep}
\setcounter{secnumdepth}{4}

\renewcommand{\baselinestretch}{0.9}

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

\setlength{\parindent}{0pt}
\setlength{\parskip}{-2pt}

% http://www.latex-community.org/forum/viewtopic.php?f=46&t=3837&start=0#p15112
\makeatletter
\g@addto@macro\normalsize{%
\setlength\abovedisplayskip{0pt}%
\setlength\abovedisplayshortskip{0pt}%
\setlength\belowdisplayskip{0pt}%
\setlength\belowdisplayshortskip{0pt}%
}
\makeatother

% http://comments.gmane.org/gmane.comp.tex.xy-pic/223
% fixes {>->} having the tail overlap the item.
\newdir{ >}{{}*!/-2.6667\jot/\dir{>}}


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

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

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

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

\DeclareMathOperator{\mm}{\mid\mid}
\newcommand{\natto}{\overset{\cdot}{\to}}

\newcommand{\defnref}[3][]{\ifstrempty{#1}{\ref{defn:#2}}{\ref{defn:#1}}}
\DeclareDocumentCommand{\defn}{ O{} D<>{} m }{%
  {\ifstrempty{#1}%
    {\label{defn:#3}}%
	{\label{defn:#1}}%
   \ifstrempty{#2}%
    {\index{#3|defnref[#1]{#3}}\bfseries #3}%
    {\index{#2#3|defnref[#1]{#3}}\bfseries #3}}%
}
\newcommand\xrdefnhelper[1]{defn:#1}
\newcommand{\xrdefn}[1]{\ref{\forcsvlist{\xrdefnhelper}{#1}}}
\newcommand{\hrdefn}[2][]{\ifstrempty{#1}{\hyperref[defn:#2]{#2}[\ref{defn:#2}]}
                                         {\hyperref[defn:#1]{#2}[\ref{defn:#1}]}} 

\newcommand\xrexhelper[1]{ex:#1}
\newcommand{\xrex}[1]{EX: \ref{\forcsvlist{\xrexhelper}{#1}}}

\begin{document}
%>>>
% Intro <<<
Unless otherwise notated, references are to \textit{Abstract and Concrete
Categories: The Joy of Cats}, \cite{adamek:joy}.  Notation follows theirs
with some contamination from Awodey's \textit{Category Theory},
\cite{awodey:ct}, and Pierce's \textit{Basic Category Theory for Computer
Scientists}, \cite{pierce:basicct}.

Entries within each section are roughly sorted by definition, alphabetically.

Quantifiers are written perhaps unusually in this document, as $Q_{\phi}$,
where $Q$ is $\forall$, $\exists$, $\bigcup$, etc. and $\phi$ is a list of
variables or an expression whose free variables are quantified over.
Constrained quantification may be written as $v_1 : \tau_1, v_2 : \tau_2 .
\phi(v_1,v_2)$ to indicate ``the pairs of values $v_1$ ($\in \tau_1$) and
$v_2$ ($\in \tau_2$) such that $\phi(v_1,v_2)$ holds''.  Strings of
quantifiers are represented $Q_{\phi} Q'_{\phi'}$ etc.  There is not
necessarily a dot between quantifiers or between the quantifiers and
quantified formula.

%>>>
\section{Basics} % <<<

  \paragraph{}
  %
  A \defn{category} $\mathbf{C}$ (\S3.1) is a quadruple
  $(\mathcal{O},\mbox{hom},id,\circ)$ with
  \begin{itemize}
    \item A collection of objects $\mathcal{O}$
  \item For each pair of objects $A,B$, a (disjoint) collection of arrows
    from \defn{domain} $A$ to \defn{codomain} $B$,
    $\mbox{hom}(A,B)$ (also written $\mathbf{C}(A,B)$).
    \item An associative arrow composition operator $\circ$.
    \item Identity arrows ($id_A$) on each object $A$, unit of $\circ$
  \end{itemize}

  \paragraph{}
  %
  Categories may be described (Awodey:p21) as
     \[\xymatrix{ C_2 \ar[r]^\circ & C_1 \ar@<2ex>[r]_{cod} \ar@<-2ex>[r]_{dom} & C_0 \ar[l]^i }\]

  \paragraph{}
  %
  A category is (Awodey:p24-25,D1.11-12)\dots
    \begin{itemize}
      \item \defn{small} if $C_0$ and $C_1$ are sets and \defn{large} otherwise.
      \item \defn{locally small} if $\forall_{X,Y \in C_0} \mbox{hom}_C(X,Y) \subseteq C_1$ is a set.
    \end{itemize}

  \paragraph{}
  %
  A predicate $P$ is \defn{essentially unique} (\S7.3) if it is unique up to
  isomorphism:
  \begin{itemize}
    \item If both $PA$ and $PB$, then $A \simeq B$
    \item If $PA$ and $A \simeq B$, then $PB$.
  \end{itemize}

  \paragraph{}
  %
  $\mathbf{B}$ is a \defn{subcategory} of $\mathbf{A}$ if it has
  subcollections of objects and morphisms with identical composition and
  identity (\S4.1.1).  $\mathbf{B}$ is additionally \dots
  \begin{itemize}
	\item \defn[fullcat]{full} if it has all morphisms from $\mathbf{A}$
	      between objects in $\mathbf{B}$. (\S4.1.2) 
	\item \defn{reflective} if each $B$ has an $\mathbf{A}$-reflection. (\S4.16.2)
	      \xrdefn{reflection}
  \end{itemize}

  \paragraph{}
  %
  A category is$\dots$
  \begin{itemize}
    \item \defn{balanced} if all bi are iso (\S7.49.2)
    \item \defn{discrete} if all morphisms are identities. (\S3.26.1)
    \item \defn{thin} if $\forall_{A,B} \mbox{hom}(A,B) \simeq \set{*}$. (\S3.26.2)
  \end{itemize}

% >>>
\section{Derived Categories} % <<<

  \paragraph{}
  %
  The \defn{arrow} (Awodey:p16,i3) category $\mathbf{C}^\to$ has arrows for
  commutative squares in $\mathbf{C}$.  There are two functors
  $\mathbf{cod}, \mathbf{dom} : \mathbf{C}^\to \to \mathbf{C}$.

  \paragraph{}
  %
  The \defn[conecat]{cone} category over a given diagram,
  $\mathbf{Cone}(D(J))$, has as objects \hrdefn[cone]{cones} to that diagram
  and a morphism between cones is an arrow $\phi : C \to C'$ s.t.
  $\forall_{D_j \in D(J)} c_j^\prime \circ \phi = c_j$.

  \paragraph{}
  %
  The \defn{dual} (\S3.5;Awodey:p15,i2) category $\mathbf{A}^\text{op}$
  which exchanges domains and codomains of arrows in $\mathbf{A}$.  Any
  purely-categorical statement implies its dual.

  \paragraph{}
  %
  The \defn{slice} (Awodey:p16,i4) category $\mathbf{C}/C$ has objects of
  arrows in $\mathbf{C}$ with codomain $C$.  Arrows are tops of commutative
  triangles.

% >>>
\section{Object Properties} % <<<

  \paragraph{}
  %
  $C$ is a \defn{coseparator} if $\forall_{f,g : B \to A} f \ne g
  \Rightarrow \exists_{h : A \to C} . h \circ f \ne h \circ g$. (\S7.17)
  (Contrast \hrdefn{monomorphism}.)

%  \paragraph{}
%  %
%  The \defn{end} of a diagonal profunctor $S : \mathbf{A}^\text{op} \times
%  \mathbf{A} \to \mathbf{B}$ is the object 

  \paragraph{}
  %
  An object $0$ is \defn{initial} if $\forall_B \exists! f_B : 0 \to B$.
  (\S7.1)

  \paragraph{}
  %
  A \defn{limit} (Awodey:D5.16) of a diagram $D(J)$ is a terminal object in
  the category $\mathbf{Cone}(D(J))$.  Written: $c_i : (\varprojlim_{j} D_j)
  \to D_i$.  A \defn{colimit} (Awodey:\S5.6) is an initial object in the
  category of cocones; $c_i : D_i \to (\varinjlim_j D_j)$. \xrdefn{cone}
  
  \paragraph{}
  %
  $(A \times B,\pi_1,\pi_2)$ is a \defn{product} iff (UMP)
    \[\xymatrix{
    {}\save[]+<-1cm,0cm>*\txt<8pc>{$\forall_{Z,z_1,z_2} \exists!_u$\\$u\pi_1 = z_1 ~\wedge~ u\pi_2 = z_2$}\restore
    &      & Z \ar[dl]_{z_1} \ar[dr]^{z_2} \ar@{..>}[d]^u & \\
    &    A & \ar[l]_{\pi_1} A \times B \ar[r]^{\pi_2} & B \\
    }\]

 \paragraph{}
  %
  The \defn{product category} $\mathbf{C} \times \mathbf{D}$ of two
  categories $\mathbf{C}$ and $\mathbf{D}$ consists of objects which are
  each an ordered pair of an object from $\mathbf{C}$ and one from
  $\mathbf{D}$; morphisms are, similarly, pairs of morphisms from
  $\mathbf{C}$ and $\mathbf{D}$.  This sense of $\times$ is itself the
  trivial \hrdefn{bifunctor}.

  \paragraph{}
  %
  $(P,p_1,p_2)$ is a \defn{pullback} (Awodey:p80,D5.4) of $f,g$ iff (UMP)
     \[\xymatrix{
     {}\save[]+<-1cm,0cm>*\txt<8pc>{$\forall_{Z,z_1,z_2 . fz_1 = gz_2}\exists!_u$\\$z_1 = p_1u ~\wedge~ z_2 = p_2u$}\restore
     & Z \ar[dr]_{z_2} \ar@/^1pc/[rr]_{z_1} \ar@{..>}[r]_u & P \ar[d]^{p_1} \ar[r]_{p_2} & B \ar[d]^g \\
     &                                              & A \ar[r]^f & C
     }\]
     $P$ may be denoted $A \times_C B$ when $f,g$ are clear.

  \paragraph{}
  %
  $S$ is a \defn{separator} if $\forall_{f,g : A \to B} f \ne g
  \Rightarrow \exists_{h : S \to A} . f \circ h \ne g \circ h$. (\S7.10)
  (Contrast \hrdefn{epimorphism}.)
  $S$ is a separator iff $\mbox{hom}(S,-)$ is faithful. (\S7.12)

  \paragraph{}
  %
  A set of objects $\mathcal{T}$ is a \defn{separating set} if
  $\forall_{f,g : A \to B} f \ne g \Rightarrow \exists{S \in \mathcal{T},
  h : S \to A} . f \circ h \ne g \circ h$. (\S7.14)

  \paragraph{}
  %
  An object $1$ is \defn{terminal} if $\forall_A \exists! f_A : A \to 1$.
  (\S7.4)

  \paragraph{}
  %
  An object that is both initial and terminal is called a \defn{zero}.
  (\S7.7) \xrex{mon0}

% >>>
\section{Arrow Properties} % <<<

  \paragraph{}
  $(Q,q)$ is a \defn{coequalizer} (\S7.51) of $f,g$ iff (UMP) $qf = qg$ and
     \[\forall_{Z,z . zf = zg} \exists!_u uq = z \quad
     \xymatrix{
     Z & Q \ar@{..>}[l]^u & B \ar[l]^q \ar@/^1pc/[ll]^{z} & A \ar@<1ex>[l]^f \ar@<-1ex>[l]_g
     }\]
  Coequalizers are essentially unique (\S7.70.1) and epic (\S7.71,\S7.75.2).
  \xrex{setcoeq}

  \paragraph{}
  %
  $e$ is an \defn{epimorphism} (\S7.39) (the dual of a monomorphism)
  (equiv: is \defn{epic} (Awodey:D2.1)) if
  %
    \[\xymatrix{\forall_{i,j} ie = je \Rightarrow i = j & A \ar@{->>}[r]^e & B \ar@<1ex>[r]^{i} \ar@<-1ex>[r]_j & C} \]
  %
  If $f$ and $g$ are epis, then so is $g \circ f$; if $g \circ f$ is epi,
  then so is $g$. (\S7.41) \xrex{setmonepi}

  \paragraph{}
  %
  $(E,e)$ is an \defn{equalizer} (\S7.51) of $f,g$ iff (UMP) $fe = ge$ and
     \[\forall_{Z,z . fz = gz} \exists!_u eu = z \quad
     \xymatrix{
     Z \ar@{..>}[r]^u \ar@/_1pc/[rr]^{z} & E \ar[r]^e & A \ar@<1ex>[r]^f \ar@<-1ex>[r]_g & B \\
     }\]
  Equalizers are essentially unique (\S7.53) and monic (\S7.56,\S7.59.2).
  \xrex{seteq}

  \paragraph{}
  %
  A mono $m$ is a \defn{extremal} (\S7.61) if $e$ epic and
  $m = f \circ e$ implies that $e$ iso.

  \paragraph{}
  %
  Let $G: \mathbf{A} \to \mathbf{B}$ and $B \in \mathbf{B}$.  A
  \defn[gstrarr]<@G-structured arrow with domain B> {$G$-structured arrow
  with domain $B$} is a pair $(f : B \to GA, A)$.  (\S8.30)  It is
  %
  \begin{itemize}
    %
    \item \defn{generating} if $\forall_{r,s : A \to A'} Gr \circ f = Gs
      \circ f \implies r = s$
	%
    \item \defn{extremally generating} if it is generating and $\forall_{m :
      A' \to A, m ~\text{mono}, (g,A')} f = Gm \circ g \implies m ~\text{iso}$.
	%
	\item \defn[gunivarr]<@G-universal for B>{$G$-universal for $B$} if
	$\forall_{(f', A')}
	%
    \exists!_{\check f} f' = G{\check f} \circ f$.  That is,
    \[\xymatrix{
        B \ar[r]^f \ar@/_1.25pc/[rr]^{f'}
        & GA \ar@{.>}[r]^{G{\check f}}
        & GA'
        & A \ar@{.>}[r]^{\check f}
        & A'
    }\]
  \end{itemize}
  When $G$ is a subcategory inclusion, a $G$-structured universal arrow is
  a \defn{reflection} (\S4.16).

  \paragraph{}
  %
  $f : A \to B$ is an \defn{isomorphism} if $\exists!_g . f \circ g = id_B
  ~\wedge~ g \circ f = id_A$. (\S3.8; ! in \S3.11).  Every isomorphism
  is both monic and epic (Awodey:P2.6).

  \paragraph{}
  %
  $f$ is a \defn{monomorphism} (\S7.32) (equiv: is \defn{monic}
  (Awodey:D2.1)) if
    \[\xymatrix{\forall_{i,j} mi = mj \Rightarrow i = j & C \ar@<1ex>[r]^{i} \ar@<-1ex>[r]_j & A \ar@{{ >}->}[r]^m & B} \]
  If $f$ and $g$ are monos, then so is $g \circ f$; if $g \circ f$ is mono,
  then so is $f$. (\S7.34)  Objects with monomorphisms to $X$ are called
  \defn{subobjects} of $X$ (Awodey:D5.1). \xrex{setmonepi}

  \paragraph{}
  %
  A \defn{point} (Awodey:p32) of $C$ is any $c : 1 \to C$. \xrex{monpt}

  \paragraph{}
  %
  $f$ is a \defn{regular monomorphism} (\S7.56) if it is an equalizer of
  some pair of morphisms.

  \paragraph{}
  %
  $f : A \to B$ is a \defn{retraction} if $\exists_g . f \circ g = 1_B$
  (\S7.24) aka \defn{split epi} (Awodey:D2.7).  If $f$ and $g$ are
  retractions, then so is $g \circ f$; if $g \circ f$ is a retraction, then
  so is $g$. (\S7.27)

  \paragraph{}
  %
  $f : A \to B$ is a \defn{section} if $\exists_g . g \circ f = 1_A$.
  (\S7.19) aka \defn{split mono} (Awodey:D2.7).
  If $f$ and $g$ are sections, then so is $g \circ f$;
  if $g \circ f$ is a section, then so is $f$. (\S7.21)

  \paragraph{}
  %
  Several morphism properties combine in useful ways:
  \begin{itemize}
    \item mono, epi $\Rightarrow$ \defn{bimorphism} (\S7.49) \xrex{monbi}
    \item section $\Rightarrow$ regular mono (\S7.35, \S7.59.1)
    \item regular mono $\Rightarrow$ extremal mono (\S7.59.2, \S7.63)
    \item retraction $\Rightarrow$ epi (\S7.42)
    \item mono, retraction $\Leftrightarrow$ isomorphism (\S7.36)
    \item section, epi $\Leftrightarrow$ isomorphism (\S7.43)
  \end{itemize}
  %(XXX stopped around \S7.60; there's more to be said)

% >>>
\section{Exponentials} % <<<

  \paragraph{}
  %
  (Awodey:p107,D6.1) In a category with binary products, given two objects $B$ and $C$,
  their \defn{exponential} is an object $C^B$ and arrow $\epsilon : C^B \times B \to C$
  s.t.
     \[\xymatrix{
     {}\save[]+<-1cm,0cm>*\txt<8pc>{$\forall_{A,f : A \times B \to C}\exists!_{\tilde f : A \to C^B}$\\
                                    $\epsilon \circ (\tilde f \times 1_B) = f$}\restore
     & C^B & C^B \times B \ar[r]^\epsilon & C \\
     & A \ar@{..>}[u]^{\tilde f} & A \times B \ar@{..>}[u]^{\tilde f \times 1_B} \ar[ur]_f
     }\]
  The arrows $f$ and $\tilde f$ are ``exponential transposes.''

  \paragraph{}
  %
  Exponential transposition is self inverse (Awodey:p108).  This implies
    \[ \mbox{hom}_{\mathbf{C}}(A \times B, C) \simeq \mbox{hom}_{\mathbf{C}}(A, C^B) \]

  \paragraph{}
  %
  The \defn{exponential category} $\mathbf{D}^\mathbf{C}$ has as objects
  \hrdefn[functor]{functors} from $\mathbf{C}$ to $\mathbf{D}$ and as
  morphisms the \hrdefn[nattrans]{natural transformations} between these
  functors.

  \paragraph{}
  %
  A category is \defn{cartesian closed} (Awodey:p108,D6.2) if it has all
  finite products and exponentials.

% >>>
\section{Functors} % <<<
% Basics <<<

  \paragraph{}
  %
  Default notation here: functors $F,G : \mathbf{A} \to \mathbf{B}$.

  \paragraph{}
  %
  A \defn{covariant functor} (or just \defn{functor}) $F$
  (\S3.17;Awodey:D1.2) assigns to each $\mathbf{A}$-object a
  $\mathbf{B}$-object and to each $\mathbf{A}$-morphism a
  $\mathbf{B}$-morphism s.t. composition and identites are {\em preserved}.

  \paragraph{}
  %
  A \defn[contrafunc]{contravariant functor} $F$ (\S3.20.5) is a (covariant) functor
  $\mathbf{A}^\text{op} \to \mathbf{B}$.

  \paragraph{}
  %
  A \defn{diagram} (Awodey:D5.15) is a functor $D : J \to C$ from some
  indexing category $J$.

  \paragraph{}
  %
  A \defn{endofunctor} has $\mathbf{A} = \mathbf{B}$.  $F \circ F$ may be
  denoted $F^2$, etc. (\S3.23; ftn 15)

  \paragraph{}
  %
  Functors compose. (\S3.23)

  % XXX Cite
  \paragraph{}
  %
  A functor $F : C \to D$\dots
  \begin{itemize}
    \item \defn[fpresvlim]{preserves limits of type $J$} if
      \[ \forall_{D : J \to C}\forall_{\varprojlim_j D_j} F(\varprojlim_j D_j) \simeq \varprojlim_j F(D_j).\]

    \item \defn[fcreatlim]{creates limits of type $J$} if $\forall_{D : J \to C}$
      and all limits $L = \varprojlim_j FD_j$ (i.e., bundle $p_j : L \to FD_j$ in $C'$),
      $\exists! (\bar{p_j} : \bar{L} \to D_j) \in C'$ with $F(\bar L) = L$, $F(\bar{p_j}) = p_j$,
      and $\bar L = \varprojlim_j D_j$. 
  \end{itemize}

  \paragraph{}
  %
  A (covariant) \defn{bifunctor} is a functor from a \hrdefn{product
  category} such that each partial application is {\em also} a functor.
  (See \cite{hinze:f} and bifunctors.tex for more.) A \defn{profunctor} is a
  bifunctor which is \hrdefn[contrafunc]{contravariant} in one argument and
  covariant in the other.

  \paragraph{}
  %
  A functor $F$ is (\S3.27, \S3.33)
  \begin{itemize}
    \item \defn{amnestic} if $f$ is an identity iff $Ff$ is an identity.
    \item \defn{continuous} if it preserves all limits. (Awodey:D5.24)
    \item an \defn{equivalence} if it is full, faithful, and
      isomorphism-dense.
    \item an \defn{embedding} if it is injective on morphisms.
    \item \defn{faithful} if $\forall_{A,A'} F\vert_{\mathbf{A}(A,A')}
      \subseteq \mathbf{B}(FA, FA')$ is injective.
    \item \defn[fullfunc]{full} if $\forall_{A,A'} F\vert_{\mathbf{A}(A,A')}$ surjective.
    \item \defn{isomorphism-dense} if $\forall_B \exists_A . F(A) \simeq B$.
  \end{itemize}

  \paragraph{}
  %
  All functors \defn{preserve} (in $\mathbf{A}$ implies in $\mathbf{B}$) 
  isomorphisms (\S3.21), sections (\S7.22), and retractions (\S7.28).

  \paragraph{}
  %
  Some functors \defn{reflect} (in $\mathbf{B}$ implies in $\mathbf{A}$) useful properties:
  \begin{itemize}
      \item Full, faithful functors reflect sections (\S7.23) and retractions (\S7.29).
      \item Faithful functors reflect monos (\S7.37.2) and epis (\S7.44).
  \end{itemize}

% >>>
\subsection{Transformations} % <<<

  \paragraph{}
  %
  A \defn[nattrans]{natural transformation} $\tau : F \natto G$ assigns each
  $A \in \mathbf{A}$ to $\tau_A : FA \to GA$ s.t.
  $\forall_{f : A \to A'} G f \circ \tau_A = \tau_{A'} \circ F f$
  (\S6.1;Awodey:D7.6).
  That is,
  %
  \[\xymatrix{
     {}\save[]+<-1cm,0cm>*\txt<8pc>{$\forall_{A,B,f \in C}$\\$Gf\circ \tau_A = \tau_B\circ Ff$}\restore
      & FA \ar[r]^{\tau_A} \ar[d]_{Ff} & GA \ar[d]^{Gf} \\
      & FB \ar[r]^{\tau_B}             & GB} \]
  %
  More generally, given any functor from a \hrdefn{product category}, we may
  say that it is natural in the $i$-th position if, for all ways of fixing
  the other positions, the resulting partial applications form natural
  transformations.

  \paragraph{}
  %
  There is special notation for functors ($H$) applied to natural
  transformations and vice-versa (\S6.3): $H\tau : HF \natto HG$ defined by
  $(H\tau)_A = H(\tau_A)$ and $\tau H : FH \natto GH$ defined by $(\tau H)_A
  = \tau_{HA}$.

%  XXX Not yet
%  \paragraph{}
%  %
%  A \defn[exttrans]{extranatural transformation} is one where
%
%  \paragraph{}
%  %
%  A \defn[dinat]{dinatural transform} is

% >>>
\subsection{Special Functors} % <<<

  \paragraph{}
  %
  For every category $\mathbf{C}$ and object $D \in \mathbf{D}$ there is
  a unique \defn{constant functor} $\mathbf{!}_D$ which sends every
  $C$ to $D$ and every $f$ to $1_D$.

  \paragraph{}
  %
  The \defn{covariant representable functor} (Awodey:p44) at $A \in
  \mathbf{C}$ is defined by $\mbox{Hom}(A,\text{---}) : \mathbf{C} \to
  \mathbf{Sets}$.   These functors are continuous (Awodey:P5.25).

  \paragraph{}
  %
  Representable functors preserve monos. (\S7.37.1)

  \paragraph{}
  %
  Pullback defines a functor
    \[ h^* : (A \stackrel{\alpha}{\to} C) \in \mathbf{C}/C
       \mapsto (C' \times_C A \stackrel{\alpha'}{\to} C') \in \mathbf{C}/C' \]
    where $\alpha'$ is the pullback of $\alpha$ along $h$. (Awodey:P5.10)

% >>>
% >>>
\section{Cones and Sources} % <<<

  \paragraph{}
  %
  A \defn{cone} (Awodey:D5.15) to a diagram $D(J)$ is a collection of arrows
  $c_j : C \to D_j$ s.t. $\forall_{D_\alpha \in D(J)} c_j = D_\alpha \circ
  c_i$.  (Cones are also \hrdefn[nattrans]{natural
  transformations} from the \hrdefn{constant functor} to the inclusion
  functor of the diagram $D$. \cite{milewski:limits})  (Cones are
  \hrdefn[source]{sources} subject to commutation diagrams implied by the
  diagram.)

  \paragraph{}
  %
  A \defn{source} in category $\mathbf{A}$ indexed by $I$ is a pair $(A,
  \set{f_i : A \to A_i}_{i \in I})$.  This source has domain $A$ and
  codomain $\set{A_i}_{i\in I}$. (\S10.1)

  \paragraph{}
  %
  Given $(A,\set{f_i}_{i \in I})$ and
  $\{(A_i,\set{g_{ij}}_{j \in J_i})\}_{i \in I}$
  all sources, their \defn{composite} is $(A, \set{g_{ij} \circ f_i}_{i\in I,
  j\in J_i})$. (\S10.3)

  \paragraph{}
  %
  A \defn{mono-source} (\S10.5) is $(A,\set{f_i})$ s.t. \\ $\forall r,s: B \to A 
  \brak{\forall_{i\in I} f_i \circ r = f_i \circ s} \Rightarrow r = s$.

% >>>
\section{Concrete Categories} % <<<

  \paragraph{}
  %
  For this section, $\mathbf{A}$ is a \defn{concrete category} over
  $\mathbf{X}$ with \defn{forgetful} \hrdefn{functor} $U : \mathbf{A} \to
  \mathbf{X}$ \hrdefn{faithful}, denoted $(\mathbf{A}, U)$.  (\S5.1.1)

  \paragraph{}
  %
  When $\mathbf{A} = \mathbf{X}$, $\mathbf{Alg}(U)$ has
  \hrdefn[falg]{$U$-algebras} as objects and algebra homomorphisms as
  morphisms.

  \paragraph{}
  %
  If $\mathbf{X}$ is $\mathbf{Set}$, $\mathbf{A}$ is a \defn{construct}.
  (\S5.1.2)

  \paragraph{}
  %
  $(UA \overset{f}{\to} UB) \in \mathbf{X}$ \defn[Amporphism]{is an
  $\mathbf{A}$-morphism} if $f$ has an {\em unique} $U$-preimage in
  $\mathbf{A}$.  (\S5.3, \S6.22)

  %An object $A\in\mathbf{A}$ is
  %\dots\! if $\forall_{B \in \mathbf{A}}$, \dots is an $\mathbf{A}$ arrow.
  %\begin{itemize}
  %  \item \defn{discrete}, $(UA \to UB)$ (\S8.1)
  %  \item \defn{indiscrete}, $(UB \to UA)$ (\S8.3)
  %\end{itemize}

  \paragraph{}
  %
  A \defn{free object} $A \in \mathbf{A}$ is one with a ($U$-structured)
  universal arrow $(u,UA)$ in $B$. (\S8.22+\S8.30)  \xrdefn{gunivarr}

  %$f \in \mathbf{A}$ is \defn{initial} if $\forall_{C \in \mathbf{A}}$ $UC
  %\overset{f \circ g}{\to} UB$ is an $\mathbf{A}$-morphism implies that $UC
  %\overset{g}{\to} UA$ is an $\mathbf{A}$-morphism.

% >>>
\section{Adjoints and Adjoint Situations} % <<<
\label{sec:adj}

Be sure to see \autoref{sec:adjex} for examples.

\subsection{Joy Approach}

  \paragraph{}
  %
  A functor $G : \mathbf{A} \to \mathbf{B}$ is \defn{adjoint} if
  $\forall_{B \in \mathbf{B}}$ there exists a $G$-structured universal
  arrow with domain $B$.  (\S18.1) \xrdefn{gunivarr}

  \paragraph{}
  %
  Adjoints compose (\S8.5), preserve \hrdefn[mono-source]{mono-sources}
  (\S8.6), and preserve \hrdefn[limit]{limits} (\S8.9)

  \paragraph{}
  %
  Given adjoint $G$ with $\eta_B : B \to G(A_B)$ the $G$-structured
  universal arrow with domain $B$, $\exists!_F$ such that $FB = A_B$ and
  $\eta : id_B \natto G \circ F$ is natural; further, there is a unique,
  natural $\epsilon : F \circ G \natto id_A$ with $G\epsilon \circ \eta G =
  id_G$ and $\epsilon F \circ F \eta = id_F$.  (\S19.1)

  \paragraph{}
  %
  $(\eta,\epsilon) : F \dashv G : \mathbf{A} \to \mathbf{B}$ is a
  \defn{adjoint situation} if the above relationships hold. (\S19.7)

\subsection{Awodey Approach}

  \paragraph{}
  %
  An \defn{adjunction} (Awodey:D9.1) of $F : C \to D$ and $G : D \to C$ is a
  \hrdefn[nattrans]{natural transformation} $\eta : I_C
  \stackrel{\cdot}{\to} (G\circ F)$ s.t.
  %
  \[\xymatrix{
     {}\save[]+<-1cm,0cm>*\txt<8pc>{$\forall_{f:X \to GY}\exists!_{f^\#:FX\to Y}$\\
                                    $f = Gf^\# \circ \eta_X$}\restore
      & FX\ar@{..>}[d]^{f^\#} & X \ar[dr]^f \ar[r]^{\eta_X} & GFX \ar@{..>}[d]^{Gf^\#} \\
      & Y & & GY
  }\]
  %
  Equivalently (Awodey:D9.7), a natural {\em isomorphism}
  %
  \[ \phi : \mbox{Hom}_D(FC,D) \simeq \mbox{Hom}_C(C,GD),
       \quad \eta_X = \phi(1_{FX}) \]

\subsection{Moving Right Along}

  \paragraph{}
  %
  A \defn{monad} (\S20.1) on $\mathbf{X}$ is $(T : \mathbf{X} \to \mathbf{X},
  \eta : id_{\mathbf{X}} \natto T, \mu : T^2 \natto T)$ s.t.
  \[\forall_X \quad
  \xymatrix@R=10pt{
    T^3X \ar[r]^{T(\mu_X)} \ar[d]^{\mu_{TX}} & T^2X \ar[d]^{\mu_{X}} \\
    T^2X \ar[r]^{\mu_X}                 & TX
  } \quad \xymatrix@R=10pt{
    TX \ar[r]^{T(\eta_X)} \ar[dr]_{id_{TX}} & T^2X \ar[d]^{\mu_X} & TX \ar[l]_{\eta_{TX}} \ar[dl]^{id_{TX}} \\
        & TX & 
  }\]

% >>>
\appendix
\section{Miscellaneous Terminology} % <<<

  \paragraph{}
  %
  Given an \hrdefn{endofunctor} $F$ on $\mathbf{C}$, a
  \defn[falg]<@F-algebra>{$F$-algebra} is a pair of a \defn{carrier} $X \in
  \mathbf{C}$ and interpretation morphism $h : FX \to X \in \mathbf{C}$.  A
  \defn{algebra homomorphism} is a morphism $f$ such that $f : (X,h) \to
  (X',h')$ s.t. $f \circ h = h' \circ T(f)$.  (\S5.37)


  \paragraph{}
  %
  A category is \defn{finitely presented} (Awodey:p75) if it is the free
  category over a finite graph quotiented by a finite set of equations.

  \paragraph{}
  %
  The \defn{local membership relation} for generalized element $z : Z \to C$
  and subobject $M$ (i.e., with monic $m : M \to C$), $z \in_X M$, holds iff
  $\exists_{f:Z \to M} . z = mf$.

  \paragraph{}
  %
  An \defn[wCPO]<@w-complete Partial Order>{$\omega$-complete Partial Order}
  ($\omega$CPO) is a Poset which has all {\em co}limits of type
  $(\mathbb{N},\le)$.  (All countably infinite ascending chains have a top.)
  (Awodey:p101,E5.33)

% >>>
\section{Miscellaneous Useful Properties} % <<<

  \paragraph{}
  %
  (Awodey:p84,L5.8) In the commuting diagram
    \[\xymatrix{ F \ar[r]_{f'} \ar[d]^{h''} & E \ar[r]_{g'} \ar[d]^{h'} & D \ar[d]^{h} \\
       A \ar[r]^f & B \ar[r]^g & C
    }\]
    \begin{enumerate}
      \item If $FEBA$ and $EDCB$ are pullbacks, so is $FDCA$.
      \item If $FDCA$ and $EDCB$ are pullbacks, so is $FEBA$.
    \end{enumerate}

  \paragraph{}
  %
  (Awodey:p84,C5.9) Pullbacks preserve commutative triangles.

  \paragraph{}
  %
  Universal Constructions (or Universal Mapping Properties, UMP) reduce to
  limits (Awodey:p91,E5.17-20):
  %
  \begin{tabular}{|c|c|c|c|}
  	\hline
      terminals & products & equalizers & pullbacks \\
      %
  	\hline
      & $\xymatrix@C5pt{x & y}$
      & $\xymatrix{x \ar@<1ex>[r]^{\alpha} \ar@<-1ex>[r]_{\beta} & y}$
      & $\xymatrix@C5pt@R5pt{& x \ar[d] \\ y \ar[r] & z}$\\
  	\hline
  \end{tabular}

  \paragraph{}
  %
  Objects defined by UCs are unique up to isomorphism.

% >>>
\section{Examples To Jog Your Memory} % <<<

\subsection{$\mathbf{Set}$}

  \paragraph{}\label{ex:setmonepi}
  %
  \hrdefn[epic]{Epic} is surjective, \hrdefn{monic} is injective.

  \paragraph{}\label{ex:setcoeq}
  %
  \hrdefn[coequalizer]{Coequalizers} correspond to equivalence classes
  (\S7.69.1): Let $\sim$ be {\em the smallest} eq. rel. s.t. $\forall_{a \in
  A} f(a) \sim g(a)$; then $(Q,q) = (B/\sim, b \mapsto \brak{b}_\sim)$ is a
  coequalizer of $f$ and $g$.

  \paragraph{}\label{ex:seteq}
  %
  \hrdefn[equalizer]{Equalizers}: $(E,e) = (\set{x \mid f(x) = g(x)} \subseteq X, \subseteq)$.

\subsection{$\mathbf{Mon}$}

  \paragraph{}\label{ex:monbi}
  %
  \hrdefn[bimorphism]{Bimorphisms} are not isos: ($(\mathbf{N},+,0) \to
  (\mathbf{Z},+,0)$).  (Pierce:\S1.6.3)

  \paragraph{}\label{ex:mon0}
  %
  $(\set{*},\cdot,*)$ is a (the) \hrdefn{zero}.

  \paragraph{}\label{ex:monpt}
  %
  Each monoid $M$ has only one \hrdefn{point}, $1 \to M$.

\subsection{Adjoint Situations and Monads}
  \label{sec:adjex}
  Defintitons in \autoref{sec:adj}.

  \paragraph{}
  %
  Consider $(\eta, \epsilon) : F \dashv G : \mathbf{Mon} \to \mathbf{Set}$.
  $\eta_X : X \to GFX$ is insertion of generators: $\forall x \in X \eta_X x = x$.
  $\epsilon_Y : FGY \to Y$ is the re-introduction of structure;
  if $FGY = ((GY)^*, \cdot, \varepsilon)$ and $Y = (GY, +, 0)$ then
    \[ \epsilon_Y \varepsilon = 0
      \quad \epsilon_Y (y \cdot z) =  y + z
      \quad \epsilon_Y (y \in GY)  =  y
    \]

  \paragraph{}
  %
  Further, $T = G \circ F$ is a monad.  Generically, $\mu$...
  \begin{align*}
    \mu_X (TTX) &= (G \epsilon F)_X (TTX) = (G \epsilon_{FX}) (GFGFX) \\
       &= G ((\epsilon_{FX})(FGFX)) = GFX
  \end{align*}
  So here $\mu$ is the $G$-image of a function which takes $y \in FGFX =
  F(X^*)$ (that is, a concatenation of symbols from $GFX$) and re-imposes
  structure to obtain $\epsilon_{FX} y \in FX$.

% >>>
\section{Bootstrapping Category Theory} % <<<

  \paragraph{}
  %
  \defn[catcat]<@Cat>{$\mathbf{Cat}$} is the category which has locally
  small categories as objects and \hrdefn[functor]{functors} as morphisms.
  (It is not, itself, locally small, and so is not an object in itself.)
  $\mathbf{Cat}$ is \hrdefn{cartesian closed} (see \hrdefn{product category}
  and \hrdefn{exponential category}).  Its initial object is the empty
  category and its terminal object is the category of a single object and
  its identity morphism.

% >>>
% Footer <<<
\printindex

\bibliographystyle{alphaurl}
\bibliography{ctcheat}

\end{document}

% vim: ai:expandtab:ts=4:foldmethod=marker:foldmarker=<<<,>>>
% >>>