Lectures & course notes for part 1

Lectures are 2 hours long, on Mondays at 8:00 and Thursdays at 13:30, room B1. Each past lecture has PDF notes and a short summary below; the notes may contain bibliographic references of cultural interest, not necessary to pass the course.

Lecture 1 (12 September): Motivation for category theory: semantics of programming languages requires an axiomatic theory of "composable stuff" that goes beyond "structured sets and structure-preserving maps"; mathematicians came up with their own to do algebra and topology, we reuse it. Reminders on monoids, homomorphisms and isomorphisms. An example of categorical thinking (with commutative diagrams): proof that the free monoid over a set X is characterized up to isomorphism by its universal property. Definition of a category; examples: Set, Mon, Rel.

Lecture 2 (16 September): Reminders on partial orders, preorders, monotone functions; left-divisibility preorder in a monoid. The categories PreOrd and Ord. Size issues: small and locally small categories. Examples of small categories: path category on a graph; categories representing preordered sets (|C(A,B)| ≤ 1) and monoids (1 object). Isomorphisms in arbitrary categories, for instance PreOrd (not all monotone bijections are isos!). Functors preserve commutative diagrams and isomorphisms.

Homework 1: due on 23 September.

Lecture 3 (19 September): Examples of functors: forgetful functors; free monoid functor Set → Mon; parameterised data structures (lists, option type, pairs) as endofunctors on Set. Functors generalise monoid homomorphisms and monotone functions. Composition of functors. Universal morphisms from an object to a functor or vice versa; rephrasing of the universal property of the free monoid. Duality: opposite category; contravariant functors. Covariant and contravariant hom-functors. Product of two categories; hom-bifunctor C(–,–).

Lecture 4 (23 September): Example of the contravariant powerset functor. Bifunctors: examples (pairs, sum type) and partial application. Cartesian products as universal morphisms from a diagonal functor. Examples in Set, Mon, PreOrd: usual product of sets. In Rel: disjoint sum of two sets / dependent sum of a family. Products generalise infima in preordered sets. Nullary case: terminal objects. Dual concept: coproducts, e.g. sums in Set.

Homework 2: due on 30 September.

Lecture 5 (26 September): Examples of coproducts: in Mon they exist but are complicated, but the case of free monoids is simple. Initial objects: mostly the empty set (it has a unique "empty function" out of it); singletons in Mon. Universal morphisms as initial objects in a comma category. Uniqueness up to unique isomorphism: for initial/terminal objects, for universal morphisms, for (co)products. Cartesian categories: defined using chosen binary products. Associativity, commutativity and unitality up to iso of the product. Cartesian categories admit all finite products.

Lecture 6 (30 September): Bifunctoriality of the binary product in a cartesian category. Natural transformations; examples: projections in a cartesian category, polymorphic functions on data structures as endofunctors on Set. Operations on natural transformations: vertical composition; whiskering by a functor; horizontal composition (two definitions coincide). Interchange law between vertical and horizontal compositions. Categories of functors and natural isomorphisms (the componentwise inverse is automatically natural).

Homework 3: due on 7 October.

Lecture 7 (3 October): Representable functors (in locally small categories), e.g. contravariant powerset, forgetful Mon→Set (using ℕ). Bijective correspondence between universal morphisms from X to F : C → D and representations of D(X,F(–)). A global choice for each X of a universal morphism from X to F (resp. F to X) corresponds to the unit (resp. counit) of a left adjoint (resp. right adjoint) to F. Adjoint functors in terms of natural bijections: L is left adjoint to R if and only if R is right adjoint to L.

Lecture 8 (7 October): Examples of adjunctions: previous examples of universal morphisms; the forgetful functor PreOrd→Set has adjoints on both sides; product/hom adjunction in Set, from a natural bijection to a universal property. The triangle identities uniquely determine the counit from the unit and vice versa, and provide an equivalent definition of adjunctions. Uniqueness of adjoint functors up to natural isomorphism. Composition of adjunctions. Right (resp. left) adjoints preserve products (resp. coproducts): examples (such as distributivity of × over + in Set); the forgetful Mon→Set has no right adjoint.

Homework 4: due on 14 October.

Lecture 9 (10 October): Proof that right adjoints preserve products. From adjunctions to monads. Examples over Set: List (from free/forgetful), State (from product/function). Interpretation as effectful computations (nondeterminism, mutable state) using the "bind" operator >>=. Extension to arbitrary categories: Kleisli composition. Monads over C as internal monoids in [C,C]. Every monad induced by an adjunction is an internal monoid; conversely, every internal monoid is the monad induced by a canonical adjunction with its Kleisli category.

Lecture 10 (14 October): Example of the Option monad. Initiality of the Kleisli category. Comonads (for instance (–&A)) are dual to monads. Isomorphisms of categories (Kleisli over Option vs partial functions; self-duality of Rel). Equivalences of categories are more common, and compose; they account for monoids being "the same as" one-object categories, and preordered sets "the same as" thin categories. Characterisation by full, faithful and essentially surjective functors. Adjunctions from equivalences (admitted), hence preservation of (co)products. Final brief remarks on Yoneda, presheaves and (co)limits.