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