Skip to content
Snippets Groups Projects
Exercises.tex 129 KiB
Newer Older
Nicola Capacci's avatar
Nicola Capacci committed
\documentclass{amsart}
\usepackage[foot]{amsaddr}
\usepackage{bbm}
\usepackage{mathbbol}
\usepackage{amsmath,amssymb,amsfonts, amsthm, graphicx}
\usepackage{mathtools}
Jessica Lam Jia Hong's avatar
Jessica Lam Jia Hong committed
\usepackage{stmaryrd}
Nicola Capacci's avatar
Nicola Capacci committed
\usepackage{graphicx}%for \rotatebox
\usepackage[dvipsnames]{xcolor}
\usepackage{txfonts}
\usepackage{tikz}
\usetikzlibrary{arrows,shapes,snakes,automata,backgrounds,petri,positioning}
\usepackage{comment}
\usepackage[pdfborder=0,colorlinks=true,linktocpage,linkcolor=blue,urlcolor=cyan]{hyperref}
\usepackage{csquotes}
\usepackage{comment}
\usepackage[normalem]{ulem}
\usepackage{enumerate}
\usepackage{verbatim}
\usepackage{xcolor}
\usepackage{amsmath}
%\usepackage{fullpage}

\setlength{\textwidth}{\paperwidth}
\addtolength{\textwidth}{-2in}
\calclayout

%diagram stuff
%try:  https://tikzcd.yichuanshen.de/
%xymatrix
Rizacan Çiloglu's avatar
Rizacan Çiloglu committed
\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt
Nicola Capacci's avatar
Nicola Capacci committed
\usepackage[all,pdftex, cmtip]{xy}
\newdir{ >}{{}*!/-10pt/@{>}}
\newdir{> }{{}*!/10pt/@{>}}
\newcommand{\cd}[2][]{\vcenter{\hbox{\xymatrix#1{#2}}}}
\newcommand{\ltwocell}[3][0.5]{\ar@{}[#2] \ar@{=>}?(#1)+/r 0.2cm/;?(#1)+/l 0.2cm/_{#3}}

\newcommand{\hdash}{\rotatebox[origin=c]{90}{$\vdash$}}

%tikz-cd
\usepackage{amssymb}
\usepackage{tikz}
\usetikzlibrary{cd}
\usepackage{tikz-cd}
\tikzset{% for drawing adjunctions
    symbol/.style={%
        draw=none,
        every to/.append style={%
            edge node={node [sloped, allow upside down, auto=false]{$#1$}}}
    }
}

%roman enumeration
\usepackage{enumerate}
\newenvironment{enumroman}{\begin{enumerate}[\upshape (i)]}{\end{enumerate}}
\renewcommand{\theenumi}{\roman{enumi}}

%blackboard bold numbers and stuff
\newcommand{\bbefamily}{\fontencoding{U}\fontfamily{bbold}\selectfont}
\newcommand{\textbbe}[1]{{\bbefamily #1}}
\DeclareMathAlphabet{\mathbbe}{U}{bbold}{m}{n}

%theorem stuff
\theoremstyle{plain}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{claim}[thm]{Claim}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{lem}[thm]{Lemma}

\theoremstyle{definition}
\newtheorem{defn}[thm]{Definition}
\newtheorem{digression}[thm]{Digression}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{const}[thm]{Construction}

\theoremstyle{remark}
\newtheorem{ex}[thm]{Example}
\newtheorem{rmk}[thm]{Remark}
\newtheorem{notation}[thm]{Notation}

%numbering
\setcounter{tocdepth}{1}
\makeatletter
\let\c@equation\c@thm
\makeatother
\numberwithin{equation}{section}

%r arrows double headed with \simeq symbol
\newcommand{\refinement}{%
  \xrightarrow{\simeq}\mathrel{\mkern-14mu}\rightarrow
}
\usepackage{extarrows}

%bra-ket notation
\usepackage{mathtools}
\DeclarePairedDelimiter\bra{\langle}{\rvert}
\DeclarePairedDelimiter\ket{\lvert}{\rangle}
\DeclarePairedDelimiterX\braket[2]{\langle}{\rangle}{#1 \delimsize\vert #2}

Nicola Capacci's avatar
Nicola Capacci committed
%Yoneda 
\usepackage[utf8]{inputenc}
\DeclareFontFamily{U}{min}{}
\DeclareFontShape{U}{min}{m}{n}{<-> udmj30}{}
\newcommand\yo{\!\text{\usefont{U}{min}{m}{n}\symbol{'207}}\!}

\usepackage{bbm}


Nicola Capacci's avatar
Nicola Capacci committed
%categories
\newcommand{\cat}[1]{\textup{\textsf{#1}}}% for categories
\newcommand{\Set}{\operatorname{\mathbf{Set}}}
\newcommand{\mat}{\operatorname{\mathbf{Mat}}}
\newcommand{\Cat}{\operatorname{\mathbf{Cat}}}
\newcommand{\Vect}[1]{\mathbf{Vect}_{#1}}%
\newcommand{\yonenr}[1]{\mathfrak Y_{#1}}%
\newcommand{\functorcat}[2]{[#1,#2]}%
\newcommand{\map}{\textbf{Map}}
\newcommand{\Map}{\operatorname{\mathbf{Map}}}
Nicola Capacci's avatar
Nicola Capacci committed
\newcommand{\Id}{\mathrm{Id}}
Nicola Capacci's avatar
Nicola Capacci committed
\newcommand{\FVect}{\mathbf{FVect}}
\newcommand{\Field}{\operatorname{\mathbf{Field}}}

%blackboard bold
\newcommand{\ff}{\mathbb{F}}
\newcommand{\nn}{\mathbb{N}}
\newcommand{\rr}{\mathbb{R}}
\newcommand{\qq}{\mathbb{Q}}
\newcommand{\BB}{\mathbb{B}}

%big plus symbol
\usepackage{amsmath}
\DeclareMathOperator*{\foo}{\scalerel*{+}{\sum}}
\DeclareMathOperator*{\barr}{\scalerel*{+}{\textstyle\sum}}
\usepackage{scalerel}


%calligraphic
\newcommand{\Ca}{\mathcal{C}}
\newcommand{\Oa}{\mathrm{Sub}}
\newcommand{\Da}{\mathcal{C}}
\newcommand{\Ea}{\mathcal{E}}
\newcommand{\Ba}{\mathcal{B}}

%misc shortcuts
\newcommand{\lra}{\longrightarrow}
\newcommand{\xto}[1]{\xrightarrow{#1}}
\newcommand{\op}{^\text{op}}
Nicola Capacci's avatar
Nicola Capacci committed
\newcommand{\id}{\mathrm{id}}
Nicola Capacci's avatar
Nicola Capacci committed
\newcommand{\inv}{^{-1}}
\newcommand{\End}{\operatorname{End}}
\newcommand{\Sub}{\operatorname{Sub}}
\newcommand{\Left}{\operatorname{Left}}
\newcommand{\Right}{\operatorname{Right}}
\newcommand{\Cov}{\operatorname{Cov}}
\DeclareMathOperator{\Hom}{Hom}

\allowdisplaybreaks

%use this to identify who is writing; LaTeX gurus please feel free to fiddle with the macro
Nicola Capacci's avatar
Nicola Capacci committed
\newcommand{\iam}[1]{\vspace{.1cm}{\fbox{\textbf{#1}}}\vspace{.1cm}}
Nicola Capacci's avatar
Nicola Capacci committed


\usepackage{float}
%%--------------------------------------


\begin{document}
\title{Introduction to Category Theory}




\address{ $\dagger$ Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190 CH-8057 Zürich}



%\begin{abstract}
%\end{abstract}


\maketitle

\tableofcontents

%%--------------------------------------
Nicola Capacci's avatar
Nicola Capacci committed
\section{Instructions}
Welcome one and all to our shared exercise sheet! The purpose of this space is two-fold. Firstly, because the only way to learn is to do, and listening to your peer's talks is not enough to understand category theory. Secondly, because our goal is vast, and if we were to cover the whole book (plus our extra topics at the end) we would need twice as much time. 

In class the speaker will always explain the most important topics, but you should always try, before or after the lecture, to read the relevant chapter on your own and attempt one of the questions below. These will allow you a chance to learn, and the speaker an excuse to skip the less interesting topics.
Nicola Capacci's avatar
Nicola Capacci committed
\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\begin{itemize}
\item Questions, answers and comments will be posted the following way: 
\end{itemize}
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} What is the most creative color?\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Rizacan Çiloglu's avatar
Rizacan Çiloglu committed
\iam{Student}
Nicola Capacci's avatar
Nicola Capacci committed
I don't know but it is not green.

\iam{An Other Student}
YELLOW!

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} The next Question...\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed
\begin{itemize}
\item Remember to sign you name using the \textbackslash  iam\{\}  command. Try to answer these questions without fear, ask your fellow students about their answers, or even post questions of your own!

\item If you would like to draw simple diagram you can do so here https://tikzcd.yichuanshen.de and insert them in the tex file as follows (see code)
Nicola Capacci's avatar
Nicola Capacci committed

\begin{center}
% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZABgBpiBdUkANwEMAbAVxiRAEEQBfU9TXfIRQAmclVqMWbAELdeIDNjwEio4ePrNWiEAGFu4mFADm8IqABmAJwgBbJGRA4ISAIzVNUnRbmWb9xHcnF0RRCS02Y18QazsHamckMM9tEGMAHXSAYywrLIACH2oGOgAjGAYABX5lIRArLGMACxwDLiA
\begin{tikzcd}
A \arrow[rr, "f"] \arrow[rrdd, "g\circ f"'] &  & B \arrow[dd, "g"] \\
                                            &  &                   \\
                                            &  & C                
\end{tikzcd}
\end{center}
Nicola Capacci's avatar
Nicola Capacci committed
\end{itemize}
Nicola Capacci's avatar
Nicola Capacci committed
\section{Week 1}
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} \label{Rel} The category \textbf{Rel} has as objects sets and morphisms $f:A\to B$ are \emph{relations}, that is subsets of the form $f\subseteq A\times B$. Composition in this category is given by
Nicola Capacci's avatar
Nicola Capacci committed
\begin{align*}
g\circ f = \{ (a,c)\in A\times C \,|\, \exists b\in B \,\,\text{with}\,\, (a,b)\in f, (b,c)\in g\}
\end{align*}
for $f\in A\times B$ and $g\in B\times C$. Show that \textbf{Rel} satisfies the axioms of a category. What is the identity morphism?\hfill \break

Sophie Schmidhuber's avatar
Sophie Schmidhuber committed
\iam{Sophie} 
\begin{enumerate}
\item Associativity: Let A, B, C, D be sets and $f:A\to B$, $g:B\to C$  $h:C\to D$
Then we have 
\begin{align*}
h\circ (g \circ f) &= \{(a,d)\in A\times D \,|\, \exists c\in C \,\,\text{with}\,\, (a,c) \in g\circ f, (c,d) \in h\}
\\
&=\{(a,d)\in A\times D \,|\, \exists b\in B, \, \exists c\in C\,\text{with}\,\, (a,b) \in f, (b,c) \in g, (c,d) \in h\}
\\
&= \{(a,d)\in A\times D \,|\, \exists b\in B \,\,\text{with}\,\, (a,b) \in f, (b,d) \in h\circ g\}
\\
&=(h\circ g)\circ f 
\end{align*}
\item Identity Morphism: For any set A, let $\id_A := \{(a,b) \in A\times A \,| \ a = b\} $ . Then for any morphism $f:A\to B$, if (a,b) $\in$ f then (a,b) $\in f\circ \id_A$ , using (a,a) $\in \id_A$. Conversely if (a,b) $\in f\circ \id_A$, then (a,a) $\in \id_A$ and thus (a,b) $\in f$. This shows $f=f\circ \id_A$. In the same way we can show that for any morphism $g:C\to A$ we have that $g=\id_A \circ g$.
\end{enumerate}
OlgaB08's avatar
OlgaB08 committed
=======\\
OlgaB08's avatar
OlgaB08 committed
\iam{Olga}
According to p.5 of Awodey's book we have to show that associativity and identity laws hold true:\\

OlgaB08's avatar
OlgaB08 committed
1. Associativity:\\
For any $f : A \rightarrow B$, $f : B \rightarrow C$, $f : C \rightarrow D$ morphisms in the category \textbf{Rel}:\\
OlgaB08's avatar
OlgaB08 committed
\begin{align*}
h\circ (g\circ f ) = h \circ \{(a,c)\in A \times C \,|\, \exists \,b  \in B \, \text with \, (a,b)\in f, (b,c)\in g \} \\
= \{(a,d)\in A \times D \,|\, \exists \,c  \in C \, \text with \, (a,c)\in g\circ f, (c,d)\in h \, \\
\text{and} \, \exists \, b  \in B \, \text with \, (a,b)\in f, (b,c)\in g \}\\
= \{(a,d)\in A \times D \,|\, \exists \, b  \in B \, \text with \, (a,b)\in f, (b,d)\in h\circ g \\
\text{and} \, \exists \, c  \in C \, \text with \, (b,c)\in g, (c,d)\in h \}\\
=(h\circ g) \circ f
\end{align*}\\
2. Unit: \\
We have the following identity morphism:
\begin{align*}
1_A = \{ (a,a) \, \in A\times A \, | a\in A\} \subseteq A\times A
\end{align*}
Let $f : A \rightarrow B$ be a binary relation, then:
\begin{align*}
f\circ 1_A = \{ (a,b) \in A\times B \, | \, \exists \, a\in A \, \text{with} \, (a,a)\in 1_A , (a,b) \in f\} = f = \{ (a,b) \in A\times B \, | \, \exists \, b\in B \, \text{with} (a,b) \in f, (b,b)\in 1_B \}  = 1_B\circ f 
\end{align*}
where we have used the fact that identity arrow exists for each object A and B.\hfill \break

Sophie Schmidhuber's avatar
Sophie Schmidhuber committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} For a fixed set $X$, we call $\mathcal{P}(X)$ its \emph{power set}. This is the set of all subsets of $X$. Show how this has naturally the structure of a poset (so in particular a simple category) using subset inclusions.\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Arno's avatar
Arno committed
\iam{Arno} We have to check three properties, reflexivity, transitivity and antisymetry. \\
1. Reflexivity: Clearly this holds, since every set is contained in itself.\\
2. Transitivity: Checking this on elements gives us this result.\\
3. Antisymmetry: If two sets are simultainiously contained in one another, they have to have the exact same elements, hence are equal as sets.

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{}  Check that functors compose in an associative way, proving that $\mathbf{Cat}$ is a category. \hfill \break

Muhammed Guelen's avatar
Muhammed Guelen committed
\iam{Muhammed}  Let $\mathbf{C_1}, \mathbf{C_2}, \mathbf{C_3}, \mathbf{C_4}$ be  categories and $F: \mathbf{C_1} \to \mathbf{C_2}, \, G: \mathbf{C_2} \to \mathbf{C_3}, \, H: \mathbf{C_3} \to \mathbf{C_4}$ functors. We consider 
$$K:= G \circ F:  \mathbf{C_1} \to  \mathbf{C_3},$$
where for any object $A$ and any arrow $f$ in $\mathbf{C_1}$, $$
K(A) := G(F(A))  \quad \text{and} \quad K(f) := G(F(f)) \quad \quad (2.3.1)$$
We show that $K$ is a functor. \\ Let $A,B$ be objects and $f: A \to B, \, g: B \to C$ arrows in $\mathbf{C_1}$. \begin{enumerate}
\item Since $F,G$ are functors, $F(f): F(A) \to F(B)$ and $G(F(f)): G(F(A)) \to G(F(B))$. Thus, $K(f): (G \circ F)(A) \to (G \circ F)(B)$.
\item $(G \circ F)(f \circ g) := G(F(f \circ g)) = G(F(f) \circ F(g))= G(F(f)) \circ G(F(g))$.
\item $K(1_A) := G(F(1_A)) = G(1_{F(A)}) = 1_{G(F(A))} =: 1_{(G \circ F)(A)}$
\end{enumerate}
Also, clearly, $K(A)$ is an object in $\mathbf{C_3}$. This proves the assertion that $K$ is a functor.\\
To show associativity of the composition, we require
$$
Muhammed Guelen's avatar
Muhammed Guelen committed
H \circ (G \circ F) = (H \circ G) \circ F \quad (2.3.2) 
Muhammed Guelen's avatar
Muhammed Guelen committed
$$ 
where both sides are functors from $\mathbf{C_1}$ to $\mathbf{C_4}$ by previous considerations.
Now, by (2.3.1), it readily follows that, 
$$
Muhammed Guelen's avatar
Muhammed Guelen committed
(H \circ (G \circ F))(A) = H((G \circ F)(A)) = H(G(F(A))) = (H \circ G)(F(A)) = ((H \circ G) \circ F)(A) 
Muhammed Guelen's avatar
Muhammed Guelen committed
$$
and
$$(H \circ (G \circ F))(f) = H((G \circ F)(f)) = H(G(F(f))) = (H \circ G)(F(f)) = ((H \circ G) \circ F)(f)$$
for every any object $A$ and any arrow $f$ in $\mathbf{C_1}$. This yields the desired equality stated in (2.3.2).


Nicola Capacci's avatar
Nicola Capacci committed
\subsection{}  Prove that inverses are unique. \hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Rizacan Çiloglu's avatar
Rizacan Çiloglu committed
\iam{Rızacan} Let $f$ be an arrow with Cod($f$)=$B$ and Dom($f$)=$A$. Suppose
Rizacan Çiloglu's avatar
Rizacan Çiloglu committed
$g,g'$ are both inverses of $f$. Then by associativity and properties of
the identity: $g'=\id_A\circ
Rizacan Çiloglu's avatar
Rizacan Çiloglu committed
g'=(g\circ f)\circ g'= g\circ(f\circ g')=g\circ \id_B=g$.
Nicola Capacci's avatar
Nicola Capacci committed

Rizacan Çiloglu's avatar
Rizacan Çiloglu committed

Marius Furter's avatar
Marius Furter committed
z\subsection{} Argue whether the following \emph{isomorphisms} of categories hold:
Nicola Capacci's avatar
Nicola Capacci committed
\begin{enumerate}
\item $\mathbf{Rel}\cong \mathbf{Rel}^{op}$;
\item $\mathbf{Set}\cong \mathbf{Set}^{op}$;
\item For a fixed set $X$, $\mathcal{P}(X)\cong \mathcal{P}(X)^{op}$.
\end{enumerate}\hfill \break

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Show that in $\mathbf{Set}$ isomorphisms are bijections.\hfill \break

Raphael Mathyer's avatar
Raphael Mathyer committed
\iam{Raphael} Let $f\in \mathbf{Set}(X,Y)$ be an isomorphism of sets, i.e. a morphism so that there is another morphism $g:Y\rightarrow X$ with
$g\circ f=\id_X$ and $f\circ g=\id_Y$.\\
Injectivity: Let $x_1,x_2\in X$ with $f(x_1)=f(x_2)$, then composing $g$ to the left implies immediately $x_1=x_2$ as a direct consequence of the definition of an isomorphism.\\
Surjectivity: Let $y\in Y$ be arbitrary and define $x=g(y)$, then $f(x)=f(g(y))=\id_Y(y)=y$.\\
This shows, that $f$ is indeed a bijection.

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Show that in $\mathbf{Mon}$, the category of monoids, isomorphisms are bijective homomorphisms.\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Andreas's avatar
Andreas committed
\iam{Andreas} Updated: Let $N,M$ be two monoids and $f:N\to M$ be a monoid homomorphismus. Suppose $f$ is a bijective homomorphismus, this means there exist an $n\in N$ such that $f(n)=m$ for every $m\in M$ by surjectivity and since $f$ is injective this $n$ is unique and we can define $g:M\to N$ as $g(m)=n$. So we have $g(f(n))=n$ respectively $f(g(m))=m$ and thus $g\circ f=1_N$ and $f\circ g=1_M$. We try to show that $g$ is a monoid homomorphismus too: let $m_1,m_2\in M$, then
Andreas's avatar
Andreas committed
we have $$f(g(m_1)g(m_2))=f(g(m_1))f(g(m_2))=m_1m_2=f(g(m_1m_2))$$ Since we assume $f$ is bijective it follows that
$$g(m_1m_2)=g(m_1)g(m_2)$$
and thus a group homomorphism, hence a bijective homomorphism is an isomorphism in the category $\textbf{Mon}$.

Nicola Capacci's avatar
Nicola Capacci committed
\iam{Nicola} I'm not convinced by your logical argument. You assume that $f$ is a bijective homomorphism, then in the next sentence you follow with the existence of $g$. But this is true if you assume that $f$ is an iso (by definition), which is what you want to prove!

 Perhaps this argument is better stated as ``...\emph{then there exists a map of sets $U(g):U(M)\to U(N)$ such that ...}'', where $U:\mathbf{Mon}\to \mathbf{Set}$ is the functor that forgets about the multiplication. This is a small point, but for these types of arguments is important to value precision. 
 
 
Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Show that in $\mathbf{Pos}$, the category of posets, isomorphisms are \emph{not} bijective homomorphisms.\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Marius Furter's avatar
Marius Furter committed
\iam{Marius} Consider the posets $\mathcal{P} := 
	\begin{tikzcd}[cramped, sep=scriptsize]
	a \arrow[loop, distance=1.2em, in=115, out=65] & b \arrow[loop, distance=1.2em, in=115, out=65]
	\end{tikzcd}$ and $\mathcal{Q} := 
	\begin{tikzcd}[cramped, sep=scriptsize]
	a' \arrow[loop, distance=1.2em, in=115, out=65] \arrow[r] & b' \arrow[loop, distance=1.2em, in=115, out=65]
	\end{tikzcd}$, along with the map $f: \mathcal{P} \rightarrow \mathcal{Q}$ sending $a \mapsto a'$, and $b \mapsto b'$. Clearly, $f$ is bijective and monotone. However, it has no inverse: There are exactly two monotone maps from $\mathcal{Q}$ to $\mathcal{P}$, one sending both $a',b' \mapsto a$, and another sending both $a',b' \mapsto b$. Since neither is surjective, we can't recover the identity on $\mathcal{P}$ by pre-composing with $f$. Hence, $f$ is a bijective homomorphism which is not an isomorphism, as desired.

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Construct the co-slice category $A\downarrow \mathbf{C}$, of objects of $\mathbf{C}$ ``under'' $A$, using the slice category $\mathbf{C}\downarrow A$ and the operation $(-)^{op}$. Prove your claim.\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} How many \emph{free categories} are there with 6 arrows? \emph{Hint:} Try to draw them on a piece of paper, and if you feel industrious you can report them here using this online tool https://tikzcd.yichuanshen.de/ \hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Jessica Lam Jia Hong's avatar
Jessica Lam Jia Hong committed
\iam{Jessica} Consider quivers with at most 6 vertices (otherwise there would be already more than 6 identity arrows). Quivers with edges such that loops become valid paths are not considered, since it would have an arrow for every finite path involving the loop. 

To see an example of this, let $Q$ be the quiver with two vertices $a, b$ and two edges $a \stackrel{f}{\rightarrow} b,\ b \stackrel{g}{\rightarrow} a$. The free category on $Q$ then has two identity arrows on the vertices and an arrow for every finite sequence involving the loop, including $f,\ g,\ g \circ f,\ f \circ g,\ f \circ g \circ f,\ g \circ f \circ g$ etc. 

Keeping the above in mind, we have below the drawings of all possible quivers (without the identity paths) such that the free categories on them have precisely 6 arrows. 

\textbf{\# vertex = 1}. Since loops are not allowed, the quiver with only one vertex is not considered. 

\textbf{\# vertices = 2}. Only one quiver is possible. On top of the two identity arrows, the free category on this has four arrows from one vertex to the other vertex like so:
\[
	\begin{tikzcd}
	A \arrow[r, shift left] \arrow[r, bend left] \arrow[r, shift right] \arrow[r, bend right] & B
	\end{tikzcd}
\]

\textbf{\# vertices = 3}. Four quivers are possible. On top of the three identity arrows, the free categories on these have exactly three more possible arrows as shown in the diagrams below (the third arrow of the first quiver is $g \circ f$). 
\[
	\begin{tikzcd}
	A \arrow[r, "f"] & B \arrow[d, "g"] &  & \
	A \arrow[rd] \arrow[rd, bend right] \arrow[r] & B &  & \
	A \arrow[rd] \arrow[rd, bend right] & B \arrow[d] &  & \
	A \arrow[r] \arrow[r, bend right] \arrow[r, bend left] & B \ \\
	& C   &  &   & C   &  &   & C   &  &   & C
	\end{tikzcd}
\]

\textbf{\# vertices = 4}. Four quivers are possible. On top of the four identity arrows, the free categories on these exactly two more possible arrows as shown below:
\[
	\begin{tikzcd}
	A \arrow[r, shift left] \arrow[d] & B &  & A \arrow[r] & B &  & A \arrow[r]  & B &  & A \arrow[r, shift right] \arrow[r, shift left] & B \\
	D                                 & C &  & D \arrow[r] & C &  & D \arrow[ru] & C &  & D                                              & C
	\end{tikzcd}
\]

\textbf{\# vertices = 5}. Only one quiver is possible. On top of the five identity arrows, the free category on this has one arrow from a vertex to another vertex like so: 
\[
	\begin{tikzcd}
	A \arrow[r] & B \\
	D           & C  & E
	\end{tikzcd}
\]

\textbf{\# vertices = 6}. Only one quiver is possible, and it has no arrows aside from the six identity arrows. 

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} (\emph{Harder}) Prove the universal mapping property of free categories on graphs. \hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\section{Discussion: Week 1}
Nicola Capacci's avatar
Nicola Capacci committed

Severin Schraven's avatar
Severin Schraven committed
\iam{Severin} I find it useful to also allow for some informal discussion in this file. Nicola also agreed on that. So if there is a statement that puzzles you, it probably will be also confusing for the other people.
Nicola Capacci's avatar
Nicola Capacci committed

Severin Schraven's avatar
Severin Schraven committed
\iam{Severin} IN Awodey, p. 22 it says "For example, all finite categories are clearly small, as is the category $\textbf{Sets}_{\text{fin}}$ of finite sets and functions." This confused me a bit, as it is not true. Indeed, we can consider the class (this is the generalized notion for stuff that is too big to be a set, just like the collection of all sets)
$$ \{ \{M\} \ : \ M\in \textbf{Set} \}. $$
Nicola explained me that the statement is at least morally true. The category is "roughly the same" as some category that is small. The main problem is that we allow for too many copies of the same thing. There is no big difference between $\{\lozenge\}$ and $\{ \heartsuit\}$ (as sets). The correct notion of "roughly the same" will be equivalence of categories, which we can find in Chapter $7$ in Awodey. In fact our example is explicitely treated in Example $7.23.$ (p. $146$). 
Marius Furter's avatar
Marius Furter committed

\iam{Marius} Regarding, the above, I'm not sure your counterexample works. If I understand correctly, you are saying that the collection $\Theta := \{ \Psi \}$, where $\Psi := \{M : M \in \mathbf{Set}\}$, is finite, since it contains only the single element $\Psi$ (I'm unclear why you put $\{M\}$ in your example?). On the other hand since, $\Theta$ is a proper class (if it where a set, $\bigcup{\Theta} = \Psi$ would also be by the axiom of union, contradiction by Russell's paradox). In particular, the collection $\Theta$ is not a set and the category $\mathcal{C}$ with $Ob(\mathcal{C}) := \Theta$ is not small. 

Assuming this is the argument, I doubt that $\Theta$ finite. In set theory we define a set to be finite if it is in bijection with an element of the natural numbers (as constructed set-theoretically from ordinals and the axiom of infinity). Since $\Theta$ is a proper class, there aren't any set-theoretic mappings between $\Theta$ and any set: Any such mapping is a subset of the cartesian product of two sets. Hence, if we assume such as map, we could again union our way to a set of all sets. Therefore, it seems we would need an extension of the concept of finiteness if we wanted to apply it to proper classes. Maybe, we could re-construct an analogue of the natural numbers at each level of the class hierarchy and then count elements with respect to these? Under the set-theoretic definition, however, $\Theta$ fails to be finite and is therefore not a counterexample.
Severin Schraven's avatar
Severin Schraven committed

\iam{Severin} I am not sure, whether I understand, what you mean. I want to show that the collection of all finite set is a proper class (and thus $\textbf{Set}_{\text{fin}}$ is not a small category). For this I note that the collection of all singeltons is a proper class. What I am saying is that $\{M\}$ is finite (clearly $M$ is not finite in general and thus I wrote the brackets). I am not sure, why you introduce $\Psi$. Can you clarify?
Marius Furter's avatar
Marius Furter committed

\iam{Marius} Okay, I see now what you were objecting to the claim that $\textbf{Set}_{\text{fin}}$ is a small category. I now agree with you. Thanks for pointing that out! I implicitly assumed we could somehow enumerate finite sets based on cardinality, but this is clearly incorrect upon reflection, as your example shows. Because of this mistaken assumption I thought you were objecting to the claim that all finite categories are small. I apologize for any confusion I created. I believe my example still shows that a category might not be small, even if it only contains a single object.

What you report Nicola as saying makes more sense now. Indeed, we can consider the category whose objects are isomorphism classes of finite sets. Restricting to some choice of representatives, we obtain an equivalent subcategory of $\textbf{Set}_{\text{fin}}$ which contains no isomorphic objects (called the skeleton of $\textbf{Set}_{\text{fin}}$, see e.g. wikipedia). This skeleton will then be isomorphic as a category to $\mathbf{FinOrd}$, the category of finite ordinals, a small category.

Severin Schraven's avatar
Severin Schraven committed
\iam{Severin} Indeed, that is the example I referenced in the book. I agree that a category might not be small, even if it contains only one element (unless that element happens to be a set). Something that I find very surprising!
Muhammed Guelen's avatar
Muhammed Guelen committed

Severin Schraven's avatar
Severin Schraven committed


Nicola Capacci's avatar
Nicola Capacci committed
\section{Week 2}

Andreas Wanner's avatar
Andreas Wanner committed

Andreas Wanner's avatar
Andreas Wanner committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Show that, in $\mathbf{Set}$, epis are surjective functions. Conclude that isos in this category are morphisms that are epic and monic. Give an example of a category where this is not the case.\hfill \break
Severin Schraven's avatar
Severin Schraven committed
\iam{Severin} One example where it does not hold is any given poset (with more than two points that are comparable and distinct) viewed as a skeletal category (all arrows are monic and epic by $4.2$, but the arrow between the two comparable distinct points is not an iso as there is no arrow in the opposite direction to begin with). Another example we saw in Olga's talk, the category of monoids (with the explicit example given by the inclusion map from $(\mathbb{N}, +, 0)$ to $(\mathbb{Z}, +, 0)$). We can tweak this example a bit and get an example in the category of rings (objects are rings and arrows are ring homomorphisms). Namely, we can take the inclusion from $(\mathbb{Z}, +, \cdot)$ to $(\mathbb{Q}, +, \cdot)$. More generally, we can take integral domain $(R, +, \cdot)$ that is not a field and consider the "inclusion" into its quotient field $\operatorname{Quot}(R)$. Another example would be the category of smooth manifolds (objects are smooth manifolds and arrows are smooth maps). Then the arrow $f: \mathbb{R}\rightarrow \mathbb{R}, \ f(x)=x^3$ yields an arrow that is both epic and monic, but not an iso. Feel free to show that those are really examples of arrow that are both epic and mono, but not iso.
Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Show that in a poset, treated as a skeletal category, all arrows are both monic and epic.\hfill \break
Severin Schraven's avatar
Severin Schraven committed
\iam{Severin} In a poset there exists at most one arrow between two given objects. Thus, already saying $g,h$ are arrows between $B$ and $D$ implies that $g=h$ (without even mentioning $f$).

Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} For the following exercises, consider the typical commutative diagram 
Nicola Capacci's avatar
Nicola Capacci committed
\begin{center}\begin{tikzcd}
A \arrow[rr, "f"] \arrow[rrdd, "g\circ f"'] &  & B \arrow[dd, "g"] \\
                                            &  &                   \\
                                            &  & C                
\end{tikzcd}
\end{center}
in any category $\mathbf{C}$. 
Nicola Capacci's avatar
Nicola Capacci committed
\begin{enumerate}
\item Show that if $f$ and $g$ are isos (resp. monos or epis), then so is $g\circ f$;
\item Show that if $g\circ f$ is monic, then so is $f$;
\item Show that if $g\circ f$ is epic, then so is $g$;
\item Give an example of $g\circ f$ being monic (or resp. epic) while $g$ (or resp. $f$) is not.
\end{enumerate}
\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

OlgaB08's avatar
OlgaB08 committed
\iam{Olga}
\begin{enumerate}
\item \underline{$f,g$ are isos $\implies (g \circ f)$ is iso}
\begin{proof}
Assume f, g are isos \\then $\exists f^{-1}, s.t. f^{-1} \circ f= 1_A$ and $f \circ f^{-1}=1_B $\\ and $\exists g^{-1}$, s.t. $g^{-1} \circ g= 1_B$ and $g \circ g^{-1}=1_C $ \\
We want to show that for $(g \circ f): A \to C$,  $\exists (g \circ f)^{-1}$ s.t. $(g \circ f)^{-1} \circ (g \circ f) = 1_A$ and $(g \circ f) \circ (g \circ f)^{-1}= 1_C$\\
So we have:\\
$(g \circ f)^{-1} \circ (g \circ f) = (f^{-1} \circ g^{-1}) \circ (g \circ f) = f^{-1} \circ (g^{-1} \circ g) \circ f = f^{-1} \circ 1_B \circ f = f^{-1} \circ f = 1_A$ \\
$(g \circ f) \circ (g \circ f)^{-1} = (g \circ f) \circ (f^{-1} \circ g^{-1}) = g \circ (f \circ f^{-1}) \circ g^{-1} = g \circ 1_B \circ g^{-1} = g \circ g^{-1} = 1_C$\\
$\implies (g \circ f)$ is iso.\\
Moreover we can show that \underline{if $f, g$ are monos then so is $(g \circ f)$}:
\begin{proof}
Assume $f$ is mono, i.e. for some $h, \tilde{h}:D \to A$ and $k, \tilde{k}: B \to E$:\\
if $f \circ h = f \circ \tilde{h}$ then $h = \tilde{h}$\\
if $k \circ f = \tilde{k} \circ f$ then $k = \tilde{k}$\\
Analog for $g$.\\

Take $h, \tilde{h}:D \to A$ and consider: \\
$(g \circ f) \circ h = (g \circ f) \circ \tilde{h}$\\
since composition is assoc. $g \circ (f \circ h) = g \circ (f \circ \tilde{h})$\\
since g is mono $f \circ h = f \circ \tilde{h}$\\
since f is mono $h = \tilde{h}$\\
$\implies (g \circ f)$ is mono\\

Now take $k,\tilde{k}:C \to F$ and consider: \\
$k \circ (g \circ f) = \tilde{k} \circ(g \circ f)$ \\
since composition is assoc. $(k \circ g) \circ f = (\tilde{k} \circ g) \circ f$\\
since f is epi $k \circ g = \tilde{k} \circ g$\\
since g is epi $k = \tilde{k}$\\
$\implies (g \circ f)$ is epi
\end{proof}
\end{proof}
\item \underline{$g \circ f$ is mono $\implies f$ is mono}
\begin{proof}
We want to show that if $f \circ h = f \circ \tilde{h}$, then $h = \tilde{h}$\\
Consider $f \circ h = f \circ \tilde{h}$ for some $h, \tilde{h}:D \to A$\\
combine with g on left $g \circ f \circ h = g \circ f \circ \tilde{h}$ \\
because of assoc. $(g \circ f) \circ h = (g \circ f) \circ \tilde{h}$ \\
since $g \circ f$ is mono $h = \tilde{h}$ \\
$\implies f$ is mono
\end{proof}
\item \underline{$g \circ f$ is epi $\implies g$ is epi}
\begin{proof}
We want to show that if $k \circ g = \tilde{k} \circ g$, then $k = \tilde{k}$\\
Consider $k \circ g = \tilde{k} \circ g$ for some $k,\tilde{k}:C \to F$\\
combine with f on right $k \circ g \circ f = \tilde{k} \circ g \circ f$ \\
because of assoc. $k \circ (g \circ f) = \tilde{k} \circ (g \circ f)$ \\
since $g \circ f$ is epi $k = \tilde{k}$ \\
$\implies g$ is epi
\end{proof}
\item Example\\
Consider category \underline{Set} and following functions\\
$f: [0, \inf) \to \mathbb{R}$, $f(x)=x$ is injective \\
$g: \mathbb{R} \to [0, \inf)$, $g(x)=|x|$ is not injective (since $g(-1)=g(1)$, but $1\neq{-1}$)\\
and \\
$(g \circ f) : [0, \inf) \to [0, \inf)$, $(g \circ f)(x)=|x|$ is bijective, i.e. injective
\end{enumerate}

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} $\mathbf{Vec}_k$ is the category of vector spaces over the field $k$ and linear maps between them. Describe its initial and terminal object. \hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Muhammed Guelen's avatar
Muhammed Guelen committed
\iam{Muhammed} The initial  and terminal object in $\mathbf{Vec_k}$ is the trivial vector space $W = \{0_W\}$. Indeed, let $V$ be an object in $\mathbf{Vec_k}$ Then, the unique linear map from ${0_W}$ to $V$ is given by $w \mapsto 0_V$. Similarly, the unique homomorphism from $V$ to $\{0_W\}$ is characterized by the mapping $v \mapsto 0_W$. As these are true for any arbitrary $V$ in the category, the claim follows. 

Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed

\subsection{} Show that the following are equivalent. For an arrow $f:A\to B$ in any category,
\begin{enumerate}
\item $f$ is an iso;
\item $f$ is both a mono and a split epi;
\item $f$ is both epic and a spit mono;
\item $f$ is both a split mono and a split epi.
\end{enumerate}\hfill \break
Andreas's avatar
Andreas committed
\iam{Andreas}
\begin{itemize}
\item $(i)\to (iv)$: $f$ is an isomorphism, meaning we have $ff^{-1}=1_B$ and $f^{-1}f=1_A$, so we have
$f(f^{-1}f)=f\circ 1_A$ and $(ff^{-1})f=1_B\circ f$, hence there exist right resp. left inverse, thus $f$ is a split epi and split mono.
\item $(iv)\to (i)$: If $f$ is both split mono and epi, there exist a left and right inverse such that $f^{-1}f = 1_A$ and $ff^{-1}=1_B$, but that is the definition of an isomorphism.
\item $(i)\to (ii)$: By $(i\to iv)$ we know that $f$ is split epi. Consider arrows $i,j$ such that $fi=fj$, then it follows that $(f^{-1}f)i=(f^{-1}f)j$ and thus $i=j$, hence $f$ is a mono.
\item $(i)\to (iii)$: By $(i\to iv)$ we know that $f$ is split mono. Consider arrows $i,j$ such that $if=jf$, then it follows that $i(ff^{-1})=j(ff^{-1})$ and thus $i=j$, hence $f$ is a epic.
\item $(ii)\to (iv)$ So $f$ is a mono, so for every arrow $i$ with $fi=ff^{-1}$ it follows that $i=f^{-1}$. Since $f$ is split epi, there exists such a right inverse $f^{-1}$.
\item $(iii)\to (iv)$ So $f$ is a epic, so for every $j,i$ with $if=f^{-1}f$ it follows that $i=f^{-1}$. Since $f$ is split mono, there exists such a left inverse $f^{-1}$.
\end{itemize}
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Show that in any category, any retract of a projective object is projective. \hfill \break

Muhammed Guelen's avatar
Muhammed Guelen committed
\iam{Muhammed} Let $\mathbf{C}$ be a category, $P$ projective and $A$ retract of $P$. Then, there exist arrows $g: P \to A$ and $h: A \to P$ such that $gh = 1_A$. Let $\tau: E \twoheadrightarrow X$ and $\varphi: A \to X$. We want to find $\psi: A \to E$ which satisfies $\tau \psi = \varphi$. Since $P$ is projective, we can find a $\psi ' :P \to E$ such that $\tau \psi ' = \varphi g$. Finally, set $\psi := \psi ' h: A \to E$, then, 
Muhammed Guelen's avatar
Muhammed Guelen committed
$$
\tau \psi = \tau \psi' h = \varphi gh = \varphi.
$$
This proves the claim.

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Show that all epis in $\mathbf{Pos}$, the category of posets, are surjections on elements, and that the one element poset is projective.\hfill \break

Raphael Mathyer's avatar
Raphael Mathyer committed
\iam{Raphael} Let $f:X\rightarrow Y$ be an epis of posets. Let $Z=\{\{\},\{*\}\}$ equipped with the order $\{\}\leq \{*\}$. Define the morphisms of posets $\alpha:Y\ni y\mapsto \{*\}$ and
$\beta:Y\rightarrow Z$ with $\beta(y)=\{*\}$ if and only if $y\in f(X)$. Then we have $\alpha\circ f=\beta\circ f$, and hence $\alpha=\beta$, i.e. $f(X)=Y$.\\
Let now $X=\{*\}$ be a one element poset. Let $g:E\rightarrow Y$ be an epi of posets and $f:X\rightarrow Y$ be a morphism of posets. Because an epi of posets is surjective
(by the above) we know that there is an $e\in E$ with $g(e)=f(*)$. Define $\overline{f}(*)=e$, then clearly $g(\overline{f}(*))=g(e)=f(*)$, hence $X$ is projective.
  
Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Show that sets, regarded as \emph{discrete} posets, are projective in $\mathbf{Pos}$. Give an example of a poset which is not projective. Show that every projective poset is discrete, that is a set. Conclude that $\mathbf{Set}$ is (isomorphic to) the \emph{full subcategory} of projective objects in $\mathbf{Pos}$. \hfill \break


Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Show that a homomorphisms of graphs $h:G\to H$ is monic just if it is injective on edges and vertices.\hfill \break

Marius Furter's avatar
Marius Furter committed
\iam{Marius} The claim boils down to the fact that we have two special graphs $V :=$ \fbox{$\bullet$} and $E:=$ \fbox{$\bullet \rightarrow \bullet$} that allow us to distinguish vertices and arrows in any graph. More precisely, for any graph $G$ we have isomorphisms $\alpha: \text{Hom}(V,G) \cong V(G)$ and $\beta: \text{Hom}(E,G) \cong E(G)$ in $\mathbf{Set}$, where $V(G)$ denotes the vertex set of $G$, and $E(G)$ its edge set. In fact, assigning each graph its underlying set of vertices (resp. edges) defines functors $V,E: \mathbf{Graph} \rightarrow \mathbf{Set}$. Moreover, for any $h: G \rightarrow G'$ in $\mathbf{Graph}$ the following squares commute, where $h_*(v) = h \circ v$, and $V(h)$, $E(h)$ are the maps induced on the underlying sets by $h$. (Think this through yourself, as it is not enlightening to write it down in symbols).
\begin{figure}[!h]
	\centering
\begin{tikzcd}
{\text{Hom}(V,G)} \arrow[rr, "\alpha_G"] \arrow[dd, "h_{*}"] &  & V(G) \arrow[dd, "V(h)"] \\
&  &                         \\
{\text{Hom}(V,G')} \arrow[rr, "\alpha_{G'}"]                 &  & V(G')                  
\end{tikzcd}
\qquad
\begin{tikzcd}
{\text{Hom}(V,G)} \arrow[rr, "\beta_G"] \arrow[dd, "h_{*}"] &  & E(G) \arrow[dd, "E(h)"] \\
&  &                         \\
{\text{Hom}(V,G')} \arrow[rr, "\beta_{G'}"]                 &  & E(G')                  
\end{tikzcd}
\end{figure}
This shows that the above isomorphisms are natural. In particular the functors $V$ and $E$ are representable, represented by the objects $V$ and $E$, respectively. 

We next observe that in any category $\mathcal{C}$, a morphism $h: A \rightarrow B$ is mono iff for every $C \in \mathcal{C}$ the map $h_* : \text{Hom}(C,A) \rightarrow \text{Hom}(C,B)$ is injective. (Sketch: ($\Rightarrow$) For $f \neq g \in \text{Hom}(C,A)$, $h_*(f) = h \circ f \neq h \circ g = h_*(g)$, since h monic. ($\Leftarrow$) For $f,g: T \rightarrow A$, $h: A \rightarrow B$, if $h \circ f = h_*(f)= h_*(g) = h \circ g$, then $f = g$, by injectivity). In particular, if $h: G \rightarrowtail G'$ is monic in $\mathbf{Graph}$, then the image of $h$ under both $\text{Hom}(V,-)$ and $\text{Hom}(E,-)$ is injective. By the natural isomorphisms $\alpha$ and $\beta$, this implies that $V(h)$ $(=\alpha_{G'} \circ h_* \circ \alpha_G^{-1})$, and similarly $E(h)$, are injective, as was to be shown.  

The above argument generalizes: Whenever we can represent the functor $U$ which maps object to their underlying set by some object in our category, we may conclude that monomorphisms are injective on the underlying sets. In particular, this holds for sets ($\text{Hom}(\{*\}, X) \cong X$), monoids ($\text{Hom}(\mathbb{N}, M) \cong U(M)$), groups ($\text{Hom}(\mathbb{Z}, G) \cong U(G)$), $R$-modules ($\text{Hom}(R,M) \cong U(M)$), posets ($\text{Hom}(\scalebox{0.6}{\begin{tikzcd}
\bullet \arrow[loop, distance=1.25em, in=115, out=65]
\end{tikzcd}},P) \cong U(P)$), and so on. 

Nicola Capacci's avatar
Nicola Capacci committed
\iam{Nicola} This is a great answer, thanks!

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Let $A$ be a set. Define an $A$-monoid to be a monoid $M$ equipped with a function of sets $m:A\to U(M)$ ($U(M)$ is the underlying set of the monoid $M$). A morphism of $A$-monoids 
$$h:(M,m)\to (N,n)$$
 is a monoid homomorphism which commutes the following triangle in $\mathbf{Set}$
\begin{center}
\begin{tikzcd}
U(M) \arrow[rr, "U(h)"] &                                   & U(N) \\
                        & A \arrow[lu, "m"] \arrow[ru, "n"] &     
\end{tikzcd}
\end{center} 
where $U(h)$ is the morphism $h:M\to N$ treated as the function between the underlying sets. Together with the obvious identities this forms a category $A-\mathbf{Mon}$ of $A$-monoids.

Show that the initial object in this category is the free monoid on $A$, $M(A)$. \emph{(Hint: see section 1.7 for the definition of free monoid)}\hfill \break

\subsection{} Show that in a category with binary products, the product is associative. Meaning that there is a canonical isomorphism 
$$(A\times B)\times C\cong A\times (B\times C)$$
for any triple of objects $A,B,C$.\hfill \break

\subsection{} Given a category $\mathbf{C}$ with two distinguished objects $A$ and $B$, define a category $\mathbf{C}_{A,B}$ to have objects $(X,x_1,x_2)$ with 
\begin{center}
\begin{tikzcd}
A &                                        & B \\
  & X \arrow[lu, "x_1"] \arrow[ru, "x_2"'] &  
\end{tikzcd}
\end{center}
and with arrows $f:(X,x_1,x_2)\to (Y,y_1,y_2)$ being arrows $f:X\to Y$ in $\mathbf{C}$ commuting the diagram 
\begin{center}
\begin{tikzcd}
A                                                       &                                           & B \\
                                                        &                                           &   \\
X \arrow[uu, "x_1"] \arrow[rruu, "x_2"'] \arrow[r, "f"] & Y \arrow[luu, "y_1"'] \arrow[ruu, "y_2"'] &  
\end{tikzcd}
\end{center}

Nicola Capacci's avatar
Nicola Capacci committed
Show that $\mathbf{C}_{A,B}$ has a terminal object if and only if $A\times B$ is well defined in $\mathbf{C}$. \hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

\subsection{} In any category $\mathbf{C}$ with binary products, define the \emph{graph} of an arrow $f:A\to B$ to be the morphism $\Gamma(f)$ defined by the following universal property:
\begin{center}
\begin{tikzcd}
A &                                                                                                        & B \\
  & A\times B \arrow[ru, "p_2"] \arrow[lu, "p_1"]                                                          &   \\
  & A \arrow[luu, "\mathrm{id}_A", bend left] \arrow[ruu, "f"', bend right] \arrow[u, "\Gamma(f)", dashed] &  
\end{tikzcd}
\end{center}
\begin{enumerate}
\item Show that this arrow is always monic;
\item For $\mathbf{C}=\mathbf{Set}$, show that this defines a functor $\Gamma:\mathbf{Set}\to \mathbf{Rel}$. \emph{(Hint: for the definition of the category $\mathbf{Rel}$ see Exercise \ref{Rel}. To define the relation $R(f)\in A\times B$ use the image of $\Gamma(f)$)}
\end{enumerate}\hfill \break

\subsection{} \emph{(Harder)} Show that the forgetful functor $U:\mathbf{Mon}\to \mathbf{Set}$ from monoids to sets which forgets about the monoid structure is representable. Show that $U$ preserves small products.
Severin Schraven's avatar
Severin Schraven committed

\iam{Severin} The forgetful functor should be representable by $\operatorname{Hom}(M(*), \cdot)$, where $M(*)$ denotes the free monoid on $\{*\}$. The forgetful functor $U: \textbf{Mon} \rightarrow \textbf{Set}$ is on objects $U(M)= \vert M \vert$ (underlying set of the monoid) and $U(f) = \vert f \vert$ (underlying function on the sets). The functor $\operatorname{Hom}(M(*), \cdot)$ is given by 
\begin{align*}
\operatorname{Hom}(M(*), \cdot) : \ &\textbf{Mon} \rightarrow \textbf{Set} \\
&M \mapsto \operatorname{Hom}(M(*), M) \\
&(f: B \rightarrow B') \mapsto \left( \operatorname{Hom}(M(*), B) \rightarrow \operatorname{Hom}(M(*), B'), g \mapsto f \circ g \right).
\end{align*}
Now we have to identify those two functors. We consider the following two maps on the level of objects.
\begin{align*}
\Psi: \operatorname{Hom}(M(*), M) \rightarrow \vert M \vert, \ \overline{f} \mapsto \vert \overline{f} \vert (i(*))
\end{align*}
where $i: \{*\} \rightarrow M(\{*\})$ as in the UMP of the free monoid (see Awodey p. 17). And 
\begin{align*}
\Phi: \vert M \vert \rightarrow \operatorname{Hom}(M(*), M), m \mapsto \overline{f}_m
\end{align*}
where $\overline{f}_m$ is the unique monoid morphism we get from the UMP of the free monoid with respect to the function $f_m : \{*\} \rightarrow \vert M \vert, \ f_m(*) = m$. We have that $\Psi, \Phi$ are mutually inverse and thus $\vert M \vert$ is isomorphic to $\operatorname{Hom}(M(*), M)$ in the category of sets. Indeed, we have
\begin{align*}
(\Psi \circ \Phi) (m) = \vert \overline{f}_m \vert (i(*)) = f_m(*) = m.
\end{align*}
On the other hand, we have
\begin{align*}
(\Phi \circ \Psi)(\overline{f}) = \overline{f}_{\vert \overline{f} \vert(i(*))} = \overline{f},
\end{align*}
where we used in the last line the UMP for the free monoid ($\vert \overline{f}_{\vert \overline{f}\vert(i(*))} \vert(i(*))= \vert \overline{f} \vert(i(*))$ and thus, by the uniqueness part of the UMP $\overline{f}_{\vert \overline{f} \vert(i(*))} = \overline{f}$).
Feel free to flesh out this hand-wavy sketch.
Nicola Capacci's avatar
Nicola Capacci committed

\section{Discussion: Week 2}
\iam{Muhammed} I am not sure if I understand the charactarization of concrete categories through test objects as described in Rmk. 1.7? Can somebody elucidate this?

\iam{Severin} I understand it this way: In \textbf{Set} we have equality of arrows iff their evaluation coincides, i.e. for $f,g\in \text{Hom}(A,B)$ we have $f=g$ iff $f(x)=g(x)$ for all $x\in A$. Now we rephrase this in terms of terminal objects. In the category of sets, "the" terminal object is "the" one-point set. So for every $x\in A$ we can define a morphism $\overline{x}:\{*\} \rightarrow A, *\mapsto x$ (and all morphisms of the terminal object in \textbf{Set} are of this form). Hence, saying $f(x)=g(x)$ for all $x\in A$ is equivalent to saying that $f\overline{x}=g\overline{x}$ for all morphisms $\overline{x}$ from the terminal object to $A$. 

To me it seems that we want to say, that we can have "generalized objects" (the morphisms from the terminal object) and if for two morphisms their "evaluations coincide", then the morphisms must be the same. This property will also not be shared by all categories (some of them do not have a terminal object to begin with, like for example the category of fields (with objects fields and morphisms unital ring homomorphisms)). Of course it is better explained in $2.3$ in Awodey.

\iam{Nicola} Firstly, let me apologize for moving this discussion, but this way we can keep the topics separate. Now, regarding concrete categories, Remark 1.7 of Awodey makes a very good point. 

In the first week I said {concrete categories} are those whose objects are sets with some \emph{property} and morphisms are property-preserving-functions. With insight, this was a terrible definition (but in my defence it wasn't supposed to be one), and the reason lies in this remark. If I gave you a category as a list of objects, morphisms and wrote out all the compositions, could you tell if it was a concrete category? It seems, looking at it, with abject called $A$ or $B$ and morphisms named $f$ or $g$, that you could be talking about sets as well as fruit, so at first glance the answer should be no. But if not, then what about the notion of concrete category? Is it something quantifiable, or just a property of how we \emph{present} a given category, that is to say, not an intrinsic property at all?

Enter generalized objects, a topic I was hoping to avoid at least until we discussed Yoneda :) In particular, let us examine our favourite category $\mathbf{Set}$. As Severin points out, or alternatively in Section 2.2 of Awodey, a map of sets from the terminal object (i.e. the one-element-set) to any given set behaves by selecting an element
\begin{center}
\begin{tikzcd}
\star \arrow[rr, "a"] &  & A
\end{tikzcd}
\end{center}
As such, it is not hard to see how we obtain a bijective correspondence (i.e. an iso in $\mathbf{Set}$) between 
$$\Hom_\mathbf{Set}(\star,A)\cong A$$
Let us organize the data of this bijection more categorically, specifically this data extends from an equivalence of sets to an equivalence of functors 
\begin{center}
\begin{tikzcd}
\mathbf{Set} \arrow[rr, "{\mathrm{Hom}(\star,-)}", bend left] \arrow[rr, "\mathrm{Id}"', bend right] &  & \mathbf{Set}
\end{tikzcd}
\end{center}
We can work out the details of this equivalence when we come to discuss natural transformations, but, taking this at face value for the moment and allowing me some terminology, this statement is paramount to the knowledge that the identity functor on $\mathbf{Set}$ is \emph{co-represented} by the terminal object. 

\begin{comment}
Let us see another example of this type of behaviour, before returning to concrete categories. Consider the category $\mathbf{Man}_d$ of $d$ dimensional smooth manifolds (without boundaries) and smooth \emph{open} maps between them. As a special sub-category of $\mathbf{Man}_d$ we have $\mathbf{Emb}_d$, with the same objects but whose morphisms are open embeddings. This subcategory is special because the morphisms of $\mathbf{Man}_d$ posses the property of \emph{image-factorization}, meaning that for every smooth open map of manifolds $f:M\to N$ there is a commuting triangle in $\mathbf{Man}_d$
\begin{center}
\begin{tikzcd}
                                                     & \mathrm{im}(f) \arrow[rd, "\iota_f", hook] &   \\
M \arrow[rr, "f"] \arrow[ru, "\tilde{f}", two heads] &                                            & N
\end{tikzcd}
\end{center}
where $\tilde{f}$ is epi and $\iota_f$ is a split mono (which i claim is an open embedding in $\mathbf{Man}_d$). Using this assignment we can construct a replacement functor 

 In particular in this category we have an object $\mathbb{R}^d$ and the set
$$\Hom_{\mathbf{Man}_d}(\mathbb{R}^d,M) $$
\end{comment}

With this in mind, and suspending all disbelief as to how one arrives here, let me give you the definition of concrete category.

\begin{defn}(Concrete Category) A concrete category is a category $\mathcal{C}$ equipped with a faithful functor to $\mathbf{Set}$:
\begin{center}
\begin{tikzcd}
\mathcal{C} \arrow[rr, "U"] &  & \mathbf{Set}
\end{tikzcd}
\end{center}
where a functor $F:\mathcal{C}\to \mathcal{D}$ is called faithful if for all pairs of objects $A,B$ of $\mathcal{C}$ the induced function of sets
\begin{center}
\begin{tikzcd}
\Hom_\mathcal{C}(A,B) \arrow[rr, "F"] &  & \Hom_\mathcal{D}(F(A),F(B))
\end{tikzcd}
\end{center}
is injective.
\end{defn}

\begin{rmk} Often we are interested in the particular case where the functor $U:\mathcal{C}\to \mathbf{Set}$ is (co)representable, meaning that there is an object $A$ of $C$ and a natural isomorphism (equivalence of functors) between
$$\Hom_\mathcal{C}(A,-)\cong U(-)$$
The reason for this fact is that, in most cases, one asks that $U:\mathcal{C}\to \mathbf{Set}$ be not only faithful, but equipped with a left adjoint $F:\mathbf{Set}\to \mathcal{C}$. Then, it is a fact that we have a natural equivalence of functors 
$$\Hom_\mathcal{C}(F(\star),-)\cong U(-)$$

Conversely, if $\mathcal{C}$ has coproducts, or sometimes even under weaker conditions, then for any object $A$ the functor $\Hom_\mathcal{C}(A,-)$ is always right adjoint, making $\mathcal{C}$ and $\Hom_\mathcal{C}(A,-)$ into a concrete category.
\end{rmk}

Now, there is a lot of terminology here (about left and right adjoints) so maybe this is a point worthwhile revisiting later. Although, before signing off I would like to point out how our definition fixed our original problem: \emph{how can being concrete be a property of a category?}

The answer is that it is not. It is a property of a category together with a functor. 


\section{Week 3}
Nicola Capacci's avatar
Nicola Capacci committed

\subsection{} Alongside the \emph{forgetful} functor $U:\mathbf{Mon}\to \mathbf{Set}$, which assigns to a monoid its underlying set there is the \emph{free} monoid functor $M:\mathbf{Set}\to \mathbf{Mon}$, which assigns to a set its free monoid. The details of this construction are in Section 1.7 of Awodey.

Show in detail that the free monoid functor \emph{preserves coproducts}, in the sense that for any two sets $A$ and $B$ there is a canonical isomorphism
$$M(A)+M(B)\cong M(A+B)$$
(\emph{Hint:} The details of this construction are in Example 3.5 of Awodey)\hfill \break

Muhammed Guelen's avatar
Muhammed Guelen committed
\iam{Muhammed} As Awodey keeps everything rather short, the following exposition is supposed to fill in the details of Example 3.5 -- modulo typos: Let $A,B$ sets and $A+B$ their coproduct with injections $i_{A}: A \to A+B$ and $i_B: B \to A+B$. Further, let $\eta_A: A \to |M(A)|$, $\eta_{A+B}: A+B \to |M(A+B)|$ and $\eta_B: B \to |M(B)|$ be the free monoids of $A, A+B, B$, respectively. Let $M(A) + M(B)$ be the coproduct of $M(A)$ and $M(B)$ with respective injections $m_A, m_B$. Consider the following diagram: 
\begin{center}
% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZABgBoBGAXVJADcBDAGwFcYkQBZACgEEBKEAF9S6TLnyEUAJlLFqdJq3YA5ISJAZseAkRlUaDFm0SdeAagBCA4aK0SiAFgrzDSk9ytrb4nSjJSXRWMQHi8NMW1JZBkAgyD2HkswzR8op1iFI3YLIXkYKABzeCJQADMAJwgAWyQyEBwIJHI4rJMqgH1QmxAK6qQAZhoGppa3EA6cmkZ6ACMYRgAFCPsTcqwCgAscMN6axCd6xsQ612CAHTOYHHpOncq9gFYho5lMsYurm+BEi0E7vsQADZngNRudLtd2jlurskAdhognm9glhblNZvMlnZfCA1pttjD7khgYckEjTuxUZMQNM5otljjGDBSgTKIIgA
\begin{tikzcd}
                                         &  & M(A) + M(B)                           &  &                                         \\
M(A) \arrow[rru, "m_A"]                  &  & M(A+B)                      &  & M(B) \arrow[llu, "m_B"']                \\
A \arrow[u, "\eta_A"] \arrow[rr, "i_A"'] &  & A+B \arrow[u, "\eta_{A+B}"] &  & B \arrow[u, "\eta_B"] \arrow[ll, "i_B"]
\end{tikzcd}
\end{center}
Note that we ignore the fact that this diagram and the following ones contain arrows going from $\mathbf{Sets}$ to $\mathbf{Mon}$. If we were precise, we should consider suitable compositions with a forgetful functor $F: \mathbf{Mon} \to \mathbf{Set}$, whereof we abstract for the sake of clarity. Now, let $f = m_A \circ \eta_A$, $g = m_B \circ \eta_B$ and $\bar{f} = \eta_{A+B} \circ i_A, \bar{g} = \eta_{A+B} \circ i_B$. 

\begin{center}
% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZABgBoBGAXVJADcBDAGwFcYkQBZACgEEBKEAF9S6TLnyEUAJlLFqdJq3YA5ISJAZseAkRlUaDFm0SdeAagBCA4aK0SiAFgrzDSk9ytrb4nSjJSXRWMQHi8NMW1JZBkAgyD2HkswzR8op1iFI3YLIXkYKABzeCJQADMAJwgAWyQyEBwIJHI4rJMqgH1QmxAK6qQAZhoGppa3EA6cmkZ6ACMYRgAFCPsTcqwCgAscMN6axCd6xsQ612CAHTOYHHpOncq9gFYho5lMsYurm+BEi0E7vsQADZngNRudLtd2jlurskAdhognm9glhblNZvMlnZfCA1pttjD7khgYckEjTuxUZMQNM5otljjGDBSgT1LD9iDEM1kexSv89vCXmD2BcZvRysBSn9CQCSQjXhSTKLxcACtK2USgZzuYqQAVcoIgA
\begin{tikzcd}
                                                                                  &  & M(A) + M(B)                           &  &                                                                                  \\
M(A) \arrow[rru, "m_A"]                                                           &  & M(A+B)                      &  & M(B) \arrow[llu, "m_B"']                                                         \\
A \arrow[u, "\eta_A"] \arrow[rr, "i_A"'] \arrow[rruu, "f"] \arrow[rru, "\bar{f}"] &  & A+B \arrow[u, "\eta_{A+B}"] &  & B \arrow[u, "\eta_B"] \arrow[ll, "i_B"] \arrow[llu, "\bar{g}"] \arrow[lluu, "g"]
\end{tikzcd}
\end{center}
Now, by the UMP of the coproduct of A and B, there exists a unique arrow $u$ that makes the diagram made up by $A,B, A+B, f, g, i_A, i_B$ commute. Similarly, from the UMP of free monoids on $A$ and $B$, we get unique arrows $f', g'$ such the respective diagrams below commute:

\begin{center}
% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZABgBoBGAXVJADcBDAGwFcYkQBZACgEEBKEAF9S6TLnyEUAJlLFqdJq3bd+AAgDUq7gCEBw0djwEiMqjQYs2iTr3W6hIkBkMSiAFgryLS6zr2PncWMUMikvRSsQHgcDIMlkGTDzCPYeOxinMSN4jySFS3ZtIXkYKABzeCJQADMAJwgAWyQyEBwIJHJkgusGgH1o-RA6xqQAZho2jq6fED6imkZ6ACMYRgAFLNdrWqwygAscDOGmxA9W9sQW70iAHRuYHHp+o-qTgFYJi5l8mbuHp+AaW0gheI0QADZPmNprd7o9ekVBsckGdJogPj9IlhngtlqsNi5giAdvtDkjXkhIeckBjruxsfMQIsVutNkTGDBqmTHMjTlDEJ1MexqiBcSyCXF2CSDqCTqivjD2HclvRasBqiDyWCqWjvnTrMrVcAypqeRSIfzBfqQGVZTTLRN6FhGOxIGA2DQVmAoEgALSjFqMLDu9hQehwPalUVMvGswmSYm7GWK6zMO2XfnfIMh6xQCA4HBRlNDADk6fG1MQWeDkTDEaLQusZTLgkogiAA
\begin{tikzcd}
                                                                                   &  & M(A) + M(B)                                                      &  &                                                                                  \\
M(A) \arrow[rru, "m_A"] \arrow[rr, "f'", dotted]                                   &  & M(A+B)                                                           &  & M(B) \arrow[llu, "m_B"'] \arrow[ll, "g'", dashed]                                \\
A \arrow[u, "\eta_A"] \arrow[rr, "i_A"'] \arrow[rruu, "f"'] \arrow[rru, "\bar{f}"] &  & A+B \arrow[u, "\eta_{A+B}"] \arrow[uu, "u"', dashed, bend right] &  & B \arrow[u, "\eta_B"] \arrow[ll, "i_B"] \arrow[llu, "\bar{g}"] \arrow[lluu, "g"]
\end{tikzcd}
\end{center}
Now, by the UMP of the free monoid on $A+B$, there is a unique arrow $v$ that makes the diagram made up of $A+B, M(A+B), M(A)+M(B), \eta_{A+B}, u$ commute. Also, by the UMP of the coproduct of $M(A)$ and $M(B)$, there is a unique arrow $\overline{v}$ that makes the diagram made up of $M(A), M(B), M(A)+M(B), M(A+B), f', g', \overline{m}, m_A, m_B$ commute, as shown below:

\begin{center}
% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZABgBoBGAXVJADcBDAGwFcYkQBZACgEEBKEAF9S6TLnyEUAJlLFqdJq3bd+AAgDUq7gCEBw0djwEiMqjQYs2iTr3W6hIkBkMSiAFgryLS6zr2PncWMUMikvRSsQHgcDIMlkGTDzCPYeOxinMSN4jySFS3ZtIXkYKABzeCJQADMAJwgAWyQyEBwIJHJkgusGgH1o-RA6xqQAZho2jq6fED6imkZ6ACMYRgAFLNdrWqwygAscDOGmxA9W9sQW70iAHRuYHHp+o-qTgFYJi5l8mbuHp+AaW0gheI0QADZPmNprd7o9ekVBsckGdJogPj9IlhngtlqsNi5giAdvtDkjXkhIeckBjruxsfMQIsVutNkTGDBqmTHMjTlDEJ1MexqiBcSyCXF2CSDqCTqivjD2HclvRasBqiDyWCqWjvnTrMrVcAypqeRSIfzBfqQGVZTTLRN6FhGOxIGA2DQVmAoEgALSjFqMLDu9hQehwPalUVMvGswmSYm7GWK6zMO2XfnfIMh6xQCA4HBRlNDADk6fG1MQWeDkTDEaLQusZTLWpOgt1CxrofzhZ9xcNatoppq5u+aMF2drPYbkfoPsQYGYjEYjudroIHpAXvnLQjWC5fr1KWstGKgiAA
\begin{tikzcd}
                                                                                   &  & M(A) + M(B) \arrow[d, "\bar{v}", dotted]                         &  &                                                                                  \\
M(A) \arrow[rru, "m_A"] \arrow[rr, "f'", dotted]                                   &  & M(A+B) \arrow[u, "v", dotted, shift left=2]                      &  & M(B) \arrow[llu, "m_B"'] \arrow[ll, "g'", dashed]                                \\
A \arrow[u, "\eta_A"] \arrow[rr, "i_A"'] \arrow[rruu, "f"'] \arrow[rru, "\bar{f}"] &  & A+B \arrow[u, "\eta_{A+B}"] \arrow[uu, "u"', dashed, bend right] &  & B \arrow[u, "\eta_B"] \arrow[ll, "i_B"] \arrow[llu, "\bar{g}"] \arrow[lluu, "g"]
\end{tikzcd}
\end{center}
It remains to show that $v, \bar{v}$ are inverses. Now, $v\bar{f} = v(\eta_{A+B}i_A) = (v\eta_{A+B})i_A = ui_A = f$ and $\bar{v}f = \bar{v}(m_A\eta_{A}) = (\bar{v}m_A)\eta_{A} = f'i_A = \bar{f}$. Combining these, we get $v\bar{v}f =f$ and $\bar{v}v\bar{f} = \bar{f}$. Following this type of arguments all the way and by using the uniqueness of the UMP-induced arrows, finally yields $v\bar{v} = id = \bar{v}v$. 



Nicola Capacci's avatar
Nicola Capacci committed
\iam{Nicola} Thank you for your detailed answer Marius. I think the core of the answer is correct, but I have a very strong point against your initial diagram. It is always unwise to draw ``diagrams'' that lie in different categories, and I know Awodey does this sometimes and it is infuriating.

 A more precise argument could be made starting with the following diagram in $\mathbf{Set}$
Nicola Capacci's avatar
Nicola Capacci committed
\begin{center}
\begin{tikzcd}
                                         &  & U(M(A) + M(B))              &  &                                         \\
U(M(A)) \arrow[rru, "U(m_A)"]            &  & U(M(A+B))                   &  & U(M(B)) \arrow[llu, "U(m_B)"']          \\
A \arrow[u, "\eta_A"] \arrow[rr, "i_A"'] &  & A+B \arrow[u, "\eta_{A+B}"] &  & B \arrow[u, "\eta_B"] \arrow[ll, "i_B"]
\end{tikzcd}
\end{center}
where I'm using the notation $U:\mathbf{Mon}\to \mathbf{Set}$ instead of  ``$|\,\cdot\,|$''. 
Muhammed Guelen's avatar
Muhammed Guelen committed

Nicola Capacci's avatar
Nicola Capacci committed
Since $M$ is a functor we obtain two morphisms in $\mathbf{Mon}$ by mapping the coproduct injections of $A+B$:
\begin{center}
\begin{tikzcd}
M(A) \arrow[rr, "M(i_A)"] &  & M(A+B) &  & M(B) \arrow[ll, "M(i_B)"']
\end{tikzcd}
\end{center}
The images after $U$ of these morphisms are the two dotted functions you marked above as $f'$ and $g'$. Going forward, by the universal property of coproducts in $\mathbf{Mon}$ one obtains a unique morphism, which you call $\bar{v}$
\begin{center}
\begin{tikzcd}
                                             &  & M(A)+M(B) \arrow[d, "\exists!\bar{v}", dashed] &  &                                                \\
M(A) \arrow[rr, "M(i_A)"] \arrow[rru, "m_A"] &  & M(A+B)                                         &  & M(B) \arrow[ll, "M(i_B)"'] \arrow[llu, "m_B"']
\end{tikzcd}
\end{center}
To obtain ${v}$, you observed that, by the universal property of the coproduct in $\mathbf{Set}$ one obtains a unique function $u$
\begin{center}
\begin{tikzcd}
                                         &  & U(M(A) + M(B))                      &  &                                         \\
U(M(A)) \arrow[rru, "U(m_A)"]            &  &                                     &  & U(M(B)) \arrow[llu, "U(m_B)"']          \\
A \arrow[u, "\eta_A"] \arrow[rr, "i_A"'] &  & A+B \arrow[uu, "\exists!u", dashed] &  & B \arrow[u, "\eta_B"] \arrow[ll, "i_B"]
\end{tikzcd}
\end{center}
which can be used recalling the universal property of free monoids. Given the function $u:A+B\to U(M(A)+M(B))$ one obtains a unique map of monoids $\bar{u}:M(A+B)\to M(A)+M(B)$ satisfying the universal property. This is the morphism whose image after $U$ you call $v$. Finishing the proof now only amounts to checking that $\bar{u}$ and $\bar{v}$ are inverses \emph{in monoids}, which is straight forward.
Muhammed Guelen's avatar
Muhammed Guelen committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Verify that the construction given in Example 3.9 for the coproduct of monoids, as a quotient of a free monoid, satisfies the required universal property in $\mathbf{Mon}$.\hfill \break

\subsection{} Let $P:\mathbf{Set}\to \mathbf{Pos}$ be the functor which assigns to each set its power set, viewed as a poset with subset inclusions. Prove that this functor turns coproducts into products, in the sense that
$$P(A)\times P(B)\cong P(A+B)$$
for any pair of sets $A$ and $B$. \hfill \break

Marius Furter's avatar
Marius Furter committed
\iam{Marius}
Recall that the coproduct in $\mathbf{Set}$ is the disjoint union, and the product $\mathcal{Q} \times \mathcal{R}$ in $\mathbf{Pos}$ is obtained from the cartesian product of sets $Q \times R$ by setting $(q,r) \leq (q',r') \Leftrightarrow q \leq q' \text{ and } r \leq r'$. Using this we see that for sets $A,B$, $P(A + B) = \mathfrak{P}(A \sqcup B)$, where $\mathfrak{P}(\cdot)$ denotes the powerset. Furthermore, $P(A) \times P(B) = \mathfrak{P}(A) \times \mathfrak{P}(B)$, where $(X,Y) \leq (X',Y') \Leftrightarrow X \subset X' \text{ and } Y \subseteq Y'$, for subsets $X,X' \subseteq A$ and $Y,Y' \subset B$. Finally note that for every $Z \in \mathfrak{P}(A \sqcup B)$ we have $Z = Z_A \sqcup Z_B$, with $Z_A \subseteq A$ and $Z_B \subseteq B$.

For any sets $A,B$, define the map $\Psi: \mathfrak{P}(A \sqcup B) \rightarrow \mathfrak{P}(A) \times \mathfrak{P}(B)$ by sending $Z = Z_A \sqcup Z_B \mapsto (Z_A,Z_B)$. This has an obvious inverse $\Phi: \mathfrak{P}(A) \times \mathfrak{P}(B) \rightarrow \mathfrak{P}(A \sqcup B)$ sending $(X,Y) \mapsto X \sqcup Y \in \mathfrak{P}(A \sqcup B)$. It remains to show that both maps are monotone, i.e. morphisms in $\mathbf{Pos}$. For this let $Z_A \sqcup Z_B = Z \subseteq W = W_A \sqcup W_B$ in $\mathfrak{P}(A \sqcup B)$. The disjointness of $A$ and $B$ in the disjoint union implies $Z_A \subseteq W_A$ and $Z_B \subseteq W_B$. Hence $\Psi(Z) = \Psi(Z_A \sqcup Z_B) \leq \Psi(W_A \sqcup W_B) = \Psi(W)$. Conversely, if $(X,Y) \leq (X',Y')$ in $\mathfrak{P}(A) \times \mathfrak{P}(B)$, then $X \subseteq X'$ and $Y \subseteq Y'$ for $X,X' \subseteq A$ and $Y,Y' \subseteq B$. Therefore $\Phi((X,Y)) = X \sqcup Y \subseteq X' \sqcup Y' = \Phi((X',Y'))$, thus $P(A)\times P(B)\cong P(A+B)$ as desired.

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Show that $\mathbf{Mon}$ has all equalizers and finite products.\hfill \break

Andreas's avatar
Andreas committed
\iam{Andreas} Let $M_1,M_2,X$ be monoids with monoid homomorphisms $f,g$ such that 
\begin{center}
\begin{tikzcd}
M_1 \arrow[rr, "f", shift left] \arrow[rr, "g"', shift right] &  & M_2
\end{tikzcd}
\end{center}
then an equalizer $e:X\to M_1$ is given if $f\circ e = g \circ e$. This must be a function from the subset $X\subseteq M_1$ defined as
$X=\{x\in M_1|f(x)=g(x)\}$ into $M_1$. It is clear that $e$ must be another monoid homomorphism, since it is just an inclusion map. Consider now another monoid $Z$ with homomorphism $h:Z\to M_1$. If $fh(z) = gh(z)$ then it follows that $h(z)\in X$, but this means there exist a unique $q(z):Z\to M_1$ such that
$q(z) = eh(z)$ and hence
\begin{center}
\begin{tikzcd}
Z \arrow[rr, "h"] \arrow[rrdd, "q"'] &  & X \arrow[dd, "e"] \\
                                            &  &                   \\
                                            &  & M_1                
\end{tikzcd}
\end{center}
Since $h,e$ are homomorphisms, it follows that $q$ is also a homomorphism.$\implies \textbf{Mon}$ has all equalizers.\\
Now consider a finite product $M_1\times\cdots \times M_n$ with projections $\pi_i:M_1\times\cdots \times M_n\to M_i$. For any monoid $Z$ with homomorphism $z_i:Z\to M_i$ we get a homomorphism $z_{MN}:Z\to M_1\times\cdots \times M_n$ such that $z_i(t) = \pi_i(  z_{MN})$ by $z_{MN}(t)=(z_1(t),\dots,z_n(t))$, so $\textbf{Mon}$ has all finite products. 

Nicola Capacci's avatar
Nicola Capacci committed
\iam{Nicola} Although it is obvious when one thinks about it a minute, I invite someone (other then Andreas) to show why $X$, which appears in the construction of equalizers, is well defined as a monoid. What is the operation? Is this set closed under it?

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Show that $\mathbf{Mon}$ has all coequalizers as follows. Given any pair of monoid homomorphisms $f,g:M\rightrightarrows N$ we define two equivalence relations on $N$
\begin{enumerate}
\item The first declares $n\sim' n'$ if and only if for all monoids $X$ and homomorphisms $h:N\to X$ on has the implication 
$$hf=hg \implies h(n)=h(n')$$
\item The second is the intersection of all equivalence relations $\sim$ on $N$ satisfying $f(m)\sim g(m)$ for all $m\in M$ as well as
$$n\sim n' \quad \text{and}\quad l\sim l' \implies n\cdot l\sim n'\cdot l'$$
\end{enumerate}
Show that these two equivalence relations agree on $N$. Hence show that the quotient set $U(N)/\sim$ is a monoid under $[x]\cdot [y]=[x\cdot y]$ and that the projection map $N\to N/\sim$ is the coequalizer of $f$ and $g$.\hfill \break

\subsection{} Show that, in a category with coproducts, the coproduct of two projective objects is projective.\hfill \break

Arno's avatar
Arno committed
\iam{Arno} Suppose we have $f: P_1+P_2 \to X$ and an epi $e: E \to X$ we want to construct $\bar{f}: P_1+P_2 \to E$ such that $f=e\circ \bar{f}$.
Since $P_1$ and $P_2$ are projective, we have $\tilde{f_i}: P_i \to E$ such that $f \circ i_i=\tilde{f_i} \circ e$. Thus we get from the coproduct property a morphism $[\tilde{f_1},\tilde{f_2}]: P_1+P_2 \to E$ and since it (precomposed with $e$) agrees with on the level of summands with $f$, it is in fact equal to $f$ because of the uniqueness property. (Drawing a picture really helps you to understand all of what i'm saying!)

Nicola Capacci's avatar
Nicola Capacci committed
\iam{Nicola} You can use this website (https://tikzcd.yichuanshen.de) to draw simple pictures and include them into the text using the tikz-cd environment.  

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Use duality to formulate, on your own, the notion of \emph{injective object} by dualizing that of a projective object. Test your definition on posets; show that a map of posets is monic iff it is injective on elements, and give an example of a poset which is injective and one which is not.\hfill \break

\subsection{} $\mathbf{Pos}_0$ is the category of \emph{rooted posets}, which are posets with a least element $0$ and monotone maps preserving $0$. There is a self evident functor 
$$U:\mathbf{Pos}_0\longrightarrow \mathbf{Pos}$$
which embeds $\mathbf{Pos}_0$ as a sub-category of $\mathbf{Pos}$. Denote by $+$ the coproduct in $\mathbf{Pos}$ and $+_0$ the coproduct in $\mathbf{Pos}_0$; show that the following is a coequalizer diagram in $\mathbf{Pos}$
\begin{center}
\begin{tikzcd}
\star \arrow[rr, "0_P", shift left] \arrow[rr, "0_Q"', shift right] &  & U(P)+U(Q) \arrow[rr] &  & U(P+_0 Q)
\end{tikzcd}
\end{center}
where $0_P$ and $0_Q$ is the map from the terminal poset which selects the least elements of $P$ and $Q$, a pair of rooted posets. (You many assume $\mathbf{Pos}$ has all coequalizers.)\hfill \break

\subsection{}  Denote by $U:\mathbf{Top}\to \mathbf{Set}$ the forgetful functor sending a topological space to its underlying set. Let $f,g: X\rightrightarrows Y$ be a pair of parallel continuous maps, make the quotient space $q:Y\to Q$ by 
\begin{enumerate}
\item Taking the coequalizer in $\mathbf{Set}$ to obtain the function $U(q)$ 
\begin{center}
\begin{tikzcd}
U(X) \arrow[rr, "U(f)", shift left] \arrow[rr, "U(g)"', shift right] &  & U(Y) \arrow[rr, "U(q)"] &  & U(Q)
\end{tikzcd}
\end{center}
\item Equip the set $U(Q)$ with the quotient topology, which declares $U\subseteq Q$ open if $q^{-1}(U)\subseteq Y$ is.
\end{enumerate}
Prove that this satisfies the universal property of coequalizers in $\mathbf{Top}$, and conclude that $\mathbf{Top}$ has all coequalizers.

(\emph{Nota bene}: Do not be confused by the notation, the coequalizer constructed in $\mathbf{Set}$ produces a set and a function, we call this $U(Q)$ because we endow this set with a topology in the second step, motivating our notation)
Nicola Capacci's avatar
Nicola Capacci committed


\section{Week 4}

\subsection{} Show that a pull-back of arrows

\begin{center}
\begin{tikzcd}
A\times_X B \arrow[rr, "p_1"] \arrow[dd, "p_2"] \arrow[rd, "\lrcorner" description, phantom, near start] &      & B \arrow[dd, "g"] \\
                                                                                    & {\,} &                   \\
A \arrow[rr, "f"]                                                                   &      & X                
\end{tikzcd}
\end{center}

in a category $\mathcal{C}$ is the same thing as the product $f\times g$ in the slice category $\mathcal{C}\downarrow X$. (\emph{Hint:} The definition of slice category is in Section 1.6 of Awodey)\hfill \break

\subsection{}Show that in any category, given the pull-back square
\begin{center}
\begin{tikzcd}
M' \arrow[rr] \arrow[dd, "m'"] \arrow[rd, "\lrcorner" description, phantom, near start] &      & M \arrow[dd, "m"] \\
                                                                   & {\,} &                   \\
A' \arrow[rr, "f"]                                                 &      & A                
\end{tikzcd}
\end{center}
if $m$ is monic then so is $m'$. Otherwise, you can prove the opposite statement about epis and push-outs.\hfill \break

OlgaB08's avatar
OlgaB08 committed
\iam{Olga}
\begin{proof}

Let us choose some morphisms $g, h: N \rightarrow M'$, such that $m' \circ g = m' \circ h$. Our goal will be to show that $g = h$ (which is the definition of a monomorphism). \\
We construct the following diagram: 

\[
\begin{tikzcd}
N \arrow[drr, bend left, " l \circ g"]  \arrow[dr, shift right =1.2ex, "h"'] \arrow[dr,"g "]   \arrow[ddr, bend right, "m' \circ h"'] & {} & \\
{} & M' \arrow[r, "l"] \arrow[d, "m'"'] & M \arrow[d, "m"] \\
{} & A' \arrow[r, "f"']& A \arrow[ul,phantom, "\lrcorner", very near end].
\end{tikzcd}
\]

Using the associativity of the composition and commutativity of the pull-back square we obtain the compositions: 
\[
m \circ (l \circ g) = (m \circ l) \circ g = (f \circ m') \circ g = f \circ (m' \circ g) = f \circ (m' \circ h),
\]
which make the outer diagram commute. \\
Further,\\
\[m \circ (l \circ g) = f \circ (m' \circ h) = (f \circ m') \circ h = (m \circ l) \circ h = m \circ (l \circ h)
\]\\
But $m$ is monic, so $l \circ g = l \circ h$ \\
Thus we obtain s commutative diagram: \\
\[
\begin{tikzcd}
N \arrow[drr, bend left, " l \circ g"]  \arrow[dr,"g "]   \arrow[ddr, bend right, "m' \circ g"'] & {} & \\
{} & M' \arrow[r, "l"] \arrow[d, "m'"'] & M \arrow[d, "m"] \\
{} & A' \arrow[r, "f"']& A \arrow[ul,phantom, "\lrcorner", very near end].
\end{tikzcd}
\]
This means that $N$ can be factorized through $M'$ via $g$.\\
Similarly, if we use the fact that $m' \circ g = m' \circ h$ and replace $m' \circ g$ with  $m' \circ h$ we can factorize $N$ through $M'$ via $h$.\\
Thus, both $h$ and $g$ make the outer diagram commutative.\\
Using the Universal property of pullback, we notice that the factorization through $M'$
 has to be unique. Thus, $g=h$
\end{proof}


Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Prove the ``two pull-backs'' lemma:
\begin{lem} Suppose the following is a commutative diagram in $\mathcal{C}$, assume further that the right square is a pull-back diagram.
\begin{center}
\begin{tikzcd}
Q \arrow[rr, "q_1"] \arrow[dd, "q_2"] &  & A\times_X B \arrow[rr, "p_1"] \arrow[dd, "p_2"] \arrow[rd, "\lrcorner", phantom, near start] &      & B \arrow[dd, "g"] \\
                                      &  &                                                                                              & {\,} &                   \\
C \arrow[rr, "h"]                     &  & A \arrow[rr, "f"]                                                                            &      & X                
\end{tikzcd}
\end{center}
Then the outer rectangle is a pull-back diagram if and only if the left square is.
\end{lem}

\begin{proof}
Andreas's avatar
Andreas committed
\iam{Andreas}
Andreas's avatar
Andreas committed
So in order for the outer rectangle to be a pull-back diagram, we need that $f\circ h \circ q_2=g\circ p_1\circ q_1$ and that the universal property holds. Clearly the first one holds, since it is a commutative diagram.\\
Andreas's avatar
Andreas committed
$\Leftarrow$ Assume now that the left square is a pull-back diagram.
\begin{center}
\begin{tikzcd}
Z\arrow[drr, bend left, "x"]\arrow[ddr, bend right, "z_1"]\arrow[dr, dotted, "u" description] & & &\\
& Q \arrow[r, "q_1"]\arrow[d, "q_2"]& A\times_X B\arrow[d, "p_2"] \arrow[r, "p_1"] & B \arrow[d, "g"]\\
& C\arrow[r, "h"]& A \arrow[r, "f"] & X              
\end{tikzcd}
\end{center}
Because the right square is a pull-back diagram, we can see $x=\langle x_1,x_2\rangle$ as the unique map such that there exist $x_1:Z\to B$ and $x_2:Z\to A$. Hence the outer square is also a pull-back diagram:
\begin{center}
\begin{tikzcd}
Z\arrow[drr, dotted, bend left, "x={\langle x_1,x_2 \rangle}"]\arrow[ddr, bend right, "z_1"]\arrow[drrr, bend left, "x_2"]\arrow[ddrr, bend right, "x_1"]\arrow[dr, dotted, "u" description] & & &\\
& Q \arrow[r, "q_1"]\arrow[d, "q_2"]& A\times_X B\arrow[d, "p_2"] \arrow[r, "p_1"] & B \arrow[d, "g"]\\
& C\arrow[r, "h"]& A \arrow[r, "f"] & X              
\end{tikzcd}
\end{center}
$\implies$ Assume the outer square is a pull-back  diagram. Then again because the right square is a pull-back too, there exist a unique $x:Z\to A\times_X B$ such that $x_1 = p_1x$ and $z_2=p_1x$. But this means that $u$ is also the unique map for the left square pull-back diagram.
\begin{center}
\begin{tikzcd}
Z\arrow[drrr, bend left, "z_2"]\arrow[ddr, bend right, "z_1"]\arrow[dr, dotted, "u" description] & & &\\
& Q \arrow[r, "q_1"]\arrow[d, "q_2"]& A\times_X B\arrow[d, "p_2"] \arrow[r, "p_1"] & B \arrow[d, "g"]\\
& C\arrow[r, "h"]& A \arrow[r, "f"] & X              
\end{tikzcd}
\begin{tikzcd}
Z\arrow[drr, dotted, bend left, "x"]\arrow[ddr, bend right, "z_1"]\arrow[drrr, bend left, "z_2"]\arrow[ddrr, bend right, "x_1"]\arrow[dr, dotted, "u" description] & & &\\
& Q \arrow[r, "q_1"]\arrow[d, "q_2"]& A\times_X B\arrow[d, "p_2"] \arrow[r, "p_1"] & B \arrow[d, "g"]\\
& C\arrow[r, "h"]& A \arrow[r, "f"] & X              
\end{tikzcd}
\end{center}
Nicola Capacci's avatar
Nicola Capacci committed
\end{proof}

\subsection{} Let $\mathcal{C}$ be a category with pull-backs, show that an arrow $m:M\to X$ is monic if and only if  the diagram below is a pull-back
\begin{center}
\begin{tikzcd}
M \arrow[rr, "\mathrm{Id}_M"] \arrow[dd, "\mathrm{Id}_M"'] \arrow[rd, "\lrcorner" description, phantom, near start] &      & M \arrow[dd, "m"] \\
                                                                                               & {\,} &                   \\
M \arrow[rr, "m"]                                                                              &      & X                
\end{tikzcd}
\end{center}


\subsection{} Dualize explicitly the notion of push-out as the dual of pull-backs. Also, indicate how one constructs push-outs using coproducts and co-equalizers. \hfill \break



Nicola Capacci's avatar
Nicola Capacci committed
\subsection*{Pull-back Functor} In the remainder of this week's exercises we can look more deeply at the concept of slice category and pull-back functor. In Awodey the definition of slice category is in Section 1.6, while some details of the pull-back functor are in Section 5.3.
Nicola Capacci's avatar
Nicola Capacci committed
\begin{defn}(Slice Category) Let $\mathcal{C}$ be a category and $A$ a distinguished object. Define the slice category $\mathcal{C}\downarrow A$ as the category whose objects are morphisms with codomain $A$, such as $f$ or $g$ below, and morphisms are commutative diagrams such as 
\begin{center}
\begin{tikzcd}
X \arrow[rr, "g"] \arrow[rd, "\alpha"] &                   & A \\
                                       & Y \arrow[ru, "f"] &  
\end{tikzcd}
\end{center} 
which we typically just label by $\alpha:f\to g$.
\end{defn}
Nicola Capacci's avatar
Nicola Capacci committed
\begin{ex} Let $\mathbf{Emb}_d$ be the category of smooth $d$ dimensional manifolds and open embeddings between them. Choose a manifold $M$, then $\mathbf{Emb}_d\downarrow M$ is the poset of open subspaces of $M$, sometimes called $\mathrm{Open}(M)$.
\end{ex}
Nicola Capacci's avatar
Nicola Capacci committed
Now consider a diagram of this type:
\begin{center}
\begin{tikzcd}
B \arrow[rr, "h"] &  & A                 \\
                  &  &                   \\
                  &  & Y \arrow[uu, "f"]
\end{tikzcd}
\end{center}
Both $f$ and $h$ can be viewed as objects of $\mathcal{C}\downarrow A$, but our immediate objective is to fix $B$ and ``transfer'' $f$ to an object of the slice category $\mathcal{C}\downarrow B$. This can be done if $\mathcal{C}$ has pull-backs using the following diagram 
\begin{center}
\begin{tikzcd}
B \arrow[rr, "h"]                                                             &    & A                 \\
                                                                              & \; &                   \\
B\times_A Y \arrow[rr] \arrow[uu, "h^*f"] \arrow[ru, "\urcorner" description, phantom, near start] &    & Y \arrow[uu, "f"]
\end{tikzcd}
\end{center}
where $h^*f$ is called the pull-back of $f$ by $h$.
Nicola Capacci's avatar
Nicola Capacci committed
\begin{ex} Returning to our previous example, $\mathbf{Emb}_d$ has all pull-backs, so given a continuous map $h:M\to N$ one obtains a monotone map (of posets) 
\begin{align*}
h^*:\mathrm{Open}(N)&\to \mathrm{Open}(M)\\
U&\longmapsto h^{-1}(U)
\end{align*}
which acts by ``pulling back'' open subspaces from $N$ to $M$.
\end{ex}
Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Let $\mathcal{C}$ be a category with pull-backs and $h:B\to A$ a morphism. Prove that this defines a functor $$h^*: (\mathcal{C}\downarrow A)\to (\mathcal{C}\downarrow B)$$ using the description above. (\emph{Hint:} use the two pull-back lemma.)\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Let $\mathcal{C}$ be a small category with pull-backs and $\mathbf{Cat}$ be the (1-)category of small categories. Show, giving details, that there exists a functor 
\begin{align*}
\mathcal{C}&\to \mathbf{Cat}\\
A&\mapsto \mathcal{C}\downarrow A\\
(h:B\to A)&\mapsto (h^*: (\mathcal{C}\downarrow A)\to (\mathcal{C}\downarrow B))
\end{align*}
Nicola Capacci's avatar
Nicola Capacci committed
Speculate on the importance of this functor.\hfill \break

\section{Week 5}

\subsection{} Show that, for any three objects $A,B,C$ in a cartesian closed category, there are isomorphisms:
\begin{enumerate}
Arno's avatar
Arno committed
\item $(A\times B)^C\cong A^C\times B^C$\\
\iam{Arno} We want to show, that $A^C\times B^C$ satisfies the exponential condition, which implies the isomorphism. \\
First we want to define an evaluation map $ev: A^C\times B^C \times C \to A\times B$. To do so, we have to have to give a map into $A$ and $B$ respectively. \\
We allready have evaluation maps $ev_{A}: A^C\times C \to A$ and $ev_{B}: B^C\times C \to B$. We take $ev = <ev_{A} \circ \pi _{A^C\times C},ev_{B}\circ \pi _{B^C \times C}>$.\\
Because $X \times Y \times Z \cong (X \times Y) \times Z \cong X \times (Y \times Z)$ we have the maps $\pi _{A^C \times C}$ and $\pi _{B^C \times C}$, so the defined map makes sense.\\
Now $\forall g: X \times C \to A \times B$ $g$ splits into $g_{A}: X\times C \to A$ and$ g_{B}:X\times C \to B$ from which we get from the exponential property unique maps $\tilde{g_{A}}:X\to A^C$ and $\tilde{g_{B}}:X\to B^C$ such that $g_{i}=ev_{i}\circ \tilde{g_{i}}\times id_{C}$\\
Thus we see that there is a unique morphism $\tilde{g}=\tilde{g_{A}}\times \tilde{g_{B}}$ such that $g=ev \circ (\tilde{g}\times id_{C})$\\
Andreas's avatar
Andreas committed
\item $(A^B)^C\cong A^{(B\times C)}$\\
\iam{Andreas} Since it's CCC there must exist and objects $(A^B)^C,A^{B\times C}$ and $\operatorname{ev}_{A^B}:(A^B)^C\times C \to A^B$ and $\tilde{q}:A\to A^{B\times C}$and $\operatorname{ev}_{A,2}:A^{(B\times C)}\times (B\times C) \to A$, and $\tilde{g}_{A^B}:X\to (A^B)^C$ and $\tilde{g}_{A,2}:X\to A^B$\\
So $g:(A^B)^C\to A^{(B\times C)}$ with
$g(\cdot):=\tilde{q}\circ\operatorname{ev}_B(\operatorname{ev}_{A^B}(\cdot,1_C),1_B)$ and $g^{-1}:A^{(B\times C)}\to (A^B)^C$ with
$g^{-1}(\cdot):=\tilde{g}_{A^B}\circ\operatorname{ev}_{A,2}(\cdot,1_{B\times C})$\\
Nicola Capacci's avatar
Nicola Capacci committed
\end{enumerate}

\subsection{} Is the category of monoids cartesian closed?\hfill \break
OlgaB08's avatar
OlgaB08 committed
\iam{Olga}
\begin{proof}

First, recall that the initial \textbf{0} and terminal object \textbf{1} in \textbf{Mon} coincide $(\textbf{0} \cong \textbf{1})$. In particular, this is the trivial monoid $\{ \ast \}$. \\
Consider the following isomorphism from Chapter 6.1:
\begin{equation}
Hom_{\mathcal{C}}(A \times B,C) \cong Hom_{\mathcal{C}}(A, C^{B}).
\end{equation}

Nicola Capacci's avatar
Nicola Capacci committed
Assume that \textbf{Mon} is cartesian closed. Let $M$ and $N$ be two arbitrary objects of \textbf{Mon}. We use the observation from the equation above together with the isomorphism $(\textbf{0} \cong \textbf{1})$:
OlgaB08's avatar
OlgaB08 committed

\begin{equation}
Hom_{\textbf{Mon}}(M,N) \cong Hom_{\textbf{Mon}}(\textbf{1}, N^{M}) \cong Hom_{\textbf{Mon}}(\textbf{0}, N^{M}) \cong \textbf{1}.
\end{equation}

The last isomorphism follows from the definition of initial object. The second equation above implies that $\textbf{Mon}$ is trivial, which is not true. Thus, $\textbf{Mon}$ is not cartesian closed.
\end{proof}

Nicola Capacci's avatar
Nicola Capacci committed
\iam{Nicola} Great answer! I only have a small point about notation. $\mathbf{Mon}$ is a locally small category, meaning that the Hom-spaces are sets. Hence, one obtains that 
\begin{align*}
\Hom(\mathbf{0},N^M)\cong \{\star\}
\end{align*}
in $\mathbf{Set}$. You write this expressing the terminal set as $\mathbf{1}$, which you already used for the terminal monoid.


Nicola Capacci's avatar
Nicola Capacci committed

\subsection{} How is the category of abelian groups cartesian closed? Describe its exponential functor.\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Sophie Schmidhuber's avatar
Sophie Schmidhuber committed
\iam{Sophie} We already know that the category of abelian groups has all binary products. Now for any two abelian groups B and C define $C^B$ as the set of all homomorphisms from B to C. This is again an abelian group under the addition of homomorphisms, where $(f+g)(b) = f(b)+g(a)$. Furthermore we have  $ev : C^B \oplus B \to C$ sending $(f,b)$ to $f(b)$. Note that this is again a group homomorphism. Now $ev$ satisfies the UMP, since for any abelian group A and $f: A \oplus B \to C$ there exists a unique $\tilde{f} : A \to C^B$ such that $ev(\tilde{f}(a),b) = f(a,b)$, where $\tilde{f}(a)$ is the function that fixes a and sends an element $b \in B$ to $f(a,b)$. Note that also $\tilde{f}$ is a homomorphism. So the category of abelian groups is cartesian closed. 

The exponential functor $-^A: Ab \to Ab$ will send an abelian group B to $B^A$ and a homomorphism $f: B \to C$ to the homomorphism $f^A: B^A \to C^A$, the latter of which sends a homomorphism $g: A \to B$ to the homomorphism $f \circ g: A \to C$. 

Nicola Capacci's avatar
Nicola Capacci committed
\iam{Nicola} Can you tell how this fails in the category of Groups, that is, dropping the abelian condition?
Sophie Schmidhuber's avatar
Sophie Schmidhuber committed

Nicola Capacci's avatar
Nicola Capacci committed

Muhammed Guelen's avatar
Muhammed Guelen committed
\subsection{} Show that, for any objects $A,B$ in a cartesian closed category $\mathbf{C}$ there is a bijective correspondence
Nicola Capacci's avatar
Nicola Capacci committed
\begin{align*}
\Hom(1,B^A)\cong \Hom(A,B)
\end{align*}

Muhammed Guelen's avatar
Muhammed Guelen committed
\iam{Muhammed} This is a straight-forward application of the definition of exponentials. Note that $\mathbf{C}$ is a CCC, and hence all finite products and exponentials exists. In particular, the existence of binary products is guaranteed.  Now, let $A,B \in \text{Ob}(\mathbf{C})$ and $\varepsilon: B^{A} \times B \to B$ an evaluation. Then, for any arrow $f: 1 \times A \to B$, there exists a unique arrow $\tilde{f}: 1 \to B^{A}$ such that $\varepsilon (\tilde{f} \times 1_A) = f$.
Since $1 \times A \cong A$, it suffices to show that $\Hom(1 \times A, B) \cong \Hom(1, B^{A})$.\\[0.1in]
\hspace{0.2cm} \textbf{Claim}. $\Phi: \Hom(1 \times A, B) \to \Hom(1, B^{A}), f \mapsto \tilde{f}$ is an isomorphism.\\[0.02in]
We need to check linearity, injectivity and surjectivity of $\Phi$. These are all together direct consequences from uniqueness property of the transpose. In fact, let $f,g \in  \Hom(1 \times A, B)$. Then, for $h := f+g$, there exists a $\tilde{h}$ s.t. $$\varepsilon (\tilde{h} \times 1_A) = h = f + g  = \varepsilon(\tilde{f} \times 1_A) + \varepsilon(\tilde{g} \times 1_A) =  \varepsilon((\tilde{f} + \tilde{g})  \times 1_A)$$ 
and hence by uniqueness $\tilde{h} = \widetilde{f+g} = \tilde{f} + \tilde{g}$. Injectivity follows straight from the uniqueness again. As for the surjectivity, one sees easily that for any $g \in \Hom(1, B^A)$, the morphism $\bar{g} : = \varepsilon( g \times 1_A): 1 \times A \to B$ satisfies the equation $\Phi(\bar{g}) = \tilde{\bar{g}} = g$ -- once again, by uniqueness of the transpose. This yields surjectivity and completes the proof.

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Prove that, for any cartesian closed category $\mathcal{C}$ with a fixed base object $A$, the operation 
\begin{align*}
A^{(-)}:\mathcal{C}^{op}\to \mathcal{C}
\end{align*}
describes a functor.\hfill\break

\subsection{} Let $\mathcal{C}$ be a cartesian closed category with coproducts, show that it is distributive in the sense that there exists a (natural) isomorphism
\begin{align*}
(A\times C)+(B\times C)\cong (A+B)\times C
\end{align*}

Marius Furter's avatar
Marius Furter committed
\iam{Marius} \emph{(Incomplete: Couldn't find an elegant way to do it elementarily using UMPs of (co)products. Getting a map into the product or out of the coproduct is straightfoward, but I couldn't find an obvious inverse. In any case, there seems to be a lot of calculation involved. Also couldn't find a way based on the approach below that avoids Yoneda lemma.)} 

Let $\mathcal{C}$ be cartesian closed. For any $Y \in \mathcal{C} $ we have the following series of isomorphisms given by the currying isomorphism and the fact that maps out of the coproduct are in bijection with pairs of maps out of the summands.

$$
\begin{aligned}
	\Hom((A+B) \times C, Y) & \cong \Hom(A+B,Y^C) \\
	& \cong \Hom(A,Y^C) \times \Hom(B,Y^C) \\
	& \cong \Hom(A \times C, Y) \times \Hom(B \times C, Y) \\
	& \cong \Hom((A \times C) + (B \times C), Y)  \\
\end{aligned}
$$
Nicola Capacci's avatar
Nicola Capacci committed
From this we want to conclude that $(A+B) \times C, Y) \cong (A \times C) + (B \times C)$. One way to do this is by showing that the isomorphisms above define a natural transformation $\Hom((A+B) \times C, -) \cong \Hom((A \times C) + (B \times C), -)$ and then to apply the Yoneda lemma (in particular, the fact that the Yoneda embedding $A \mapsto Hom(-,A)$ is fully faithful, which implies that $\Hom(-,A) \cong \Hom(-,B) \Leftrightarrow A \cong B$). As we have yet to discuss both of these topics, I will wait with completing this solution until then.
Marius Furter's avatar
Marius Furter committed

Nicola Capacci's avatar
Nicola Capacci committed
\iam{Nicola} Good point!
Nicola Capacci's avatar
Nicola Capacci committed

Andreas Wanner's avatar
Andreas Wanner committed
\section{Discussion: Week 5}
Nicola Capacci's avatar
Nicola Capacci committed

Andreas Wanner's avatar
Andreas Wanner committed
\iam{Andi} Hi, I am a bit late to the party and also did not yet catch up to finish my first solution to an exercise. However I found something cool about Heyting algebras:

In \href{https://twitter.com/johncarlosbaez/status/1243560612757565441}{this} series of recent tweets John Baez gives a quick introduction to Heyting algebras.
I found his tweets and also the replies of others quite interesting. In the last tweet he asks for non-boolean bi-Heyting algebras.
The poset $\lbrace 0,1,2\rbrace$ is the simplest example they find. And he learned:
\textit{"Any totally ordered set with a top and bottom element is a bi-Heyting algebra.     Today I learned this, so today has been a worthwhile day."}

It took me a moment to realize why such totally ordered sets are non-boolean.
I took an explicit definition of boolean algebra from \href{https://ncatlab.org/nlab/show/Boolean+algebra}{nlab} and applied it to the totally ordered set $\lbrace 0,1,2,3\rbrace$:
\begin{itemize}


\item it is a poset.

\item there is a top element $\top = 3$ such that $x \leq \top$ always holds.

\item there is a bottom element $\bot = 0$ such that $\bot \leq x$ always holds.

\item given elements $a$ and $b$, there is an element $a\wedge b$ (a \textit{meet} of $a$ and $b$) such that $x\leq a\wedge b$ holds iff $x\leq a$ and $x\leq b$. For the elements $1$ and $2$ this would be $1\wedge 2=1$.

\item given elements $a$ and $b$, there is an element $a\vee b$ (a \textit{join} of $a$ and $b$) such that $a\vee b\leq x$ holds iff $a\leq x$ and $b\leq x$. For the elements $1$ and $2$ this would be $1\wedge 2=2$.
\end{itemize}
All fulfilled so far, but then:
\begin{itemize}
\item given an element $a$, there is an element $\neg a$ (a \textit{complement} of $a$) such that $a\wedge\neg a\leq \bot$ and $\top\leq a\vee \neg a$. This is not the case for the elements $1$ and $2$.
\item (checking the last condition for boolean algebras: $a \wedge (b \vee c) \leq (a \wedge b) \vee (a \wedge c)$ for any elements $a$, $b$ and $c$, is left to the reader.)
\end{itemize}
Thus the totally ordered set $\lbrace 0,1,2,3\rbrace$ cannot be taken as a boolean algebra.
(In $\lbrace 0,1 \rbrace$ the requirement for complements is still fulfilled.)

I am not totally sure yet, if this is the break with the law of the excluded middle that Heyting algebras are famous for not being required to obey. (But I guess so).
And btw I can really recommend his tweets in the middle, which I did not dare to paraphrase here. (Categorical structure of tweets would be another question. Poset I guess. Unless a hacker manages to post two tweets as a reply to each other.)
 
Nicola Capacci's avatar
Nicola Capacci committed
 \iam{Nicola} This is very interesting, I never really tough about it, so let's analyse this statement closely.
\begin{center}
``\textit{Any totally ordered set with a top and bottom element is a bi-Heyting algebra.}''
\end{center}
Let's start with defining a bi-Heyting algebra. We know that a Heyting algebra is a (finitely) complete and co-complete cartesian closed poset, so let us try to deduce the notion of 
co-Heyting algebra using duality. Firstly observe that the first condition of an Heyting algebra is symmetric under the operation $(-)^{op}$, and that this is broken asking that there exists an exponential map together with the universal property
\begin{align}\label{Heyting Alg}
(- \Rightarrow -):P^{op}\times P\longrightarrow P \nonumber\\
(x\cap y)\leq z \iff x\leq (y\Rightarrow z)
\end{align}
To dualize this definition, let me state that, in reality, being cartesian closed (for any generic category) is equivalent to asking that the functor 
\begin{align*}
(-\cap y):P\longrightarrow P
\end{align*}
admits a right adjoint 
\begin{align*}
(y\Rightarrow -):P\longrightarrow P
\end{align*}
\emph{naturally} in the variable which, in the case of posets, translates to Equation \ref{Heyting Alg}. 

Naturally then, we can expect that a co-Heyting algebra is a (finitely) complete and co-complete co-cartesian closed poset $P$, meaning that the functor 
\begin{align*}
(-\cup y):P\longrightarrow P
\end{align*}
Nicola Capacci's avatar
Nicola Capacci committed
admits an adjoint. Without going trough the details (because we have not seen adjoints yet) let me just state that, for posets, this data is equivalent to a \href{https://ncatlab.org/nlab/show/Galois+connection}{Galois connection} which is a monotone map with the following universal property
Nicola Capacci's avatar
Nicola Capacci committed
\begin{align*}
(- \smallsetminus -):P^{op}\times P\longrightarrow P\\
(x\smallsetminus y)\leq z \iff x\leq (y\cup z)
\end{align*}

Then, a bi-Heyting algebra is a poset with is both a Hyting algebra and a co-Heyting algebra.

\begin{ex}Whoever is interested can check that in any topology open sets form a Heyting algebra while closed ones form a co-Heyting algebra. 
\end{ex}

Returning now to the original statement, we can check that any \emph{totally ordered bounded set} $S$ is a Heyting bi-algebra, starting with the (co)completeness condition.
By the assumption of boundedness we know that $S$ is equipped with a top and least element.  Given any two elements $x,y\in S$, the assumption of total order requires that either $x\leq y$ or $y\leq x$. Without loss of generality let us assume the second case is true. Then it is easy to check that
\begin{align*}
x\cap y\cong x\\
x \cup y \cong y
\end{align*}
In fact, since $S$ is totally ordered, the coprocut ($\cup$) yields the supremum of the two elements while the product ($\cap$) gives the infimum. Together, these facts imply that $S$ is finitely (co)complete.

Now we have to define the maps 
\begin{align*}
(y\Rightarrow -):P&\longrightarrow P\\
(y\smallsetminus -):P&\longrightarrow P
\end{align*}
satisfying the universal properties described above. This I leave to you as an exercise (\emph{Hint}: you have to use the fact that $S$ is a total order). Having done this, we have proven that any bounded total order is a Heying bi-algebra, as per the statement. It only remains to check when the boolean condition is satisfied.

Given any Heyting algebra, we can always define a ``negation'' operation
\begin{align*}
\neg :S^{op}&\longrightarrow S\\
a&\mapsto (a\Rightarrow 0)
\end{align*}
where $0$ is the bottom element. Then a Heyting algebra is boolean if applying the negation twice commutes with the identity, meaning that this diagram commutes:
\begin{center}
\begin{tikzcd}
                                                    & S^{op} \arrow[rd, "\neg"] &   \\
S \arrow[rr, "\mathrm{id}"] \arrow[ru, "\neg^{op}"] &                           & S
\end{tikzcd}
\end{center}
which is just a diagrammatic way to state that $\neg\neg x=x$ for all $x\in S$. However this is seldom satisfied, we can check this for all total orders though. I believe that, except for the order $(0\leq 1)$, no other total order is boolean. If you are interested you can check this statement.

Nicola Capacci's avatar
Nicola Capacci committed
\section{Week 6}

\subsection{} Consider the following composite of \emph{forgetful} functors
\begin{center}
\begin{tikzcd}
\mathbf{Group} \arrow[r, "U"] & \mathbf{Mon} \arrow[r, "V"] & \mathbf{Set}
\end{tikzcd}
\end{center}
Say whether each is faithful, full, injective on arrows, surjective on arrows, injective on objects, and surjective on objects.\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Andreas's avatar
Andreas committed
\iam{Andreas} Let's abbreviate $\{G,M,S\}:=\{\textbf{Group},\textbf{Mon},\textbf{Set}\}$. For $U$: By the definition of a functor, it preserves identity and compositions, hence it is faithful. Further any homomorphisms in $M$ is also a homomorphism in $G$, hence for any $A,B\in G_0$ we have that $U_{A,B}$ is surjective and therefore $U$ is full. For any object $O\in M_0$, if it has an inverse, then it is clear that this object will be unique in $G_0$, so $U$ must be injective on objects. There exist objects in $M_0$ that have no inverse, hence $U$ can not be surjective (though I didn't come up with an example). Hence $U$ is injective on arrows but not surjective.\\
Andreas's avatar
Andreas committed

For $V$: By the definition of a functor, it preserves identity and compositions, hence it is faithful. The class $S_1$ consists of all functions
between sets, hence it must be much larger than $M_1$, therefore not for all $A,B\in M_0$ the map $V_{A,B}$ is surjective and hence $V$ is not full. For any object $O\in S_0$ we can turn it into a group, hence $V$ is surjective on objects. $V$ can not be injective since different objects $O\in M_0$ can have the same cardinality. Hence $V$ is surjective on arrows but not injective.\\
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\iam{Nicola} The functor 
\begin{align*}
U:\mathbf{Group}\longrightarrow \mathbf{Mon}
\end{align*}
is \emph{faithful} if, for any two groups $G$ and $H$, the induced map on Hom-sets
\begin{align*}
U:\Hom_\mathbf{Group}(G,H)\longrightarrow \Hom_\mathbf{Mon}(U(G),U(H))
\end{align*}
is injective, while it is \emph{full} if this map is also surjective. 

Faithfulness of functors is a non-trivial condition, you should check your answer again.


Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Let $(P,\leq)$ be a poset, one can make it into a topological space (whose underlying set is $P$) by declaring $U\subset P$ open only if, for every $x\in U$ and $x\leq y$, then $y\in U$. These sets are called ``upward-closed'', and the resulting topology is called the Alexandroff topology of $(P,\leq)$. Show that monotone maps between posets are continuous in this topology, hence that one obtains a functor 
\begin{align*}
A:\mathbf{Pos}\longrightarrow \mathbf{Top}
\end{align*}
from posets and monotone maps to topological spaces and continuous functions. Is $A$ faithful? Is it full? \hfill \break

\subsection{} Prove that every functor $F:\mathcal{C}\to \mathcal{D}$ can be factored as
\begin{center}
\begin{tikzcd}
                                            & \mathcal{E} \arrow[rd, "D"] &             \\
\mathcal{C} \arrow[rr, "F"] \arrow[ru, "E"] &                             & \mathcal{D}
\end{tikzcd}
\end{center}
in two ways:
\begin{enumerate}
\item With $E$ bijective on objects and full, and $D$ faithful;
\item With $E$ surjective on objects, and $D$ injective on objects, full, and faithful.
\end{enumerate}
When do these factorization agree?\hfill \break

Arno's avatar
Arno committed
\iam{Arno} \\
\begin{enumerate}
\item define $\mathcal{E}$ with $Ob(\mathcal{E})=Ob(\mathcal{C})$ and $Hom_{\mathcal{E}}(X,Y)=Hom_{\mathcal{C}}(X,Y)/\sim$, where $f \sim g$ iff $F(f)=F(g)$ \\
Then let $E$ be the projection and $D$ be the map induced by $F$\\
It's easy to see, that these are indeed functors and Categories, st. the conditions hold.\\
\item define $\mathcal{E}$ with $Ob(\mathcal{E})=\{X \in \mathcal{D}\mid \exists X' \in \mathcal{C}\, with\, F(X')=X\})$ and  $Hom_{\mathcal{E}}(X,Y)=Hom_{\mathcal{D}}(X,Y)$\\
Then let $E$ act as F and $D$ be the inclusion, again one can see the properties.\\
\item The factorizations agree, iff $F$ is injective on objects and full. Clearly if $F$ is injective on objects and full the definitions agree and if they agree, then the fact, that $E$ in the second definition has to be bijective on objects and full yields injectivity on objects and fullness for $F$.
\end{enumerate}

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Let $[\mathcal{D},\mathcal{C}]$ denote the functor category from $\mathcal{D}$ to $\mathcal{C}$. Show that $[\mathcal{D},\mathcal{C}]$ has binary products if $\mathcal{C}$ does. (\emph{Hint}: products are constructed object-wise with $(F\times_{[\mathcal{D},\mathcal{C}]} G)(c)=F(c)\times_\mathcal{C}G(c)$)\hfill \break

Muhammed Guelen's avatar
Muhammed Guelen committed
\iam{Muhammed} Let $F, G: \mathcal{D} \to \mathcal{C}$ and assume that $\mathcal{C}$ has binary products. 

%Hence, for any object $C_1, C_2, X$ in $\mathcal{C}$, there exists $\phi: X \to C_1 \times C_2$ such that the following diagram commutes: \\
%\begin{center}
%
%
%\begin{tikzcd}
%    &  & X \arrow[lldd, "x_1"'] \arrow[rrdd, "x_2"] \arrow[dd, "\exists ! \varphi", dotted] &  &     \\
%    &  &                                                                                    &  &     \\
%C_1 &  & C_1 \times C_2 \arrow[ll, "\pi_{1}"] \arrow[rr, "\pi_2" description]               &  & C_2
%\end{tikzcd}
%\end{center}


Muhammed Guelen's avatar
Muhammed Guelen committed
A morphism between functors $\alpha : F \to G$ is defined to be a family of morphisms in $\mathcal{C}$ parametrized by the objects $D$ in $\mathcal{D}$, that is  $$\alpha_D: F(D) \to G(D).$$ Accordingly, we define the product of $F$ and $G$ object-wise, i.e. $(F \times_{[\mathcal{D},\mathcal{C}]} G)(D) := F(D) \times_{\mathcal{C}} G(D)$. Observe that this is well-defined, since $F(D), G(D)$ are objects in $\mathcal{C}$. The rest is straight-forward. To have a binary product $F \times_{[\mathcal{D},\mathcal{C}]} G$, by the UMP of products, we require the existence of a $\Phi: Z \to F \times G$ 
Muhammed Guelen's avatar
Muhammed Guelen committed
s.t. the following diagram commutes: 

\begin{center}
% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZAJgBoAGAXVJADcBDAGwFcYkQAtEAX1PU1z5CKcqWLU6TVuwBiPPiAzY8BImXE0GLNohAyABAB1DeALbwA+sGTHT9HAAsAxk2AARXkcN3HLxsABhbkpufQBxeX5lISIAFjEJLWldCOCaGCgAc3giUAAzACcIUyRREBwIJABGTSkdEDyQGkZ6ACMYRgAFARVhEAKsTIccSIaiksQyiqQAZlrtdkymkBb2rp6Y3UYYPJHefPHSmmnEMkkF3WMYAA8sOBw4fQBCL06HLGXVju7o1S2dkbNLBgepQCA4HAZUaFYpIM4nGrnZIgYxoLBWKrcT5tb4bP4rAHQw6nY6VRBzJH1VHo4jYtY-QT4gZDPYhIA
\begin{tikzcd}
  &  & Z \arrow[lldd, "f"'] \arrow[rrdd, "g"] \arrow[dd, "\exists ! \Phi", dotted]          &  &   \\
  &  &                                                                                      &  &   \\
F &  & {F \times_{[\mathcal{D}, \mathcal{C}]} G} \arrow[ll, "\pi_{1}"] \arrow[rr, "\pi_2"'] &  & G
\end{tikzcd}

\end{center}
%with $\pi_1, pi_2$ being projections in $[\mathcal{D}, \mathcal{C}]$.\\
Muhammed Guelen's avatar
Muhammed Guelen committed
By definition, this translates to the following diagram: For every object $D \in \text{Ob}(\mathcal{D})$, we have
Muhammed Guelen's avatar
Muhammed Guelen committed
\begin{center}
% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZAJgBoAGAXVJADcBDAGwFcYkQAtEAX1PU1z5CKcqWLU6TVuwBiPPiAzY8BImXE0GLNohAyABAB1DeALbwA+sGTHT9HAAsAxk2AARXkcN3HLxsABhbkpufQBxeX5lISIAFjEJLWldCOCaGCgAc3giUAAzACcIUyRREBwIJABGTSkdEDyQGkZ6ACMYRgAFARVhEAKsTIccSIaiksQyiqQAZlrtdkymkBb2rp6Y3UYYPJHefPHSmmnEMkkF3WMYAA8sOBw4fQBCL06HLGXVju7o1S2dkbNLBgepQCA4HAZUaFYpIM4nGrnZIgYxoLBWKrcT5tb4bP4rAHQw6nY6VRBzJH1VHo4jYtY-QT4gZDPYhIA
\begin{tikzcd}
Muhammed Guelen's avatar
Muhammed Guelen committed
  &  & Z(D) \arrow[lldd, "f_D"'] \arrow[rrdd, "g_D"] \arrow[dd, "\exists ! \Phi_D", dotted]          &  &   \\
Muhammed Guelen's avatar
Muhammed Guelen committed
  &  &                                                                                      &  &   \\
Muhammed Guelen's avatar
Muhammed Guelen committed
F(D) &  & {F(D) \times_{\mathcal{C}} G(D)} \arrow[ll, "\pi_{1, D}"] \arrow[rr, "\pi_{2,D}"'] &  & G(D)
Muhammed Guelen's avatar
Muhammed Guelen committed
\end{tikzcd}
\end{center}
Muhammed Guelen's avatar
Muhammed Guelen committed
where $(F \times_{[\mathcal{D}, \mathcal{C}]} G)(D)$ is subsituted by $F(D) \times_{\mathcal{C}} G(D)$. Note that this diagram now lives in $\mathcal{C}$ and by assumption the binary products in $\mathcal{C}$ exist. This, in particular, means that $F(D) \times_{\mathcal{C}} G(D)$ exists or put differently, $\Phi_D$ exists. But as this is true for every $D \in \text{Ob}(\mathcal{D})$,  this yields 
Muhammed Guelen's avatar
Muhammed Guelen committed
$$\Phi: Z \to  F \times G. $$
again by the notion of morphism between functors. This completes the proof.

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} A groupoid is a category whose arrows are isomorphisms, the category of groupoids and functors between them is called $\mathbf{Grpd}$. Prove that it is cartesian closed. (This is Proposition 7.22 in Awodey) \hfill \break

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Let $\mathcal{C}\simeq \mathcal{D}$ be an equivalence of categories. Prove that $\mathcal{C}$ has products if and only if $\mathcal{D}$ does.\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Marius Furter's avatar
Marius Furter committed
\iam{Marius}(Second argument reducing the equivalent case to the isomorphic case using skeletons.)

Define a skeleton $\text{sk}(\Ca)$ of a category $\Ca$ as follows: For each isomorphism class of objects in $\Ca$, choose one representative and add this to $\text{Ob(sk}(\Ca))$. Then $\text{sk}(\Ca) \simeq \Ca$ under the inclusion functor and $c \cong d$ implies $c = d$ for objects $c,d \in \text{sk}(\Ca)$. Note that the above requires a choice principle and that skeletons are only unique up to isomorphism.

We next observe that equivalent categories have isomorphic skeletons. To see this let $F: \Ca \rightarrow \mathcal{D}$ be an equivalence. This induces an equivalence $\bar{F}: \text{sk}(\Ca) \rightarrow \mathcal{D}$ for an arbitrary skeleton of $\Ca$, with $\bar{F}$ simply being the restriction of $F$ under the inclusion functor of the skeleton, which we shall from now on simply denote $F$. Now consider the induced map $\tilde{F}: \text{sk}(\Ca) \rightarrow \text{sk}(\mathcal{D})$, where $\tilde{F}c$ is set to be the representing object of the isoclass of $Fc$. Moreover, an arrow $Ff : Fc \rightarrow Fd$ induces an arrow $\tilde{F}f: \tilde{F}c \rightarrow \tilde Fd$ by post- and pre-composing with appropriate isomorphisms $\alpha_{Fc}: Fc \rightarrow \tilde Fc$ by setting $\tilde Ff := \alpha_{Fd} Ff \alpha_{Fc}^{-1}$. Functoriality is preserved by this assignment: 
$$\tilde F\text{id}_c = 
\alpha_{Fc} F\text{id}_c \alpha_{Fc}^{-1} =
\alpha_{Fc} \alpha_{Fc}^{-1} =
\text{id}_{\tilde Fc}
$$ and 
$$\tilde F(gf) = 
\alpha_{Fe} F(gf) \alpha_{Fc}^{-1} =
\alpha_{Fe} Fg Ff \alpha_{Fc}^{-1} =
\alpha_{Fe} Fg \alpha_{Fd}^{-1} \alpha_{Fd} Ff \alpha_{Fc}^{-1} =
\tilde Fg \tilde Ff.
$$

We can do the same for the pseudo-inverse $G$ of $F$ to obtain an induced functor $\tilde G : \text{sk}(\mathcal{D}) \rightarrow \text{sk}(\Ca)$. Now because $GF \cong id_\Ca$, we have $\tilde G \tilde F = id_{\text{sk}(\Ca)}$, because our construction preserved the isoclass of the source and target objects, and because isomorphic objects are equal in skeletal categories. Similarly $\tilde F \tilde G = id_{\text{sk}(\mathcal{D})}$. We have thus shown that equivalent categories have isomorphic skeletons.

Using the above, we observe that if $\Ca$ has all limits of a certain type, then so does $\text{sk}(\Ca)$: For any diagram $D: J \rightarrow \text{sk}(\Ca)$, consider the diagram in $\Ca$ obtained by composition with the inclusion $\bar D: J \rightarrow \text{sk}(\Ca) \hookrightarrow \Ca$. This new diagram has a limit $\lim{\bar D}$ in $\Ca$. Moreover, $\lim{\bar D} \cong A$, for an object $A \in \text{sk}(\Ca)$. Hence, composing with this isomorphism we see that $A$ also fulfils the same universal property as $\lim{\bar D}$.

The converse also holds. Suppose $\text{sk}(\Ca)$ has all limits od shape $J$ and let $D: J \rightarrow \Ca$ be a diagram in $\Ca$. For each $c \in \Ca$ choose an isomorphism $\alpha_c: c \rightarrow \bar c$ to its representative $\bar c$ in $\text{sk}(\Ca)$. In this way we obtain a projection functor $P: \Ca \rightarrow \text{sk}(\Ca)$ which maps each object in an isoclass to its representative in $\text{sk}(\Ca)$, and each morphism $f: c \rightarrow c'$ to the composition $\alpha_{c'} f \alpha_c^{-1}$. Using this we get an equivalent diagram in $\text{sk}(\Ca)$ by composing $D$ with the projection functor $P$. By assumption, this diagram has a limit $\lim(PD)$ in $\text{sk}(\Ca)$. We claim that this is also a limit of $D$. Given any cone over $D$, compose with the selected isomorphisms $\{\alpha_d\}_{d \in D}$ to obtain a cone over $PD$ (the way we have defined $P(f)$ ensures that this is indeed a cone). Hence we get a unique morphism $u$ from the apex of the cone into $\lim(PD)$ making the sides the cone over $PD$ commute. Finally, if we view $\lim(PD)$ as a cone over $D$ by composing its legs with $\{\alpha_d^{-1}\}_{d \in D}$, we see that $u$ also makes the sides of this cone over $D$ commute. Hence $\lim(PD) = \lim(D)$, with the caveat that we must shift the base of the cone via a family of isomorphisms.

We are now ready to conclude. Let $\Ca \simeq \mathcal{D}$ and suppose $\Ca$ has all limits of shape J. Then so does $\text{sk}(\Ca)$. Since $\Ca$ and $\mathcal{D}$ have isomorphic skeletons, $\text{sk}(\mathcal{D})$ has all limits of shape J as well. Finally, this implies that $\mathcal{D}$ also has these limits, as desired. By duality the same holds for colimits. In particular, a category have products if and only if all the categories equivalent to it do. 

Nicola Capacci's avatar
Nicola Capacci committed
\iam{Nicola} I was making my way trough your first argument, which should work, when you pushed again. This was the argument I was thinking about when I posted the question, so I'm glad you did, and I'm also happy you agree it is much cleaner.


Marius Furter's avatar
Marius Furter committed
\iam{Marius} (In this first attempt, I tried to solve the exercise by looking at hom functors. Implicitly, I am using the fact that the functor category $\mathbf{Set}^{C^\text{op}}$ has products (because $C$ does) to get products in $\mathbf{Set}^{D^\text{op}}$, which implies $D$ has products. But the argument is hard to follow, and I am not confident it is entirely correct. I might attempt to rephrase this idea more abstractly using the property that the yoneda embedding reflects limits. If, however, an equivalence of categories simply induces an equivalence of yoneda embeddings, then this move does not seem to generate any leverage compared to the above approach.) 

Let $\mathcal{C} \simeq \mathcal{D}$ be equivalent categories with equivalence $F: \mathcal{C} \simeq \mathcal{D}$. We know by the theorem we proved in class that $F$ is fully faithful and essentially surjective. In other words $\Hom(c,x) \cong \Hom(Fc,Fx)$ and any $d \in \mathcal{D}$ is isomorphic to some $Fc$. Consequently, because isomorphic objects have isomorphic Hom-Sets, $\Hom(d,y) \cong \Hom(Fc,Fx)$ for a suitable choice of $c,x$. Furthermore, if $\alpha: d \overset{\sim}{\rightarrow} Fc$ then the following commutes for each $f: A \rightarrow B$ in $\mathcal{D}$ by associativity of composition,
Marius Furter's avatar
Marius Furter committed
\begin{center}
Marius Furter's avatar
Marius Furter committed
	% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZARgBoAGAXVJADcBDAGwFcYkQAdDnGADx2AAJCAFsAvgAoopAIIBKEGNLpMufIRTkK1Ok1bsuPfkNGSAYgGNZCpSux4CRLcR0MWbRJ258Bw8RMtSACEbZRAMe3UiMhcaN31PQx8Tf2kQxR0YKABzeCJQADMAJ1EkMhAcCCQtXXcDDiY0AAt6AH0AKkUw4tLEACYaSqQAZji9Dy9Glo6uwpKRMsGq-rG6zwKAPU7bEB6FxBqhxFHahN2tjLEgA
Marius Furter's avatar
Marius Furter committed
	\begin{tikzcd}
		{\text{Hom}(A,Fc)} \arrow[r, "\alpha_*"] \arrow[d, "f_*"] & {\text{Hom}(A,d)} \arrow[d, "f_*"] \\
		{\text{Hom}(B,Fc)} \arrow[r, "\alpha_*"]                  & {\text{Hom}(B,d)}                 
	\end{tikzcd}
\end{center}
showing that we have a natural isomorphism $\Hom(-,d) \cong \Hom(-,Fc)$ for each $d \in \mathcal{D}$. 

Finally, for any $c,x,y \in \mathcal{C}$ the following commutes 
\begin{center}
	% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZARgBoAGAXVJADcBDAGwFcYkQAdDnGADx2AAJCAFsAvgAoAYgGNSU3gEoQY0uky58hFOQrU6TVuy49+Q0ZLlKVakBmx4CRXcX0MWbRJ258Bw8RJyAJ7KquoOWkRkrjTuRl4mvuYBsvIhKvowUADm8ESgAGYATqJIZCA4EEi6Bh7sUjaFJSJIAEw0lUgAzLGGniANYSDFpYjlnYjttfHDAHoAVI3DzdUdVYg90-0FCxliQA
	\begin{tikzcd}
		{\text{Hom}(x,c)} \arrow[r, "F"] \arrow[d, "f_*"] & {\text{Hom}(Fx,Fc)} \arrow[d, "(Ff)_*"] \\
		{\text{Hom}(y,c)} \arrow[r, "F"]                  & {\text{Hom}(Fy,Fc)}                 
	\end{tikzcd}
\end{center}
because $F(fg) = F(f)F(g)$ by functoriality. We thus have a natural isomorphism $\Hom(-,c) \cong \Hom(F-,Fc)$ for all $c \in C$.

Observe that because $F$ is fully faithful, its image $F(\mathcal{C})$ forms a full subcategory of $\mathcal D$ (each image object has an identity by functoriality, if $h \in \Hom_{F(C)}(FA,FB)$, then $h = Ff$ for $f \in \Hom(A,B)$ by fullness, in particular $F(\mathcal{C})$ is closed under composition because $\mathcal{D}$ is). By the above natural isomorphisms and the UMP of the product 
Marius Furter's avatar
Marius Furter committed
$$\Hom_C(F-,FA) \times \Hom_C(F-,FB) \cong \Hom_C(-,A) \times \Hom_C(-,B) \cong \Hom_C(-, A \times B) \cong \Hom_C(F-, F(A \times B)),$$
where the product is to be understood in the functor category.
Because $\Hom_C(FA,Fc) = \Hom_{F(C)}(FA,Fc)$ for all $c \in \mathcal{C}$ we have $\Hom(F-,Fc) = \Hom_D(-, Fc) \circ F$. Using the above, and the observation that $\Hom_D(-,FA) \circ F  \times \Hom_D(-,FB) \circ F = (\Hom_D(-,FA) \times \Hom_D(-,FB)) \circ F$ yields 
Marius Furter's avatar
Marius Furter committed
$$(\Hom_D(-,FA) \times \Hom_D(-,FB)) \circ F \cong  \Hom_D(-, F(A \times B)) \circ F.$$
Finally, composing on the right with $G$ (functors preserve natural isos) and using $FG \cong id_D$ gives
$$\Hom_D(-,FA) \times \Hom_D(-,FB) \cong  \Hom_D(-, F(A \times B)).$$ 
This shows that any two objects in $F(\mathcal{C})$ have a product, namely $F(A \times B)$. To conclude, let $d,d' \in \mathcal{D}$ be arbitrary. Then by the above there exist $c,c' \in \mathcal{C}$ such that there are natural isomorphisms $\Hom(-,d) \cong \Hom(-,Fc)$ and $\Hom(-,d') \cong \Hom(-,Fc')$, whence 
$$\Hom(-,d) \times \Hom(-,d') \cong \Hom_D(-,Fc) \times \Hom_D(-,Fc') \cong  \Hom_D(-, F(c \times c')).$$
Therefore any pair of objects in $\mathcal{D}$ have a product.

Marius Furter's avatar
Marius Furter committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Regarding the previous question, what sort of properties are \emph{not} preserved by equivalence? Try to give an example of a property of a category that is preserved by isomorphism but not equivalence. \hfill \break

Marius Furter's avatar
Marius Furter committed
\iam{Marius} Our discussion regarding $\mathbf{Fin_{Set}}$ in week 1 shows that smallness is not preserved by equivalence of categories. As we saw, $\mathbf{Fin_{Set}}$ is not small, but equivalent to the small category $\mathbf{Fin_{Ord}}$ of finite ordinals.
Further, we have shown in the previous exercise that every category is equivalent to a skeletal one. Therefore, being skeletal is not preserved by equivalence either.

Here's a fun quote from the nLab entry on the \href{https://ncatlab.org/nlab/show/principle+of+equivalence#terminology}{principle of equivalence}:
Marius Furter's avatar
Marius Furter committed

\emph{Floating around the web (and maybe the nLab) is the idea of half-jokingly referring to a breaking of equivalence invariance as “evil”. This is probably meant as a pedagogical way of amplifying that it is to be avoided.}

Marius Furter's avatar
Marius Furter committed
More generally, since equivalent categories have isomorphic skeletons, and because isomorphic objects have the same "arrow-theoretic" properties, it follows that any property that can be phrased in terms of arrows and their composition is preserved by equivalence of categories. Conversely, extrinsic properties of categories (e.g. smallness, or the fact that isoclasses have a certain size) that cannot be captured by properties of arrows may break equivalence invariance. As a silly example, consider the property "Every object of $\mathcal{C}$ is a group". Clearly, this property fails to be preserved under equivalence since we can construct an abstract category isomorphic to $\mathbf{Group}$ whose objects are not groups.  
Marius Furter's avatar
Marius Furter committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Show that equivalence of categories is an equivalence relation.\hfill \break

\subsection{} A category is called \emph{skeletal} if isomorphic objects are always identical. Show that every category is always equivalent to a skeletal one, that is to say, every category has a ``skeleton''.

Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\section{The Yoneda Lemma}

Nicola Capacci's avatar
Nicola Capacci committed
\iam{Nicola} In this week's talk (week 7) I skipped some details of the proof of the Yoneda lemma, so I thought I could do this here.
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
Let's start with some notation. Throughout I'll denote the functor category between $\mathcal{C}$ and $\mathcal{D}$ as $[\mathcal{C},\mathcal{D}]$, and the category of contravariant functors on $\mathcal{C}$ as 
$$\mathbf{PSh}(\mathcal{C})=[\mathcal{C}^{op},\mathbf{Set}]$$
 which, from now on I will refer to as the category of \emph{pre-sheaves} over $\mathcal{C}$. Also, whenever possible without causing confusion, I will drop the dependency on the base category to denote pre-sheaves.

Of particular interest is the fact that each object of $\mathcal{C}$ has a \emph{characteristic} pre-sheaf, defined by
Nicola Capacci's avatar
Nicola Capacci committed
\begin{align*}
\yo_a:\mathcal{C}^\text{op}&\xrightarrow{\quad} \mathbf{Set}\\
b\,\, &\longmapsto \Hom_\mathcal{C}(b,a)
\end{align*}
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
We are now ready to state the main lemma.

\begin{lem}(Yoneda) Let $\mathcal{C}$ be a locally small category. For every pre-sheaf $G\in[\mathcal{C}^{op},\mathbf{Set}]$ and object $a\in \mathcal{C}_0$ there is a canonical isomorphism
\begin{align*}
Nicola Capacci's avatar
Nicola Capacci committed
\Phi:\mathrm{Nat}(\yo_a,G)\cong G(a)
Nicola Capacci's avatar
Nicola Capacci committed
\end{align*}
Nicola Capacci's avatar
Nicola Capacci committed
between the object of natural transformations, from the characteristic pre-sheaf of $a$ to $G$, and the value of $G$ at $a$. Moreover, this isomorphism is natural both in $a$ and $G$.
Nicola Capacci's avatar
Nicola Capacci committed
\end{lem}

Nicola Capacci's avatar
Nicola Capacci committed
This is the most precise version of the Yoneda lemma, and, without a doubt, the one everyone should know. However, I would like to rephrase it in a weaker, but, I believe, more suggestive way.

The reason that we can do this is that $\mathbf{Cat}$, the category of \emph{small} categories and functors (recall that a small category has a \emph{set} of objects), is cartesian closed with its exponentials given by 
\begin{align*}
\mathcal{C}^\mathcal{D}=[\mathcal{D},\mathcal{C}]
\end{align*}
So that we obtain an evaluation functor, which in the particular case of pre-sheaves looks like 
\begin{align*}
ev:\mathcal{C}^{op}\times \mathbf{PSh}\longrightarrow \mathbf{Set}\\
(a,F)\longmapsto F(a)
\end{align*} 
At the same time, the assignment to each object its characteristic pre-sheaf, is natural as it arises from the hom-functor trough the product/functor-category adjunction in $\mathbf{Cat}$ (a topic which we will encounter in two weeks). Consequently, it arranges itself into a functor called the Yoneda embedding
\begin{align*}
\yo:\mathcal{C}&\xrightarrow{\quad} \mathbf{PSh}\\
a\,\,&\longmapsto \,\yo_a
\end{align*}

Suspending for a moment your disbelief, consider the following composition 
\begin{center}
\begin{tikzcd}
\mathcal{C}^{op}\times \mathbf{PSh} \arrow[rr, "\yo^{op}\times \mathrm{id}"] &  & \mathbf{PSh}^{op}\times \mathbf{PSh} \arrow[rr, "\Hom_{\mathbf{PSh}}"] &  & \mathbf{Set}
\end{tikzcd}
\end{center}
It acts on objects by mapping $a\in \mathcal{C}_0$ and $G:\mathcal{C}^{op}\to \mathbf{Set}$ to
\begin{align*}
(a,G)\longmapsto (\yo_a,G)\longmapsto \mathrm{Nat}(\yo_a,G)
\end{align*}
where the last morphism evaluates to natural transformations because in the functor category $\mathbf{PSh}(\mathcal{C})$ morphisms are given by $\Hom_{\mathbf{PSh}}(F,G) = \mathrm{Nat}(F,G)$. 

Both this composition and the evaluation functor have source $\mathcal{C}^{op}\times \mathbf{PSh}$ and values in $\mathbf{Set}$. It is not hard to see how, together, the isomorphisms of the Yoneda lemma and the statement of their naturality arrange themselves into a natural isomorphism connecting these two functors, at least in the special case of \emph{small} categories where these are defined. 
\begin{center}
\begin{tikzcd}
                                                                                                                             & \; \arrow[dd, Rightarrow, "\Phi"',shorten >=1.5ex, shorten <=1.5ex] &              \\
\mathcal{C}^{op}\times \mathbf{PSh} \arrow[rr, "{\mathrm{Nat}(\yo_{(-)},-)}", bend left=49] \arrow[rr, "ev"', bend right=49] &               & \mathbf{Set} \\
                                                                                                                             & \;            &             
\end{tikzcd}
\end{center}
Our immediate goal is to do this: defining $\Phi$, proving that it is natural, and proving that it is an iso. 

Recall that natural transformations are defined \emph{point-wise} on the source, meaning that to define $\Phi$ we need to specify a function (in $\mathbf{Set}$) for each $a\in \mathcal{C}_0$ and $F\in \mathbf{PSh}$. This function is defined as follows 
\begin{align*}
\Phi_{a,F}:\mathrm{Nat}(\yo_a,F)&\longrightarrow F(a)\\
(\alpha:\yo_a \xLongrightarrow{} F)&\mapsto \alpha_a(\id_a)
\end{align*}
by the observation that, amongst more data, a natural transformation $\alpha:\yo_a\Rightarrow F$ specifies a function
\begin{align*}
\alpha_a: \yo_a(a)=\Hom_\mathcal{C}(a,a)&\longrightarrow F(a)\\
\id_a &\longmapsto \alpha_a(\id_a)
\end{align*}
which justifies how $\alpha_a(\id_a)\in F(a)$. 

Firstly, we will prove that this family of functions is natural, hence that $\Phi$ is indeed a natural transformation.

\begin{proof}[Proof of Naturality] In order to prove the naturality of $\Phi$ we will need to check that two diagrams commute, one that has to do with morphisms in $\mathcal{C}$, and one that takes care of natural transformations in $\mathbf{PSh}$. And, while perhaps an expert  in category theory could conjure these with ease, let us take a 2-categorical point of view to understand where these come from.

As we mentioned now multiple times, a functor from the terminal category $\star$ to any generic category $\mathcal{D}$ acts by selecting a single object, which by convention we take to label the functor. Similarly, a morphism $f:a\to b$ in $\mathcal{D}$ can be expressed as a natural transformation
\begin{center}
\begin{tikzcd}
                                                                   & \; \arrow[dd, Rightarrow, "f"',shorten >=1.5ex, shorten <=1.5ex]&             \\
\star \arrow[rr, "a", bend left=49] \arrow[rr, "b"', bend right=49] &    & \mathcal{D} \\
                                                                   & \; &            
\end{tikzcd}
\end{center}

I repeat this because it gives what I believe to be a nice way to visualize the componenets of $\Phi$. Specifically, if one considers the diagram below, there are two functors from the terminal category to $\mathbf{Set}$, each of which selects a set, and the natural transformation between them which ``selects'' the component $\Phi_{a,F}$ of $\Phi$.
\begin{center}
\begin{tikzcd}
                              &  &                                                                                                                              & \; \arrow[dd, Rightarrow, "\Phi"',shorten >=1.5ex, shorten <=1.5ex]&              \\
\star \arrow[rr, "{\{a,F\}}"] &  & \mathcal{C}^{op}\times \mathbf{PSh} \arrow[rr, "{\mathrm{Nat}(\yo_{(-)},-)}", bend left=49] \arrow[rr, "ev"', bend right=49] &    & \mathbf{Set} \\
                              &  &                                                                                                                              & \; &             
\end{tikzcd}
\end{center}
Now let us fix $F$ (one could in principle do both $a$ and $F$ at the same time but this is not very wise), and consider a morphism $f:a\to b$ in $\mathcal{C}$
\begin{center}
\begin{tikzcd}
                                                                                    & \; \arrow[dd, Rightarrow, "f^{op}\times \id",shorten >=1.5ex, shorten <=1.5ex] &                                                                                                                              & \; \arrow[dd, Rightarrow, "\Phi"',shorten >=1.5ex, shorten <=1.5ex]&              \\
\star \arrow[rr, "{\{a,F\}}"', bend right=49] \arrow[rr, "{\{b,F\}}", bend left=49] &    & \mathcal{C}^{op}\times \mathbf{PSh} \arrow[rr, "{\mathrm{Nat}(\yo_{(-)},-)}", bend left=49] \arrow[rr, "ev"', bend right=49] &    & \mathbf{Set} \\
                                                                                    & \; &                                                                                                                              & \; &             
\end{tikzcd}
\end{center}
Now there are four different paths going from the terminal category to $\mathbf{Set}$, connected each by natural transformations. If we evaluate (as in look at their images) in $\mathbf{Set}$ these yield a square
\begin{center}
\begin{tikzcd}
{\mathrm{Nat}(\yo_a,F)} \arrow[dd, "{\Phi_{a,F}}"] &  & {\mathrm{Nat}(\yo_b,F)} \arrow[ll, "\yo(f)_*"'] \arrow[dd, "{\Phi_{b,F}}"] \\
                                                    &  &                                                                             \\
F(a)                                                &  & F(b) \arrow[ll, "F(f)"]                                                    
\end{tikzcd}
\end{center}
whose commutativity guarantee naturality in $a\in \mathcal{C}_0$. 

\emph{Try to convince yourself of this fact, i.e. that naturality means that whichever path you take you should commute in the target}.


To see that this square commutes, pick a natural transformation $\beta\in \mathrm{Nat}(\yo_b,F)$ and run trough the diagram
\begin{center}
\begin{tikzcd}
(\yo_a \xRightarrow{\yo(f)} \yo_b\xRightarrow{\beta} F) \arrow[dd, "{\Phi_{a,F}}", maps to] &  & (\yo_b\xRightarrow{\beta} F) \arrow[ll, "\yo(f)_*"', maps to] \arrow[dd, "{\Phi_{b,F}}", maps to] \\
                                                                                  &  &                                                                                \\
{} \,\,                                                                               &  & \beta_b(\id_b) \in F(b) \arrow[ll, "F(f)", maps to]                                            
\end{tikzcd}
\end{center}
This gives an equation
\begin{align*}
 F(f)(\beta_b(\id_b))=& (\beta\circ \yo(f))_a(\id_a)\\
 =& \beta_a(f)
\end{align*}
 which is satisfied because the naturality of $\beta$ implies the commutativity of the following diagram
 \begin{center}
\begin{tikzcd}
\yo_b(b) \arrow[dd, "\yo_b(f)"] \arrow[rr, "\beta_b"] &  & F(b) \arrow[dd, "F(f)"] &  & \id_b \arrow[dd, maps to] \arrow[rr, maps to] &  & \beta_b(\id_b) \arrow[dd, maps to] \\
                                                      &  &                         &  &                                               &  &                                    \\
\yo_b(a) \arrow[rr, "\beta_a"]                        &  & F(a)                    &  & f \arrow[rr, maps to]                         &  & \beta_a(f)=F(f)(\beta_b(\id_b))   
\end{tikzcd}
 \end{center}

This proves naturality with respect to $a\in \mathcal{C_0}$. In a similar fashion, to prove naturality in $F\in \mathbf{PSh}$, fix an object $a\in \mathcal{C}$ and pick a natural transformation $(\gamma:F\Rightarrow G)\in \mathbf{PSh}$. We again express it as
\begin{center}
\begin{tikzcd}
                                                                                    & \; \arrow[dd, Rightarrow, " \id\times \gamma",shorten >=1.5ex, shorten <=1.5ex]&                                                                                                                              & \; \arrow[dd, Rightarrow, " \Phi"',shorten >=1.5ex, shorten <=1.5ex] &              \\
\star \arrow[rr, "{\{a,G\}}"', bend right=49] \arrow[rr, "{\{a,F\}}", bend left=49] &    & \mathcal{C}^{op}\times \mathbf{PSh} \arrow[rr, "{\mathrm{Nat}(\yo_{(-)},-)}", bend left=49] \arrow[rr, "ev"', bend right=49] &    & \mathbf{Set} \\
                                                                                    & \; &                                                                                                                              & \; &             
\end{tikzcd}
\end{center}
and look at the image that the terminal category has in $\mathbf{Set}$ with respect to these functors and natural transformations. They yield the square which commutes because, choosing a natural transformation $\alpha \in \mathrm{Nat}(\yo_a, F)$, one obtains
\begin{center}
\begin{tikzcd}
{\mathrm{Nat}(\yo_a,F)} \arrow[rr, "\gamma_*"] \arrow[dd, "{\Phi_{a,F}}"] &  & {\mathrm{Nat}(\yo_a,G)} \arrow[dd, "{\Phi_{a,G}}"] &  & (\alpha:\yo_a\Rightarrow F)) \arrow[rr, maps to] \arrow[dd, maps to] &  & (\yo_a \xRightarrow{\alpha}F\xRightarrow{\gamma} G) \arrow[dd, maps to] \\
                                                                          &  &                                                    &  &                                                                      &  &                                                                         \\
F(a) \arrow[rr, "\gamma_a"]                                               &  & G(a)                                               &  & \alpha_a(\id_a) \arrow[rr, maps to]                                  &  & (\gamma\circ \alpha)_a(\id_a)                                        
\end{tikzcd}
\end{center}
This finishes the proof that $\Phi$ is a well defined natural transformation.
\end{proof}

Now that we know that $\Phi$ is well defined, the Yoneda lemma for small categories reduces to the statement that $\Phi$ is a natural isomorphism, which we prove now.

\begin{proof}[Proof of Isomorphism] As stated in week 6, a natural transformation is a natural isomorphism if and only if it is an isomorphism \emph{point-wise}. Hence, it suffices for us to show that, having fixed $a\in \mathcal{C}_0$ and $F:\mathcal{C}^{op}\to \mathbf{Set}$, the function 
\begin{align*}
\Phi_{a,F}:\mathrm{Nat}(\yo_a,F)&\longrightarrow F(a)\\
(\alpha:\yo_a \xLongrightarrow{} F)&\mapsto \alpha_a(\id_a)
\end{align*}
is a bijection. We do this, of course, constructing its inverse.

Hence, let us define a function that assigns to each point $x\in F(a)$ a natural transformation
\begin{align*}
\Gamma_{a,F}:F(a)&\longrightarrow \mathrm{Nat}(\yo_a,F)\\
x&\longmapsto (\chi :\yo_a\Rightarrow F)
\end{align*}
defined, as usually, point-wise for each $c\in \mathcal{C}$
\begin{align*}
\chi_c: (\yo_a(b)=\Hom_\mathcal{C}(c,a))&\longrightarrow F(c)\\
(g:c\to a)&\longmapsto F(g)(x)\in F(c)
\end{align*}
which is well defined because, in the image of $F$, we have 
\begin{align*}
F(a) &\xrightarrow{F(g)} F(c)\\
x&\longmapsto F(g)(x)
\end{align*}

Now, to show that these two functions are inverse, pick $x\in F(a)$ and build the natural transformation $\chi:\yo_a\to F$ as above. Then, to see what this natural transformation is mapped to under $\Phi_{a,F}$ we need to evaluate it at $a$
\begin{align*}
\chi_a:\yo_a(a)&\longrightarrow F(a)\\
\id_a &\longmapsto F(\id_a)(x)= \id_{F(a)}(x)=x
\end{align*}
where we used the functoriality of $F$. This proves that $\Gamma$ is a right inverse to $\Phi$.

In the other direction, let us start with a natural transformation $\alpha:\yo_a\Rightarrow F$. Under $\Phi$ this is mapped to $\alpha_a(\id_a)\in F(a)$, as we have already seen. Pushing forward, this element of $F(a)$ yields under $\Gamma_{a,F}$ a natural transformation $\chi:\yo_a\Rightarrow F$ which, at $c\in \mathcal{C}_0$, evaluates to 
\begin{align*}
\chi_c: (\yo_a(b)=\Hom_\mathcal{C}(c,a))&\longrightarrow F(c)\\
(g:c\to a)&\longmapsto F(g)(\alpha_a(\id_a))
\end{align*}
Then, $\Phi$ and $\Gamma$ are inverses if $\chi_c(g)=\alpha_c(g)=F(g)(\alpha_a(\id_a))$, which we see by observing that the naturality of $\alpha$ implies that for all $g:c\to a$ the following diagram commutes
\begin{center}
\begin{tikzcd}
\yo_a(a) \arrow[dd, "\yo_a(g)"] \arrow[rr, "\alpha_a"] &  & F(a) \arrow[dd, "F(g)"] &  & \id_a \arrow[dd, maps to] \arrow[rr, maps to] &  & \alpha_a(\id_a) \arrow[dd, maps to] \\
                                                       &  &                         &  &                                               &  &                                     \\
\yo_a(c) \arrow[rr, "\alpha_c"]                        &  & F(c)                    &  & g \arrow[rr, maps to]                         &  & \alpha_c(g)=F(g)(\alpha_a(\id_a))  
\end{tikzcd}
\end{center}
We now know that $\Phi_{a,F}$ has an inverse $\Gamma_{a,F}$ for all choices of $a$ and $F$, hence it is an isomorphism in all components and consequently a natural isomorphism. This concludes the proof.
\end{proof}

Before signing off let me comment on why the Yoneda lemma is not usually stated this way, as a natural transformation being a natural isomorphism. The problem is, as all ugly things are in category theory, to do with set-theoretic issues. Specifically, all the categories that we consider are \emph{locally small}, which I remind you means that between any two objects is a \emph{set} of morphism. However, as we very conveniently avoided to say, functor categories between locally small categories are not usually locally small, meaning that between any two functors there could be a \emph{class} of natural transformation instead of a set. It is not hard to see why this is, a single natural transformation is indexed by the objects in the source, and, if this is a class of objects (rather then a set), then it is only by a miracle that natural transformation could form a set.

Remarkably, as a side remark, this happens as a consequence of the Yoneda lemma. The bijection 
\begin{align*}
\Phi:\mathrm{Nat}(\yo_a,G)\cong G(a)
\end{align*}
implies that $\mathrm{Nat}(\yo_a,G)$ is a set!

Now, what breaks if we consider locally small categories? First of all we need to be incredibly careful on how we even define functor categories between them, or even pre-sheaves categories over them. Specifically, we would need to define a new category $\mathbf{SET}$ of large  sets (whatever this means), and have our categories be enriched over this (we will see what enrichment means later). Then one obtains $\mathbf{CAT}$, the category of large category, which, for all intents and purposes, should be cartesian closed and possesses evaluation functors. However, saying precisely what this are is rather complicated. And, while one \emph{can} write a diagram like 
\begin{center}
\begin{tikzcd}
                                                                                                                             & \; \arrow[dd, Rightarrow, "\Phi"',shorten >=1.5ex, shorten <=1.5ex] &              \\
\mathcal{C}^{op}\times \mathbf{PSh} \arrow[rr, "{\mathrm{Nat}(\yo_{(-)},-)}", bend left=49] \arrow[rr, "ev"', bend right=49] &               & \mathbf{SET} \\
                                                                                                                             & \;            &             
\end{tikzcd}
\end{center}
I'm sure that this would turn any logician purple. 

Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\section{Week 7}
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Let $F:\mathcal{C}\to \mathcal{D}$ be a full and faithful functor, show that $c\cong c' \in \mathcal{C}$ if and only if $F(c)\cong F(c')\in \mathcal{D}$.\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Prove that if $F:\mathcal{C}\to \mathbf{Set}$ is representable then it preserves monomorphisms. Use this fact to describe a functor which is \emph{not} representable.\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Is the property of being a representable functor preserved by equivalence of categories? Let $F:\mathcal{C}\to \mathbf{Set}$ and $G:\mathcal{D}\to \mathbf{Set}$ be two covariant functors and $H:\mathcal{C}\simeq \mathcal{D}$ an equivalence of categories such that $F\cong G\circ H$ in the functor category $[\mathcal{C},\mathbf{Set}]$.
\begin{enumerate}
\item If $F$ is representable, is $G$?
\item If $G$ is representable, is $F$?
\end{enumerate}
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Prove that the following are equivalent statements
\begin{enumerate}
\item $f:c\to d$ in $\mathcal{C}$ is an isomorphism;
\item $f_*:\Hom_\mathcal{C}(-,c)\Rightarrow \Hom_\mathcal{C}(-,d)$ is a natural isomorphism;
\item $f^*: \Hom_\mathcal{C}(d,-)\Rightarrow \Hom _\mathcal{C}(c,-)$ is a natural isomorphism.
\end{enumerate}
(\emph{Hint:} This is a strengthening of Lemma 1.2.3 in Riehl) \hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Are there non-idenetity natural endomorphisms in the category of spaces?  That is, does there exist a family of continuous (non-identity) maps $X\to X$, one for each space and natural with respect to the morphisms in $\mathbf{Top}$?\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} Let $\Delta$ be the simplex category, whose objects are finite ordinal numbers $0,1,2,\dots$ viewed as total orders and order-preserving functions between them. Recall that we defined \emph{simplicial sets} as presheaves over $\Delta$, so that $\mathbf{sSet}\cong [\Delta^{op},\mathbf{Set}]$. Write 
\begin{align*}
[-]:\Delta\longrightarrow \mathbf{Pos}
\end{align*}
for the evident inclusion of categories. For each poset $P$, define the simplicial set $S(P):\Delta^{op}\to \mathbf{Set}$ by 
\begin{align*}
S(P)(n)=\Hom_\mathbf{Pos}([n],P)
\end{align*}
Show that this assignment describes a functor $S:\mathbf{Pos}\to \mathbf{sSet}$. Is $S$ faithful? Show that $S$ preserves all limits.\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed
\subsection{} In the previous exercise the functor $S:\mathbf{Pos}\to \mathbf{sSet}$ describes the \href{https://ncatlab.org/nlab/show/nerve}{nerve} of a poset, generalize this construction to locally small category by post-composing with the inclusion
\begin{align*}
V:\mathbf{Pos}\longrightarrow \mathbf{Cat}
\end{align*}

\subsection{} Use the Yoneda lemma to show that, for any locally small cartesian closed category $\mathcal{C}$ with objects $A$, $B$ and $C$, the following equation holds
\begin{align*}
(A\times B)^C\cong A^C\times B^C
\end{align*}
And if $\mathcal{C}$ has additionally coproducts then
\begin{align*}
A^{(B+C)}\cong A^B\times A^C
\end{align*}


\subsection{} Let $C$ be a locally small category with binary products, show that the Yoneda embedding 
\begin{align*}
\yo:\mathcal{C}\longrightarrow [\mathcal{C}^{op},\mathbf{Set}]
\end{align*}
preserves them. Further, if $\mathcal{C}$ has exponentials, show that $\yo$ preserves them too.\hfill \break
Nicola Capacci's avatar
Nicola Capacci committed

Nicola Capacci's avatar
Nicola Capacci committed


Andreas Wanner's avatar
Andreas Wanner committed

Nicola Capacci's avatar
Nicola Capacci committed
\end{document}