beuke.org

A personal blog about computer science, theoretical physics and other interesting topics.

Hom-Set
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.

AB

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:

Hom(A,B)Hom(h,f)Hom(A,f)Hom(h,B)Hom(C,B)Hom(C,f)Hom(A,D)Hom(h,D)Hom(C,D)

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:

a  bc  a  b  da  b  dc  a  bc  b c  b  da  d c  a  dc  d

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:

cfgfagb

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.