A personal blog about computer science topics.

Sets of Morphisms
Posted on Jan 18 2020 ~ 5 min read
#category theory  #haskell 

In category theory, hom-sets, are sets of morphisms between objects. Given objects A A and B B in a locally small category, the hom-set Hom ( A , B ) \text{Hom}(A,B) is the set of all morphisms { 0 , \{\rightarrow_0, 1 , \rightarrow_1, 2 , \rightarrow_2, , \dots, n } \rightarrow_n\} from A to B.

\begin{xy} \xymatrix{ A \ar@/^/[r] \ar@/^1pc/[r] \ar[r] \ar@/_/[r] \ar@/_1pc/[r] & B } \end{xy}

Hom-sets itself give rise to another category where hom-sets are objects and arrows between hom-sets are hom-set morphisms. A hom-set morphism is defined as:

Hom ( A , f ) : Hom ( A , B ) Hom ( A , D ) \text{Hom}(A,f) : \text{Hom}(A,B) \rightarrow \text{Hom}(A,D) , f f' \rightarrow f f f \circ {f'} for f : B D f : B \rightarrow D

Hom ( h , B ) : Hom ( A , B ) Hom ( C , B ) \text{Hom}(h,B) : \text{Hom}(A,B) \rightarrow \text{Hom}(C,B) , h h' \rightarrow h h h' \circ {h} for h : C A h : C \rightarrow A

such that the following diagram commutes:

\begin{xy} \xymatrix@!C=4.0cm@!R=1.0cm{ \text{Hom}(A,B) \ar[dr]|-{\text{Hom}(h,f)} \ar[d]_{\text{Hom}(A,f)} \ar[r]^{\text{Hom}(h,B)} & \text{Hom}(C,B) \ar[d]^{Hom(C,f)} \\ \text{Hom}(A,D) \ar[r]_{\text{Hom}(h,D)} & \text{Hom}(C,D) } \end{xy}

This can be translated to Hask, the category with Haskell types as objects and functions as morphisms. The previous morphisms f , h f,h are now functions:

f :: b -> d
h :: c -> a

and Hom ( A , B ) = a b \text{Hom}(A,B) = a \rightarrow b , such that:

\begin{xy} \xymatrix@!C=4.0cm@!R=1.0cm{ a\ \rightarrow\ b \ar[dr]|-{c\ \rightarrow\ a\ \rightarrow\ b\ \rightarrow\ d} \ar[d]_{a\ \rightarrow\ b\ \rightarrow\ d} \ar[r]^{c\ \rightarrow\ a\ \rightarrow\ b} & c\ \rightarrow\ b\ \ar[d]^{c\ \rightarrow\ b\ \rightarrow\ d} \\ a\ \rightarrow\ d\ \ar[r]_{c\ \rightarrow\ a\ \rightarrow\ d} & c\ \rightarrow\ d } \end{xy}

Let’s have a closer look at the morphism from a b a \rightarrow b to c b c \rightarrow b . So we have a a b a \rightarrow b and a morphisms that tells us we can go c a b c \rightarrow a \rightarrow b resulting in c b c \rightarrow b . Now, this makes sense if we remember how function composition works:

\begin{xy} \xymatrix { c \ar[r]^{f'} \ar[dr]_{g' \circ {f'}} & a \ar[d]^{g'} & \\ & b &&&&& } \end{xy}

We can see that c b c \rightarrow b is the function composition g f g' \circ {f'} . Thus, a hom-set morphism Hom ( f , ) \text{Hom}(f,-) is simply morphism pre-composition f f \circ - and Hom ( , f ) \text{Hom}(-,f) is just morphism post-composition f - \circ f . Furthermore, Hom ( A , ) \text{Hom}(A,-) , which you can think of as A A \rightarrow , is called a covariant hom-functor or representable functor from the category C C to the category S e t Set , x Hom C ( A , x ) x \rightarrow \text{Hom}_C(A,x) with x C x \in C and Hom C ( A , x ) S e t \text{Hom}_C(A,x) \in Set .

When the second position is fixed Hom ( , B ) : C o p S e t \text{Hom}(-,B): C^{op} \rightarrow Set (which you can think of as: B \rightarrow B ) then it’s called a contravariant functor. Consequently, if non of the arguments of the hom-functor are fixed Hom ( , ) : C o p × C S e t \text{Hom}(−,−): C^{op} \times C \rightarrow Set then we have a hom bifunctor also called profunctor, see for instance the diagonal arrow Hom ( h , f ) \text{Hom}(h,f) with pre- and post-composition.