%
% file:         cat.tex
% purpose:      presentation of ``Category theory'' course
% created:      pasha aug 23,25,31,sep 1,7-10,15-20,23,29-30,oct 1,14,17-21 2018
% modified:     pasha nov 13-14 2020
% modification: fixed a typo and better notation in the def. of natural
%               transformation
%

\documentclass{beamer}

\usepackage{amscd,mathrsfs,graphicx}
\usepackage[all]{xy}

\newcommand{\vertbar}{\>|\>}
\newcommand{\set}[2]{\ensuremath{\{ #1 \vertbar #2 \}}}

\DeclareMathOperator{\id}{id}
\DeclareMathOperator{\rk}{rk}

\setcounter{framenumber}{-1}
\setbeamertemplate{navigation symbols}{}


\title{Category Theory}
%\author{Pasha Zusmanovich}
\institute{University of Ostrava}
\date{
Version of November 14, 2020
}


\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}
\titlepage
\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% from now on, display counters
\setbeamertemplate{headline} 
{
  \vskip2pt\hskip1pt\insertframenumber /\inserttotalframenumber 
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Literature}

\begin{itemize}

\item
J. Adamek, H. Herrlich, and G.E. Strecker, 
\emph{Abstract and Concrete Categories. The Joy of Cats}, Online edition, 2004
\\
(referred as {\sc Adamek et al.})

\item
G.M. Bergman, 
\emph{An Invitation to General Algebra and Universal Constructions}, 
2nd ed., Springer, 2015
\\
(referred as {\sc Bergman})

\item
S. Mac Lane, \emph{Categories for the Working Mathematician}, 2nd~ed., Springer,
1978.
\\
(referred as {\sc Mac Lane})

\item
S. Mac Lane and G. Birkhoff, \emph{Algebra}, 3rd ed., AMS Chelsea, 1999
\\
(referred as {\sc Mac Lane--Birkhoff})

\item
I.R. Shafarevich, Basic Notions of Algebra, Springer, 1990
\\
(referred as {\sc Shafarevich})

\end{itemize}

\vskip 0.6cm

\begin{center}
\footnotesize
(All images are courtesy of Wikipedia)
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}

\begin{center}
{\Huge 1. 

\bigskip

Definition of category, motivation. Examples of categories}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Motivation}

From the previous courses you (suppose to) know that:

\begin{itemize}
\item A linear map is a map between two vector spaces which preserves linearity.
\item 
A group homomorphism is a map between two groups which preserves the group 
multiplication, the neutral element, and the inverse operation.
\item
A (commutative) ring homomorphism is a map between two (commutative) rings which
is additive and preserves the ring multiplication.
\item
A continuous map is a map between two topological spaces which preserves the 
topological structure (i.e., open sets).
\end{itemize}

Do you see the pattern?

\medskip

Moreover, many statements about those maps (for example, composition of 
homomorphisms is a homomorphism) are formulated and proved exactly in the same 
way in all these cases. (For more such examples, see 
{\sc Bergman}, pp.~213--217, {\sc Mac~Lane}, pp.~1--5, and 
{\sc Shafarevich}, pp.~202--204).

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Definition}

A \emph{category} $\mathbf C$ consists of a class $Obj(\mathbf C)$ whose 
elements are called \emph{objects}, and a class $hom(\mathbf C)$ whose elements
are called \emph{morphisms} (or \emph{arrows}), such that there is a map 
$$
hom: Obj(\mathbf{C}) \times Obj(\mathbf{C}) \to 
\text{subsets of } hom(\mathbf{C})
$$
satisfying the following axioms:
\begin{enumerate}[\upshape(i)]

\item (Existence of composition)
For any $X,Y,Z \in Obj(\mathbf C)$, there is a map $\circ$, called a 
\emph{composition}
$$
\circ: hom(Y,Z) \times hom(X,Y) \to hom(X,Z)
$$

\item (Associativity)
If $X,Y,Z,W \in Obj(\mathbf C)$, and $h \in hom(Z,W)$, $g \in hom(Y,Z)$, 
$f \in hom(X,Y)$, then
$$
h \circ (g \circ f) = (h \circ g) \circ f .
$$

\item (Existence of identity)
For any $Y \in Obj(\mathbf C)$, there exists a morphism $1_Y \in \hom(Y,Y)$ such
that $1_Y \circ f = f$ for any $f \in hom(X,Y)$, and $g \circ 1_Y = g$ for any
$g \in hom(Y,Z)$.

\end{enumerate}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Examples of categories}

\begin{block}{Examples}
\begin{itemize}
\item
All sets (objects) and maps between them (morphisms) form the category of sets 
$\mathbf{Set}$.
\item
The classes mentioned at the first slide form respectively: the category of 
vector spaces $\mathbf{Vect}$, the category of groups $\mathbf{Group}$, the 
category of rings $\mathbf{Ring}$, the category of commutative rings 
$\mathbf{CommRing}$, and the category of topological spaces $\mathbf{Top}$.
\end{itemize}
\end{block}

For more examples, see 
{\sc Adamek at al.}, pp.~22--24,
{\sc Bergman},~pp.~221--226,
{\sc Mac Lane}, pp.~10--12,
{\sc Mac~Lane--Birkhoff},~pp.~496,498,
{\sc Shafarevich},~pp.~205--206.
See also an impressive list of all categories mentioned in {\sc Adamek et al.},
pp.~475--479.

\begin{block}{Exercise}
Why in the definition of category we are speaking about a ``class'' of objects 
and not about a set of objects? 
\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Dual category}

\begin{definition}
For a category $\mathbf{C}$, the \emph{dual} (or \emph{opposite}) 
\emph{category} $\mathbf{C^{op}}$ is the category having the same objects as $\mathbf{C}$, and for which 
$hom_{\mathbf{C^{op}}}(X,Y) = hom_{\mathbf{C}}(Y,X)$, and 
$f \circ^{op} g = g \circ f$.
\end{definition}

Informally, the dual category has the same morphisms, but in the ``opposite''
directions.

\begin{block}{Example}
If $\mathbf{C}$ is the category of ordered sets with the relation $\le$, then
$\mathbf{C^{op}}$ is the category of ordered sets with the relation $\ge$.

\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Subcategories}

Informally, a \emph{subcategory} of a category $\mathbf{C}$ a subclass of 
objects of $\mathbf{C}$, ``closed'' with respect to composition of morphisms.

\begin{block}{Exercise}
Give the precise definition of a subcategory of a category. 
\end{block}

\textbf{Hint}: see {\sc Mac~Lane--Birkhoff}, p.~498.

\begin{block}{Examples}
\begin{itemize}
\item 
Category of abelian groups $\mathbf{AbGroup}$ is a subcategory in 
$\mathbf{Group}$.
\item 
$\textbf{CommRing}$, and the category of fields are subcategories in 
\textbf{Ring}.
\end{itemize}
\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Product of categories}

The notion of cartesian product of two sets is readily extended to the case of
categories.

\begin{block}{Definition}
A \emph{product} of two categories $\mathbf{B}$ and $\mathbf{C}$, denoted by
$\mathbf{B} \times \mathbf{C}$, is defined as a category whose objects are
$Obj(\mathbf{B}) \times Obj(\mathbf{C})$, and whose arrows are 
$hom(\mathbf{B}) \times hom(\mathbf{C})$, and composition of arrows is performed
component-wise:
$$
(f,g) \circ (f^\prime, g^\prime) = (f \circ f^\prime, g \circ g^\prime)
$$
for suitable $f,f^\prime \in hom(\mathbf{B})$ and 
$g,g^\prime \in hom(\mathbf{C})$.
\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{A bit of history}

\linespread{0.80}\selectfont

{\small
Category theory was created by Samuel Eilenberg (1913--1998) and 
Saunders Mac Lane (1909--2005) around 1942--1945.
}

\begin{center}
\includegraphics[scale=0.43]{Samuel_Eilenberg_MFO.jpeg}
\includegraphics[scale=0.43]{Saunders_MacLane.jpg}
\end{center}

{\small
\linespread{0.90}\selectfont
``The devious and sophisticated European versus the innocent but honest 
American?'' (D. Eisenbud, from the preface to ``A Mathematical Autobiography''
by Saunders Mac Lane).
}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}

\begin{center}
{\Huge 2. 

\bigskip

Functors}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Covariant functor}

A functor is, an essence, a morphism (i.e., a map ``preserving the structure'')
of categories.

\begin{definition}
A \emph{covariant functor} (or just \emph{functor}) from a category $\mathbf C$
to a category $\mathbf D$ consists of two maps (denoted by abuse of notation by the same letter), 
$F: Obj(\mathbf C) \to Obj(\mathbf D)$ and $F: hom(X,Y) \to hom(F(X),F(Y))$ for
any $X,Y \in Obj(\mathbf C)$ satisfying the axioms:
\begin{enumerate}[\upshape(i)]
\item $F(1_X) = 1_{F(X)}$ for any $X \in Obj(\mathbf{C})$.
\item 
$F(f \circ g) = F(f) \circ F(g)$ for any morphisms $f,g$ whenever $f \circ g$
is defined.
\end{enumerate}
\end{definition}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Contravariant functor, bifunctor}

\begin{definition}
A \emph{contravariant functor} from a category $\mathbf C$ to a category 
$\mathbf D$ is obtained from the previous definition by replacing the second $F$
by $F: hom(X,Y) \to hom(F(Y),F(X))$, and the second axiom by:
\begin{enumerate}[\upshape(ii)]
\item 
$F(f \circ g) = F(g) \circ F(f) .$
\end{enumerate}
\end{definition}

\begin{block}{Exercise}
Rewrite the definitions of covariant and contravariant functor in terms of
commutative diagrams.
\end{block}

\textbf{Hint}: see {\sc Mac~Lane--Birkhoff},~pp.~131--132,504--505.

\bigskip

\begin{block}{Definition}
A \emph{bifunctor} from a pair of categories $\mathbf{B}$, $\mathbf{C}$ to a 
category $\mathbf{D}$ is a functor from $\mathbf{B} \times \mathbf{C}$ to $\mathbf{D}$.
\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Examples}

\begin{itemize}
\item 
The map assigning to a vector space its $n$-fold tensor product, is a covariant 
functor from $\textbf{Vect}$ to itself. (Prove this!)
\item
The map assigning to a commutative ring $A$ a group (say) $SL_n(A)$ is a 
functor from $\mathbf{CommRing}$ to $\textbf{Group}$.
\item
\emph{Forgetful functors}, where a part of the structure of the objects is 
``forgotten'', for example, the functor from \textbf{Group} to \textbf{Set},
sending a group to the underlying set.
\item
The cartesian product of two sets is a bifunctor 
$\mathbf{Set} \times \mathbf{Set} \to \mathbf{Set}$.
\item
The map sending a vector space to its adjoint is a contravariant functor. 
\end{itemize}

For more examples, see 
{\sc Adamek at al.}, pp.~30--32,
{\sc Bergman},~pp.~239--241,
{\sc Mac Lane}, pp.~13--14,35,
{\sc Mac~Lane--Birkhoff},~pp.~131--133,501--503,505--506,
{\sc Shafarevich}, pp.~208--213.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}

\begin{center}
{\Huge 3. 

\bigskip

Equivalence of categories}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Isomorphism of categories}

\begin{definition}
Two categories $\mathbf{C}$ and $\mathbf{D}$ are said \emph{isomorphic}, if
there exists a functor $F: \mathbf{C} \to \mathbf{D}$, called 
\emph{isomorphism}, such that there is an ``inverse'' functor 
$F^{-1}: \mathbf{D} \to \mathbf{C}$: $F^{-1} \circ F = \id_{\mathbf{C}}$ and 
$F \circ F^{-1} = \id_{\mathbf{D}}$.
\end{definition}

\begin{block}{Example}
\begin{itemize}
\item
The category of Boolean algebras is isomorphic to the category of Boolean rings.
\item
The category of left $R$-modules over a commutative ring $R$ is isomorphic to
the category of right $R$-modules.
\end{itemize}
\end{block}

For more examples of isomorphic categories, see {\sc Adamek et al.}, pp.~33--34.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Faithful and full functors}

Isomorphic categories are, essentially, ``the same'', and the concept of 
isomorphism of categories is very restrictive. The less weaker concept of 
equivalence of categories turns out to be more meaningful.

\bigskip

Let $\mathbf{C}$, $\mathbf{D}$ be two categories, and 
$F: \mathbf{C} \to \mathbf{D}$ a functor between them. For any two objects
$X,Y \in Obj(\mathbf{C})$, consider the hom-set restriction
$$
F: hom_{\mathbf C}(X,Y) \to hom_{\mathbf D}(F(X),F(Y)) .
$$

\begin{block}{Definition}
\begin{enumerate}
\item
A functor is called \emph{embedding} if it is injective on morphisms.
\item
A functor is called \emph{faithful} if all its hom-set restriction are
injective.
\item
A functor is called \emph{full} if all its hom-set restrictions are surjective.
\end{enumerate}
\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Examples}

The forgetful functor $\mathbf{Vect} \to \mathbf{Set}$ is faithful, but is 
neither full nor an embedding.

\bigskip

For further examples of embeddings, faithful, and full functors, see 
{\sc Adamek et al.}, pp.~34--35, and {\sc Bergman}, p.~244.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Equivalence of categories}

\begin{definition}
Two categories $\mathbf{C}$ and $\mathbf{D}$ are called \emph{equivalent}, if
there is a functor $F: \mathbf{C} \to \mathbf{D}$ which is faithful and full,
and for any object $Z \in Obj(\mathbf D)$, there is an object 
$X \in Obj(\mathbf C)$, such that $F(X) \simeq Z$.
\end{definition}

\begin{block}{Examples}
\begin{itemize}
\item
The category of matrices is equivalent of the category of $\mathbf{Vect}$, but 
not isomorphic to it.
\item
The category of finite-dimensional real vector space is equivalent to its dual
(each vector space is mapped to its adjoint).
\end{itemize}
\end{block}

For details and more examples of isomorphic and equivalent categories, see 
{\sc Adamek et al.}, pp.~36,38.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}

\begin{center}
{\Huge 4. 

\bigskip

Small and large categories, concrete categories}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Small categories}

\begin{definition}
A category is called \emph{small} if the class of its objects is a set, and
\emph{large} otherwise.
\end{definition}

\begin{block}{Lemma}
The class of morphisms in a small category is a set too.
\end{block}

\begin{block}{Examples}
\begin{itemize}
\item The category of matrices is small.
\item The category of (all) monoids is large. 
\end{itemize}
\end{block}

\begin{block}{Exercise}
Which of the categories considered so far are small?
\end{block}

\medskip

For more examples of small and large categories, see {\sc Adamek~et~al.}, p.~39
and {\sc Mac Lane}, pp.~24--26.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{The category \textbf{Cat}}

\begin{block}{Lemma}
All small categories form a category $\mathbf{Cat}$. The morphisms are functors
between categories.
\end{block}

\begin{block}{Exercise 1}
Is $\mathbf{Cat}$ small?
\end{block}

\begin{block}{Exercise 2}
Can we speak about category of all (not necessarily small) categories?
\end{block}

\textbf{Hint}: see {\sc Adamek et al.}, p.~39.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Concrete categories}

If we consider categories comprised of ``concrete'' objects, like vector or 
topological spaces, we loose some information, as the emphasis in ``abstract'' 
categories is not on objects themselves, but on relationship between them. The 
notion of concrete category aims to rectify this deficiency.

\begin{definition}
A category $\mathbf{C}$ is called \emph{concrete} if there is a faithful functor
(called the \emph{forgetful functor}) $\mathbf{C} \to \mathbf{Set}$.
\end{definition}

\begin{block}{Exercise}
Which of the categories considered so far are concrete?
\end{block}

\begin{block}{Theorem}
Every small category can be turned into a concrete one, i.e. admits a faithful
functor to the category of small sets. 
\end{block}

\medskip

For more examples of concrete categories, see {\sc Adamek et al.}, p.~62, and 
{\sc Mac~Lane--Birkhoff}, pp.~142--143,497.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Concrete functors}

\begin{definition}
Let $\mathbf{C}$ and $\mathbf{D}$ be two concrete categories, with the 
corresponding forgetful functors $U: \mathbf{C} \to \mathbf{Set}$ and 
$V: \mathbf{D} \to \mathbf{Set}$. A functor $F: \mathbf{C} \to \mathbf{D}$ is
called \emph{concrete}, if $U = V \circ F$.
\end{definition}

\begin{block}{Lemma}
Every concrete functor is faithful.
\end{block}

\begin{block}{Example}
The forgetful functor from the concrete category of rings to the concrete 
category of abelian groups which ``forgets multiplication'', is concrete.
\end{block}

For more examples, see {\sc Adamek et al.}, p.~66.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}

\begin{center}
{\Huge 5. 

\bigskip

Natural transformations}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Natural transformations}

The same way as functor provides a ``morphism'' between categories, natural 
transformation provides ``morphism'' between functors.

\begin{definition}
A \emph{natural transformation} between two functors $F, G$ from a category
$\mathbf{C}$ to a category $\mathbf{D}$, is a map 
$\tau: Obj(\mathbf{C}) \to hom(\mathbf{D})$, $X \mapsto \tau_X$, such that for
any $X,Y \in Obj(\mathbf{C})$, and any arrow $f \in hom(X,Y)$, the following diagram
$$\begin{CD}
F(X)     @>\tau_X>> G(X)      \\
@VF(f)VV             @VVG(f)V  \\
F(Y)     @>\tau_Y>> G(Y)
\end{CD}$$
is commutative.

If each $\tau_X$ is invertible, then $\tau$ is called a 
\emph{natural equivalence}.

The set of all natural transformations between $F$ and $G$ is denoted by 
$[F,G]$.
\end{definition}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Examples of natural transformations}

\begin{enumerate}
\item
The determinant, considered as a map $det: GL_n \to ()^*$, is a natural
transformation between two functors from $\mathbf{CommRing}$ to 
$\mathbf{Group}$.
\item
Abelianization of a group, i.e. the natural projection $G \to G/[G,G]$ for a 
group $G$, is a natural transformation between two functors from 
$\mathbf{Group}$ to $\mathbf{Group}$.
\end{enumerate}

\bigskip

For details and further examples, see {\sc Adamek~et~al.},~pp.~83--85, 
{\sc Bergman}, p.~280, {\sc Mac Lane}, pp.~16--18, and {\sc Mac~Lane--Birkhoff},~pp.~507--508.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}

\begin{center}
{\Huge 6. 

\bigskip

Universal constructions, limits, colimits}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Universal arrow}

\begin{definition}
If $S: \mathbf{D} \to \mathbf{C}$ is a functor between two categories 
$\mathbf{D}$ and $\mathbf{C}$, and $c \in Obj(\mathbf{C})$, a 
\emph{universal arrow} from $c$ to $S$ is a pair $(r,u)$ consisting of an 
object $r \in Obj(\mathbf{D})$, and an arrow $u: c \to S(r)$ of $\mathbf{C}$, 
such that to every pair $(d,f)$ with $d \in Obj(\mathbf{D})$ and $f: c \to S(d)$
an arrow of $\mathbf{C}$, there is a unique arrow $f^\prime: r \to d$ of 
$\mathbf{D}$ with $S(f^\prime) \circ u = f$.
\end{definition}

\begin{block}{Examples}
\begin{itemize}
\item 
A map sending an element of a base of a vector space, considered as a set,
to the same vector space, considered as an element of $\mathbf{Vect}$.
\item 
A map sending an integral domain to its field of quotients.
\end{itemize}
\end{block}

For details and other examples, see {\sc Bergman}, pp.~295--296, 
{\sc Mac~Lane}, pp.~56--57, and {\sc Mac~Lane--Birkhoff}, pp.~130--131.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Universal element}

An important particular case of an universal arrow is universal element.

\begin{definition}
If $\mathbf{D}$ is a category and $H: \mathbf{D} \to \mathbf{Set}$ a functor, a
\emph{universal element} of the functor $H$ is a pair $(r,e)$ consisting of an 
object $r \in \mathbf{D}$ and an element $e \in H(r)$ such that for every pair 
$(d,x)$ with $d \in Obj(\mathbf{D})$ and $x \in H(d)$, there is a unique
arrow $f: r \to d$ of $\mathbf{D}$ with $(H(f))(e) = x$.
\end{definition}

\bigskip

\begin{block}{Examples}
Partition of a set into equivalence classes, quotients of a group by 
a normal subgroup, and tensor products can be expressed in terms of a universal
element in appropriate categories. For details and other examples, see 
{\sc Mac Lane}, pp.~57--58.
\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Limit}

Important instances of universal constructions are limits and colimits.

\begin{definition}
Let $F: \mathbf{D} \to \mathbf{C}$ be a functor between two categories 
$\mathbf{D}$, $\mathbf{C}$. A \emph{limit} of $F$, denoted by $\varprojlim F$, 
is an object $L \in Obj(\mathbf C)$ such that for every $X \in Obj(\mathbf D)$
there is a morphism $p(X): L \to F(X)$ satisfying the following property: for
$f \in hom_{\mathbf D}(X,Y)$, one has $p(Y) = F(f)p(X)$. Moreover, $p$ is 
universal for this property, i.e., given any object $M \in Obj(\mathbf C)$, and
family of morphisms $m(X): M \to F(X)$, which similarly make commuting triangles
with the morphisms $F(f)$, there exists a unique morphism $h: M \to L$ such that for all $X$, $m(X) = p(X) \circ h$.
\end{definition}

\begin{block}{Examples of constructions described in terms of limits}
\begin{itemize}
\item
$p$-adic numbers, see 
{\sc Bergman}, pp.~317--323 or {\sc Mac Lane}, pp.~110-111.
\item
Formal power series.
\end{itemize}
\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Colimit}

Reversing arrows, we get the dual notion:

\begin{definition}
Let $F: \mathbf{D} \to \mathbf{C}$ be a functor between two categories 
$\mathbf{D}$, $\mathbf{C}$. A \emph{colimit} of $F$, denoted by $\varinjlim F$, 
is an object $L \in Obj(\mathbf C)$ such that for every $X \in Obj(\mathbf D)$
there is a morphism $q(X): F(X) \to L$ satisfying the following property: for
$f \in hom_{\mathbf D}(X,Y)$, one has $q(X) = q(Y)F(f)$. Moreover, $q$ is 
universal for this property, i.e., given any object $M \in Obj(\mathbf C)$, and
family of morphisms $m(X): F(X) \to M$, which similarly make commuting triangles
with the morphisms $F(f)$, there exists a unique morphism $h: L \to M$ such that
for all $X$, $m(X) = h \circ q(X)$.
\end{definition}

\bigskip

Warning: limits and colimits not always exist!

\bigskip

One of the main questions related to limits and colimits is when that or another
functor preserves them. See {\sc Adamek et al.}, pp.~223--226, 
{\sc Bergman et al.}, pp.~347--348,352 or {\sc Mac Lane}, pp.~116--118 for 
details.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Direct and inverse limits}

Important particular cases of limit and colimit are \emph{inverse} and 
\emph{direct} limit, respectively.  
\begin{align*}
&\text{inverse limit:} 
&\dots \leftarrow C_{n-1} \leftarrow C_n \leftarrow C_{n+1} \leftarrow \dots
\\
&\text{direct limit:} &\dots \to C_{n-1} \to C_n \to C_{n+1} \to \dots
\end{align*}

An example of inverse limit: direct product $\prod_{i\in I} A_i$.

An example of direct limit: direct sum $\bigoplus_{i\in I} A_i$.

\bigskip

A well known theological concept is that of the transcendental divine 
consciousness as a limit of restricted human consciousnesses. In this setup, 
optimist would say that this limit is a direct limit, while pessimist would say
that this is an inverse one.
(As seen somewhere on \href{https://mathoverflow.net/}{mathoverflow}).

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Exercise}

Rewrite all definitions from this section in terms of commutative diagrams.

\bigskip

\textbf{Hint}: See {\sc Mac Lane}, p.~55.


\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}

\begin{center}
{\Huge 7. 

\bigskip

The Yoneda Lemma}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{The Yoneda Lemma}

\begin{block}{Lemma}
Let $\mathbf{C}$ be a category, $F: \mathbf{C} \to \mathbf{Set}$ a functor, and
$X \in Obj(\mathbf{C})$. Then the map
\begin{align*}
[hom(X, -), F] &\to F(X) \\
\sigma &\mapsto \sigma_X(\id_X)
\end{align*}
is a bijection.
\end{block}

\begin{center}
\vskip -8pt
\raisebox{-65pt}{\includegraphics[width=.46\linewidth]{nobuo-yoneda-71765d70-6bd5-4ce0-9ac2-67f62b7da14-resize-750.jpg}}
Nobuo Yoneda (1930--1996) 
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{The Yoneda Lemma (cont.)}

Roughly, the Yoneda Lemma says that an object in a category is determined
by the functor that records morphisms from each of the objects of the category
(or, the object is best understood in the context of a category surrounding it).

\bigskip

The proof if the Yoneda Lemma uses the concept of universal arrows, see 
{\sc Mac Lane}, pp.~59--61 for details.

\bigskip

\begin{block}{Exercise}
The Yoneda Lemma is formulated for covariant functor $F$. Formulate and prove
the version of the Lemma for contravariant functor.
\end{block}

\textbf{Hint}: see {\sc Bergman}, pp.~300--301.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{The category of functors}

\begin{block}{Notation}
For two categories $\mathbf{C}$, $\mathbf{D}$, denote by 
$[\mathbf{C},\mathbf{D}]$ the set of all functors from $\mathbf{C}$ to 
$\mathbf{D}$.
\end{block}

\begin{block}{Theorem}
If $\mathbf{C}$ and $\mathbf{D}$ are small, then $[\mathbf{C},\mathbf{D}]$ forms
a category, with functors being natural transformations between functors.
\end{block}

\begin{block}{Exercise}
Does $[\mathbf{C},\mathbf{D}]$ forms a category in the similar way for 
arbitrary, not necessarily small $\mathbf{C}$ and $\mathbf{D}$?
\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{An embedding theorem}

\begin{block}{Theorem}
For any category $\mathbf{C}$, the functor 
$E: \mathbf{C} \to [\mathbf{C}^{op}, \mathbf{Set}]$, defined by
$$
E(X \overset{f}\to Y) = hom(-,X) \overset{\sigma_f}\to hom(-,Y) ,
$$
where $\sigma_f(g) = f \circ g$, is a full embedding.
\end{block}

\textbf{Proof}: This is an (easy) corollary of the Yoneda Lemma.

\bigskip

This theorem is a vast generalization of the theorem from group theory about
embedding of any group in a symmetric group, and similar results.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}

\begin{center}
{\Huge 8. 

\bigskip

Adjoint functors}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Adjoint functors}

\begin{definition}
Let $\mathbf{C}$, $\mathbf{D}$ be two categories, and 
$F: \mathbf{C} \to \mathbf{D}$, $G: \mathbf{D} \to \mathbf{C}$ two functors in
opposite directions between them. The functor $F$ is called a left adjoint to 
$G$, and $G$ is called a right adjoint to $F$, if for any objects 
$X \in Obj(\mathbf{C})$ and $Y \in Obj(\mathbf{D})$, there is a bijection of 
sets 
$$
hom(F(X),Y) \simeq hom(X,G(Y)) ,
$$ 
natural in the arguments $X$ and $Y$. 
\end{definition}

\begin{block}{Exercise}
Rewrite this definition using the notions of universal arrows or universal 
elements.
\end{block}

\textbf{Hint}: See {\sc Adamek et al.}, p.~305, or {\sc Bergman}, p.~309, or 
{\sc Mac Lane}, pp.~81--82.

\begin{block}{Warning}
Left/right adjoint functors not always exist!
\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Examples of adjoint functors}

\begin{block}{Examples}
\begin{itemize}
\item
Tensor product and Hom in the category of modules over a (commutative) ring.
\item
The functor $\mathbf{Set} \to \mathbf{Top}$ supplying each set with the discrete
topology, and the forgetful functor $\mathbf{Top} \to \mathbf{Set}$.
\item
The forgetful functor $\mathbf{Group} \to \mathbf{Set}$, and the functor
$\mathbf{Set} \to \mathbf{Group}$ assigning to a set $X$ the free group freely
generated by $X$.
\end{itemize}
\end{block}

For details and other examples, see {\sc Adamek et al.}, pp.~305,319, 
{\sc Bergman}, pp.~311--312, {\sc Mac Lane}, pp.~87,123--125, and 
{\sc Mac~Lane--Birkhoff},~p.~519.

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Properties of adjoint functors}

\begin{block}{Theorem 1}
Any two left(right)-adjoints of a given functor are naturally isomorphic.
\end{block}

\begin{block}{Theorem 2}
The composition of adjoint functors is adjoint.
\end{block}

\begin{block}{Theorem 3}
Adjoint functors preserve limits.
\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}

\begin{center}
{\Huge 9. 

\bigskip

Monoidal categories}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Definition of a monoidal category}

A \emph{monoidal category} is a category $\mathbf{C}$ equipped with bifunctor
$\otimes: \mathbf{C} \times \mathbf{C} \to \mathbf{C}$, and an object 
$I \in \mathbf{C}$, called the \emph{unit} (or \emph{identity}) \emph{object}
satisfying the following conditions:
\begin{enumerate}
\item (Associativity) There is a natural (in three arguments $A$, $B$, $C$)
isomorphism 
$\alpha_{A,B,C}: (A \otimes B) \otimes \otimes C \simeq A \otimes (B \otimes C)$.
\item (Identity) There are two natural isomorphisms 
$\lambda_A: E \otimes A \simeq A$ and $\rho_A: A \otimes E \simeq A$.
\item (Coherence)
For any $A,B,C,D \in Obj(\mathbf{C})$, the pentagonal diagram
% TeX code stolen from Wikipedia:
% https://commons.wikimedia.org/wiki/File:Monoidal_category_pentagon.svg
{\tiny
\begin{equation*}
\xymatrix@C=5em{
  ((A\otimes B)\otimes C)\otimes D\ar[d]_{\alpha_{A\otimes B,C,D}}\ar[r]^{\alpha_{A,B,C}\otimes {1_D}}
  &(A\otimes(B\otimes C))\otimes D\ar[r]^{\alpha_{A,B\otimes C,D}}
  &A\otimes((B\otimes C)\otimes D)\ar[d]^{{1_A}\otimes\alpha_{B,C,D}}\\
  (A\otimes B)\otimes(C\otimes D)\ar[rr]_{\alpha_{A,B,C\otimes D}}&&A\otimes(B\otimes (C\otimes D))
}
\end{equation*}
}
commutes.
\end{enumerate}

{\tiny to be continued ...}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Definition of a monoidal category (cont.)}

\begin{enumerate}

\setcounter{enumi}{4}
\item (Coherence)
For any $A,B,C \in Obj(\mathbf{C})$, the triangle diagram
% https://commons.wikimedia.org/wiki/File:Monoidal_category_triangle.svg
\begin{equation*}
\xymatrix@C=1em{
  (A\otimes I)\otimes B\ar[dr]_{\rho_A\otimes {1_B}}\ar[rr]^{\alpha_{A,I,B}}&&\ar[dl]^{{1_A} \otimes\lambda_B}A\otimes(I\otimes B)\\
  &A\otimes B&
}
\end{equation*}
commutes.
\end{enumerate}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Examples of monoidal categories}

Informally, a category is monoidal if it is equipped with a ``product'' which is
associative up to isomorphism.

\bigskip

\begin{block}{Examples}
\begin{enumerate}
\item 
$\mathbf{Set}$ with respect to cartesian product.
\item
$\mathbf{Vect}$, and, more generally, the category of modules over a fixed 
commutative ring, with respect to tensor product.
\item
The category of associative algebras with respect to tensor product.
\item
$\mathbf{Top}$ with respect to the product of topological spaces.
\item
$\mathbf{Cat}$ with respect to the product of categories.
\end{enumerate}
\end{block}

\begin{block}{Exercise}
What will serve as a unit in each of these examples?
\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}

\begin{center}
{\Huge 10. 

\bigskip

Categorification}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Categorification}

Categorification is a process of replacing set-theoretic concepts and statements
by their category-theoretic analogues. It allows to reveal hidden structures in
mathematics, and bring them to a newer level of understanding.

\bigskip

\begin{tabular}{|l|l|}
\hline
\bf{set-theoretic notion} & \bf{category-theoretic counterpart} \\
\hline
set      & category \\ 
\hline
elements & objects  \\
\hline
function & functor  \\
\hline
equation & natural transformation \\
\hline
\end{tabular}

\bigskip

\begin{block}{Examples}
\begin{itemize}
\item
Natural numbers $\rightsquigarrow$ Cardinalities of finite sets.
\item
Symmetric functions $\rightsquigarrow$ Representations of the symmetric group.
\item
Monoid (a set with an associative binary operation and a unit) 
$\rightsquigarrow$ Monoidal category.
\end{itemize}
\end{block}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Another (historical) example}

One of the earlier examples of categorification is the replacement of Betti 
numbers by (co)homology groups (whose ranks are Betti numbers), done by Emmy 
Noether in 1920s-1930s. This gave birth to the homological algebra.

\begin{center}
$b_i = \rk H_i(X,\mathbb Q)$ \\
$b_0, b_1, b_2, \dots \rightsquigarrow$
\raisebox{-100pt}{\includegraphics[scale=0.40]{Noether.jpg}}
$\rightsquigarrow H_0, H_1, H_2, \dots$
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}

\begin{center}
{\Huge 11. 

\bigskip

Applications in computer science (functional programming, database design)}

\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Applications in functional programming}

Category theory, due its generality and flexibility, is vastly applicable in
computer science. Below are just a few examples.

\bigskip

A central concept in Haskell and other functional programming languages, used in
sequential computations, is that of monad which comes from category theory. 
Roughly, a \emph{monad} is a categorical generalization of a closure operator on
a partially ordered set. Monad is a functor from a category to itself, equipped
with two natural transformations, which give it a monoid-like structure. For an
exact definition, see {\sc Mac Lane}, pp.~137--138.

\end{frame}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Applications in database design}

\begin{enumerate}
\item
Databases, and, more generally, knowledge bases, can be represented as a special
kind of automata: a database query brings the automaton to another state, 
producing the answer to the query. One of important and complicated question
in the theory of databases is whether two databases are, essentially, the 
``same'', i.e. produce the same answers to the same queries. This question may 
be approached using the representation above, considering the category of all 
databases as a subcategory of the category of automata, and employing the 
notion of equivalence of categories.

\item
Alternatively, database schemas may be represented as categories, with functors
representing migration from one schema to another (a task frequently needed to
be performed on practice).

\item
For finite state machines, ``minimal realization'' and ``behavior'' could be
considered as adjoint functors. See {\sc Mac~Lane}, p.~89 for details.
\end{enumerate}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{}

\begin{center}
{\Huge 12. 

\bigskip

$2$-categories and applications in physics 
(string theory, topological quantum field theory)
}

\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{Braided categories in physics}

A \emph{braided category} is a monoidal category equipped with braiding, i.e.
the commutativity natural isomorphism 
$\gamma_{A,B}: A \otimes B \to B \otimes A$ satisfying additional identities 
which are satisfied in the braid group. 

\bigskip

In string theory, particles are represented as strings weaving around each 
other, so the concepts of braids and of braided category are applicable. See
{\sc Mac Lane}, pp.~260--266 for details.

\begin{center}
\includegraphics[scale=0.95]{Braid_s1_inv_alt.png}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}{$2$-categories}

An ordinary category has objects and morphisms ($1$-morphisms). A $2$-category 
extends this by including ``morphisms between morphisms'' ($2$-morphisms).
Thus, in a sense, $2$-categories are categorifications of ordinary categories.
See {\sc Mac Lane}, pp.~272--279 for details.

\begin{block}{Example}
$\mathbf{Cat}$ is actually a $2$-category.
\end{block}

\bigskip

$2$-categories is another categorical concept used in string theory.
Transformations of strings, which can be considered as morphisms in an 
appropriate category, as they move along surfaces in spacetime, can be 
considered as $2$-morphisms:
$$
\begin{xy}
(-10,0)*+{\bullet}="left"; (10,0)*+{\bullet}="right";
{\ar@/^1.25pc/ "left";"right"};
{\ar@/_1.25pc/ "left";"right"};
{\ar@{=>} (0,3)*{};(0,-3)*{}} ;
\end{xy}
$$

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{frame}

\begin{center}
{\Huge The End}
\end{center}

\end{frame}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
% eof
