Michael Barr Department of Mathematics and Statistics McGill University Charles Wells Department of Mathematics Case Western Reserve University

c Michael Barr and Charles Wells, 1999

Contents Preface 1 Preliminaries 1.1 Graphs 1.2 Homomorphisms of graphs

iv 1 1 2

2 Categories 2.1 Basic deﬁnitions 2.2 Functional programming languages as categories 2.3 Mathematical structures as categories 2.4 Categories of sets with structure 2.5 Categories of algebraic structures 2.6 Constructions on categories

4 4 6 8 10 11 13

3 Properties of objects and arrows 3.1 Isomorphisms 3.2 Terminal and initial objects 3.3 Monomorphisms and subobjects 3.4 Other types of arrow

17 17 18 19 22

4 Functors 4.1 Functors 4.2 Actions 4.3 Types of functors 4.4 Equivalences

26 26 30 32 34

5 Diagrams and naturality 5.1 Diagrams 5.2 Natural transformations 5.3 Natural transformations between functors 5.4 Natural transformations involving lists 5.5 Natural transformations of graphs 5.6 Combining natural transformations and functors 5.7 The Yoneda Lemma and universal elements

37 37 42 46 47 48 49 50

6 Products and sums 6.1 The product of two objects in a category 6.2 Notation for and properties of products 6.3 Finite products 6.4 Sums 6.5 Deduction systems as categories

55 55 57 64 69 71

7 Cartesian closed categories 7.1 Cartesian closed categories 7.2 Properties of cartesian closed categories 7.3 Typed λ-calculus 7.4 λ-calculus to category and back

73 73 77 79 80

iii

iv

Contents

8 Limits and colimits 8.1 Equalizers 8.2 The general concept of limit 8.3 Pullbacks 8.4 Coequalizers 8.5 Cocones

82 82 83 86 88 89

9 Adjoints 9.1 Free monoids 9.2 Adjoints 9.3 Further topics on adjoints

92 92 94 97

10 Triples 10.1 Triples 10.2 Factorizations of a triple

99 99 100

11 Toposes 11.1 Deﬁnition of topos 11.2 Properties of toposes 11.3 Presheaves 11.4 Sheaves

102 102 104 106 107

12 Categories with monoidal structure 12.1 Closed monoidal categories 12.2 Properties of A −◦ C 12.3 ∗-autonomous categories 12.4 Factorization systems 12.5 The Chu construction

111 111 114 115 116 117

Bibliography

119

Index

123

Preface About these notes These notes form a short summary of some major topics in category theory. They are a condensation (with some rearrangement) of part of [Barr and Wells, 1999]. The chapter and section numbers in the notes are not the same as those in the book.

About categories Categories originally arose in mathematics out of the need of a formalism to describe the passage from one type of mathematical structure to another. A category in this way represents a kind of mathematics, and may be described as category as mathematical workspace. A category is also a mathematical structure. As such, it is a common generalization of both ordered sets and monoids (the latter are a simple type of algebraic structure that include transition systems as examples), and questions motivated by those topics often have interesting answers for categories. This is category as mathematical structure. Finally, a category can be seen as a structure that formalizes a mathematician’s description of a type of structure. This is the role of category as theory. Formal descriptions in mathematical logic are traditionally given as formal languages with rules for forming terms, axioms and equations. Algebraists long ago invented a formalism based on tuples, the method of signatures and equations, to describe algebraic structures. Category theory provides another approach: the category is a theory and functors with that category as domain are models of the theory.

Other categorical literature All of