Newer
Older
\documentclass{amsart}
\usepackage[foot]{amsaddr}
\usepackage{bbm}
\usepackage{mathbbol}
\usepackage{amsmath,amssymb,amsfonts, amsthm, graphicx}
\usepackage{mathtools}
%\usepackage{stmaryrd}
\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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
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
149
150
151
\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}
%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}}}
\newcommand{\Id}{\textrm{Id}}
\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{\id}{\textbf{id}}
\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.
Questions, answers and comments will be posted the following way:
I don't know but it is not green.
\iam{An Other Student}
YELLOW!
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!
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{} 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{Olga}
According to p.5 of Awodey's book we have to show that associativity and identity laws hold true:\\
1. Associativity:
\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
\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
\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
\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
\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.