Newer
Older
\documentclass{amsart}
\usepackage[foot]{amsaddr}
\usepackage{bbm}
\usepackage{mathbbol}
\usepackage{amsmath,amssymb,amsfonts, amsthm, graphicx}
\usepackage{mathtools}
\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
\tikzset{every picture/.style={line width=0.75pt}} %set default line width to 0.75pt
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
\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}
%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}
%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}}}
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
\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}}
\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
\newcommand{\iam}[1]{\vspace{.1cm}{\fbox{\textbf{#1}}}\vspace{.1cm}}
\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
%%--------------------------------------
\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.
\begin{itemize}
\item Questions, answers and comments will be posted the following way:
\end{itemize}
I don't know but it is not green.
\iam{An Other Student}
YELLOW!
\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)
\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}
\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
\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
\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}
\iam{Olga}
According to p.5 of Awodey's book we have to show that associativity and identity laws hold true:\\
1. Associativity:\\
For any $f : A \rightarrow B$, $f : B \rightarrow C$, $f : C \rightarrow D$ morphisms in the category \textbf{Rel}:\\
\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
\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
\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.
\subsection{} Check that functors compose in an associative way, proving that $\mathbf{Cat}$ is a category. \hfill \break
\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
$$
$$
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,
$$
(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)
$$
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).
\iam{Rızacan} Let $f$ be an arrow with Cod($f$)=$B$ and Dom($f$)=$A$. Suppose
$g,g'$ are both inverses of $f$. Then by associativity and properties of
the identity: $g'=\id_A\circ
z\subsection{} Argue whether the following \emph{isomorphisms} of categories hold:
\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
\subsection{} Show that in $\mathbf{Set}$ isomorphisms are bijections.\hfill \break
\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.
\subsection{} Show that in $\mathbf{Mon}$, the category of monoids, isomorphisms are bijective homomorphisms.\hfill \break
\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
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}$.
\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.
\subsection{} Show that in $\mathbf{Pos}$, the category of posets, isomorphisms are \emph{not} bijective homomorphisms.\hfill \break
\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.
\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
\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
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
\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.
\subsection{} (\emph{Harder}) Prove the universal mapping property of free categories on graphs. \hfill \break
\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.
\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$).
\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.
\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?
\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.
\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!
\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
\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.
\subsection{} Show that in a poset, treated as a skeletal category, all arrows are both monic and epic.\hfill \break
\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$).
\subsection{} For the following exercises, consider the typical commutative diagram
\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}$.
\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
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
\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}
\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
\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.
\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
\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}
\subsection{} Show that in any category, any retract of a projective object is projective. \hfill \break
\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,
$$
\tau \psi = \tau \psi' h = \varphi gh = \varphi.
$$
This proves the claim.
\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
\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.
\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
\subsection{} Show that a homomorphisms of graphs $h:G\to H$ is monic just if it is injective on edges and vertices.\hfill \break
\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.
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
\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}
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
\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.
\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.
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
\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}
\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
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
\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$.
\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}$
\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\,|$''.
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.
\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
\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.
\subsection{} Show that $\mathbf{Mon}$ has all equalizers and finite products.\hfill \break
\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.
\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?
\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
\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!)
\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.
\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)
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
\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
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
\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}
\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}
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.\\
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
$\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}
\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}