Exercises.tex

\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.

\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}

\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}

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$.

\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}

\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

\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*}
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}
\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})$\\
\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})$\\
\end{enumerate}

\subsection{} Is the category of monoids cartesian closed?\hfill \break
\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}

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})$:

\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}

\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.



\subsection{} How is the category of abelian groups cartesian closed? Describe its exponential functor.\hfill \break

\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$. 

\iam{Nicola} Can you tell how this fails in the category of Groups, that is, dropping the abelian condition?


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

\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.

\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*}

\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}
$$
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.

\iam{Nicola} Good point!

\section{Discussion: Week 5}

\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.)
 
 \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*}
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
\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.

\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

\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.\\

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.\\

\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.


\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

\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}

\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

\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}


A morphism between functors $\alpha : F \to G$ is defined to be a family of morphisms parametrized by the objects in $\mathcal{C}$, that is  $$\alpha_C: F(C) \to G(C).$$ Accordingly, we define the product of $F$ and $G$ object-wise, i.e. $(F \times_{[\mathcal{D},\mathcal{C}]} G)(C) := F(C) \times_{\mathcal{C}} G(C)$. Observe that this is well-defined, since $F(C), G(C)$ 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$ 
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}]$.\\
By definition, this translates to the following diagram: For every object $C \in \text{Ob}(\mathcal{C}$, we have
\begin{center}
% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZAJgBoAGAXVJADcBDAGwFcYkQAtEAX1PU1z5CKcqWLU6TVuwBiPPiAzY8BImXE0GLNohAyABAB1DeALbwA+sGTHT9HAAsAxk2AARXkcN3HLxsABhbkpufQBxeX5lISIAFjEJLWldCOCaGCgAc3giUAAzACcIUyRREBwIJABGTSkdEDyQGkZ6ACMYRgAFARVhEAKsTIccSIaiksQyiqQAZlrtdkymkBb2rp6Y3UYYPJHefPHSmmnEMkkF3WMYAA8sOBw4fQBCL06HLGXVju7o1S2dkbNLBgepQCA4HAZUaFYpIM4nGrnZIgYxoLBWKrcT5tb4bP4rAHQw6nY6VRBzJH1VHo4jYtY-QT4gZDPYhIA
\begin{tikzcd}
  &  & Z(C) \arrow[lldd, "f_C"'] \arrow[rrdd, "g_C"] \arrow[dd, "\exists ! \Phi_C", dotted]          &  &   \\
  &  &                                                                                      &  &   \\
F(C) &  & {F(C) \times_{\mathcal{C}} G(C)} \arrow[ll, "\pi_{1, C}"] \arrow[rr, "\pi_{2,C}"'] &  & G(C)
\end{tikzcd}
\end{center}
where $(F \times_{[\mathcal{D}, \mathcal{C}]} G)(C)$ is subsituted by $F(C) \times_{\mathcal{C}} G(C)$. 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(C) \times_{\mathcal{C}} G(C)$ exists or put differently, $\Phi_C$ exists. But as this is true for every $C \in \text{Ob}(\mathcal{C})$,  this yields 
$$\Phi: Z \to  F \times G. $$
again by the notion of morphism between functors. This completes the proof.

\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

\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

\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. 

\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,
\begin{center}
	% https://tikzcd.yichuanshen.de/#N4Igdg9gJgpgziAXAbVABwnAlgFyxMJZARgBoAGAXVJADcBDAGwFcYkQAdDnGADx2AAJCAFsAvgAoopAIIBKEGNLpMufIRTkK1Ok1bsuPfkNGSAYgGNZCpSux4CRLcR0MWbRJ258Bw8RMtSACEbZRAMe3UiMhcaN31PQx8Tf2kQxR0YKABzeCJQADMAJ1EkMhAcCCQtXXcDDiY0AAt6AH0AKkUw4tLEACYaSqQAZji9Dy9Glo6uwpKRMsGq-rG6zwKAPU7bEB6FxBqhxFHahN2tjLEgA
	\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 
$$\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 
$$(\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.


\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

\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}:

\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.}

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.  

\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''.














\end{document}