Module CS4002: Category theory

Credit weighting (ECTS)
5 credits
Semester/term taught
Hilary term 2013-14
Contact Hours
11 weeks, 3 lectures including tutorials per week
Lecturer
Prof. Arthur Hughes (Computer Science)
Learning Outcomes

On successful completion of this module, students will be able to explain why:

• Many objects of interest in mathematics congregate in concrete categories.
• Many objects of interest to mathematicians are themselves small categories.
• Many objects of interest to mathematicians may be viewed as functors from small categories to the category of Sets.
• Many important concepts in mathematics arise as adjoints, right or left, to previously known functors.
• Many equivalence and duality theorems in mathematics arise as an equivalence of fixed subcategories induced by a pair of adjoint functors.
• Many categories of interest are the Eilenberg-Moore or Kleisli categories of monads on familiar categories2
• Many data types of interest to computing science are algebras for endofunctors.
• Many process of interest to computing science are coalgebras for endofunctors.
Module Content

What is category theory? As a first approximation, one could say that category theory is the mathematical study of (abstract) algebras of functions. Just as group theory is the abstraction of the idea of a system of permutations of a set or symmetries of a geometric object, category theory arises from the idea of a system of functions among some objects.

We think of the composition g â°¦ f (f ; g often used in CS) as a sort of âproduct'' of the functions f and g, and consider abstract âalgebras'' of the sort arising from collections of functions. A category is just such an âalgebra'', consisting of objects A, B, C, ¼ and arrows f \colon A â® B, g \colon B â® C, ..., that are closed under composition and satisfy certain conditions typical of the composition of functions1.

• Categories - functions of sets, definition of a category, examples of categories, isomorphisms, constructions on categories, free categories, foundations: large, small, and locally small.
• Abstract structures - epis and monos, initial and terminal objects, generalized elements, sections and retractions, products, examples of products, categories with products, Hom-sets.
• Duality - the duality principle, coproducts, equalizers, coequalizers.
• Groups and categories - groups in a category, the category of groups, groups as categories, finitely presented categories.
• Limits and colimits - subobjects, pullbacks, properties of pullbacks, limits, preservation of limits, colimits.
• Exponentials - exponential in a category, cartesian closed categories, Heyting algebras, equational definition, l-calculus.
• Functors and naturality - category of categories, representable structure, stone duality, naturality, examples of natural transformations, exponentials of categories, functor categories, equivalence of categories, examples of equivalence.
• Categories of diagrams - Set-valued functor categories, the Yoneda embedding, the Yoneda Lemma, applications of the Yoneda Lemma, Limits in categories of diagrams, colimits in categories of diagrams, exponentials in categories of diagrams, Topoi.