INTRODUCTION TO CATEGORY THEORY
Graham Hutton
School of Computer Science
University of Nottingham
----------------------------------------------------------------------
Exercises for lecture 1:
o Formalise the result that every simple graph is trivially a
labelled graph, in which each edge A -> B is labelled by (A,B).
o Prove that composition in the category SET is associative.
o Define a suitable category MON that has monoids as objects, taking
care to ensure that your notion of arrow within the category
preserves the underlying structure of monoids.
----------------------------------------------------------------------
Exercises for lecture 2:
o Give examples of homomorphisms and non-homomorphisms on labelled
graphs, using the example on slide 1.11 as the source graph.
o Prove that the functor List : SET -> SET preserves identity and
composite arrows, using structural induction on lists.
o Define an alternative functor Tree : SET -> SET that stores values
in the nodes of a tree rather than in the leaves.
o Prove that if C and D are categories then so is CxD.
o Show that a bifunctor + : CxD -> E is precisely a functor
+ : CxD -> E on the product category CxD.
----------------------------------------------------------------------
Exercises for lecture 3:
o Show how the identity and associativity equations required of a
category can be expressed as simple commuting diagrams.
o Show that the diagram
A -- g -> C -- j -> E
| | |
| | |
f i l
| | |
v v v
B -- h -> D -- k -> F
commutes if and only if the two component squares commute.
Note: don't forget about the external rectangle!
o Prove that fla : Tree -> List and len : List -> Int are natural.
o Suppose that and ** are pre-ordered sets
viewed as categories C and D, and that F,G : C -> D are
functors, i.e. monotonic functions.
What is a natural transformation alpha : F -> G ?
o Suppose that and **** are monoids viewed as
categories C and D, and that F,G : C -> D are functors,
i.e. monoid homomorphisms.
What is a natural transformation alpha : F -> G ?
o Prove that alpha_F : GF -> HF is natural.
o Prove equations (1)-(5) from the Godement calculus.
o Explain, with the aid of examples, how the composition of natural
transformations with functors, and also the horizontal composition
of functors, can be interpreted in programming language terms.
----------------------------------------------------------------------
Exercises for lecture 4:
o What are the isomorphisms in the category REL, and in categories
derived from pre-ordered sets and monoids?
o If arrows of type 1 -> A are viewed as the "elements" of an object
A, what is the appropriate notion of "application" ?
o Show that a monoid interpreted as a category has an initial or
terminal object precisely when the monoid is trivial.
o What is a terminal object for a pre-ordered set?
o Prove equations (6)-(9) about products.
o Prove equations (1)-(9) about co-products.
o The categorical notion of an "exponential" generalises the notion
of a "function". Following the pattern established by products and
co-products, complete the following definition: an exponential of
two objects A and B in a category with products is a pair
B, apply>
where
A=>B is an "exponential" object;
apply : (A=>B)xA -> B is an "application" arrow
such that ....
----------------------------------------------------------------------
**