,Contents
2 The Category of Sets 5
2.1 Sets and functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Commutative diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Ologs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.3 Facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Fundamental Considerations in Set 23
3.1 Products and coproducts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.2 Coproducts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Finite limits in Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Pullbacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2 Spans, experiments, and matrices . . . . . . . . . . . . . . . . . . . 37
3.2.3 Equalizers and terminal objects . . . . . . . . . . . . . . . . . . . . 39
3.3 Finite colimits in Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1 Background: equivalence relations . . . . . . . . . . . . . . . . . . 40
3.3.2 Pushouts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3.3 Other finite colimits . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4 Other notions in Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4.1 Retractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4.2 Currying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4.3 Arithmetic of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.4 Subobjects and characteristic functions . . . . . . . . . . . . . . . 53
3.4.5 Surjections, injections . . . . . . . . . . . . . . . . . . . . . . . . . 55
1
,2 CONTENTS
3.4.6 Multisets, relative sets, and set-indexed sets . . . . . . . . . . . . . 57
4 Categories and Functors, Without Admitting It 59
4.1 Monoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1.1 Definition and examples . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1.2 Monoid actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.1.3 Monoid action tables . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.1.4 Monoid homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2.1 Definition and examples . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.1 Definition and examples . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.2 Paths in a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.3.3 Graph homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . 83
4.4 Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.1 Definitions of preorder, partial order, linear order . . . . . . . . . . 84
4.4.2 Meets and joins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.4.3 Opposite order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.4.4 Morphism of orders . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.4.5 Other applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.5 Databases: schemas and instances . . . . . . . . . . . . . . . . . . . . . . 96
4.5.1 What are databases? . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.5.2 Schemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.5.3 Instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5 Basic Category Theory 103
5.1 Categories and functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.1.1 Categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.1.2 Functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.2 Common categories and functors from pure math . . . . . . . . . . . . . . 117
5.2.1 Monoids, groups, preorders, and graphs . . . . . . . . . . . . . . . 117
5.2.2 Database schemas present categories . . . . . . . . . . . . . . . . . 123
5.2.3 Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.4 Logic, set theory, and computer science . . . . . . . . . . . . . . . 129
5.2.5 Categories applied in science . . . . . . . . . . . . . . . . . . . . . 129
5.3 Natural transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.3.1 Definition and examples . . . . . . . . . . . . . . . . . . . . . . . . 130
5.3.2 Vertical and horizontal composition . . . . . . . . . . . . . . . . . 135
5.3.3 The category of instances on a database schema . . . . . . . . . . 138
5.3.4 Equivalence of categories . . . . . . . . . . . . . . . . . . . . . . . 140
, CONTENTS 3
5.4 Categories and schemas are equivalent, Cat » Sch . . . . . . . . . . . . . 143
5.4.1 The category Sch of schemas . . . . . . . . . . . . . . . . . . . . . 143
5.4.2 Proving the equivalence . . . . . . . . . . . . . . . . . . . . . . . . 145
6 Fundamental Considerations of Categories 149
6.1 Limits and colimits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.1.1 Products and coproducts in a category . . . . . . . . . . . . . . . . 149
6.1.2 Diagrams in a category . . . . . . . . . . . . . . . . . . . . . . . . 152
6.1.3 Limits and colimits in a category . . . . . . . . . . . . . . . . . . . 153
6.2 Other notions in Cat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
6.2.1 Opposite categories . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
6.2.2 Grothendieck construction . . . . . . . . . . . . . . . . . . . . . . . 160
6.2.3 Full subcategory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.2.4 Comma categories . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
6.2.5 Arithmetic of categories . . . . . . . . . . . . . . . . . . . . . . . . 165
7 Categories at Work 167
7.1 Adjoint functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
7.1.1 Discussion and definition . . . . . . . . . . . . . . . . . . . . . . . 167
7.1.2 Universal concepts in terms of adjoints . . . . . . . . . . . . . . . . 170
7.1.3 Preservation of colimits or limits . . . . . . . . . . . . . . . . . . . 172
7.1.4 Data migration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
7.2 Categories of functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
7.2.1 Set-valued functors . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
7.2.2 Database instances in other categories . . . . . . . . . . . . . . . . 176
7.2.3 Sheaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
7.3 Monads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.3.1 Monads formalize context . . . . . . . . . . . . . . . . . . . . . . . 178
7.3.2 Definition and examples . . . . . . . . . . . . . . . . . . . . . . . . 178
7.3.3 Kleisli category of a monad . . . . . . . . . . . . . . . . . . . . . . 181
7.3.4 Monads in databases . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7.3.5 Monads and adjunctions . . . . . . . . . . . . . . . . . . . . . . . . 182
7.4 Operads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.4.1 Definition and classical examples . . . . . . . . . . . . . . . . . . . 183
7.4.2 Applications of operads and their algebras . . . . . . . . . . . . . . 185
2 The Category of Sets 5
2.1 Sets and functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Commutative diagrams . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Ologs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.1 Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.3.2 Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3.3 Facts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3 Fundamental Considerations in Set 23
3.1 Products and coproducts . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.1 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1.2 Coproducts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Finite limits in Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.1 Pullbacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.2 Spans, experiments, and matrices . . . . . . . . . . . . . . . . . . . 37
3.2.3 Equalizers and terminal objects . . . . . . . . . . . . . . . . . . . . 39
3.3 Finite colimits in Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.1 Background: equivalence relations . . . . . . . . . . . . . . . . . . 40
3.3.2 Pushouts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3.3 Other finite colimits . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4 Other notions in Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4.1 Retractions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4.2 Currying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4.3 Arithmetic of sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.4.4 Subobjects and characteristic functions . . . . . . . . . . . . . . . 53
3.4.5 Surjections, injections . . . . . . . . . . . . . . . . . . . . . . . . . 55
1
,2 CONTENTS
3.4.6 Multisets, relative sets, and set-indexed sets . . . . . . . . . . . . . 57
4 Categories and Functors, Without Admitting It 59
4.1 Monoids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1.1 Definition and examples . . . . . . . . . . . . . . . . . . . . . . . . 59
4.1.2 Monoid actions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
4.1.3 Monoid action tables . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.1.4 Monoid homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . 70
4.2 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2.1 Definition and examples . . . . . . . . . . . . . . . . . . . . . . . . 72
4.3 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.1 Definition and examples . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.2 Paths in a graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
4.3.3 Graph homomorphisms . . . . . . . . . . . . . . . . . . . . . . . . 83
4.4 Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
4.4.1 Definitions of preorder, partial order, linear order . . . . . . . . . . 84
4.4.2 Meets and joins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.4.3 Opposite order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.4.4 Morphism of orders . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.4.5 Other applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
4.5 Databases: schemas and instances . . . . . . . . . . . . . . . . . . . . . . 96
4.5.1 What are databases? . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.5.2 Schemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.5.3 Instances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
5 Basic Category Theory 103
5.1 Categories and functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.1.1 Categories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.1.2 Functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
5.2 Common categories and functors from pure math . . . . . . . . . . . . . . 117
5.2.1 Monoids, groups, preorders, and graphs . . . . . . . . . . . . . . . 117
5.2.2 Database schemas present categories . . . . . . . . . . . . . . . . . 123
5.2.3 Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
5.2.4 Logic, set theory, and computer science . . . . . . . . . . . . . . . 129
5.2.5 Categories applied in science . . . . . . . . . . . . . . . . . . . . . 129
5.3 Natural transformations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130
5.3.1 Definition and examples . . . . . . . . . . . . . . . . . . . . . . . . 130
5.3.2 Vertical and horizontal composition . . . . . . . . . . . . . . . . . 135
5.3.3 The category of instances on a database schema . . . . . . . . . . 138
5.3.4 Equivalence of categories . . . . . . . . . . . . . . . . . . . . . . . 140
, CONTENTS 3
5.4 Categories and schemas are equivalent, Cat » Sch . . . . . . . . . . . . . 143
5.4.1 The category Sch of schemas . . . . . . . . . . . . . . . . . . . . . 143
5.4.2 Proving the equivalence . . . . . . . . . . . . . . . . . . . . . . . . 145
6 Fundamental Considerations of Categories 149
6.1 Limits and colimits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
6.1.1 Products and coproducts in a category . . . . . . . . . . . . . . . . 149
6.1.2 Diagrams in a category . . . . . . . . . . . . . . . . . . . . . . . . 152
6.1.3 Limits and colimits in a category . . . . . . . . . . . . . . . . . . . 153
6.2 Other notions in Cat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
6.2.1 Opposite categories . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
6.2.2 Grothendieck construction . . . . . . . . . . . . . . . . . . . . . . . 160
6.2.3 Full subcategory . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.2.4 Comma categories . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
6.2.5 Arithmetic of categories . . . . . . . . . . . . . . . . . . . . . . . . 165
7 Categories at Work 167
7.1 Adjoint functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167
7.1.1 Discussion and definition . . . . . . . . . . . . . . . . . . . . . . . 167
7.1.2 Universal concepts in terms of adjoints . . . . . . . . . . . . . . . . 170
7.1.3 Preservation of colimits or limits . . . . . . . . . . . . . . . . . . . 172
7.1.4 Data migration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173
7.2 Categories of functors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
7.2.1 Set-valued functors . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
7.2.2 Database instances in other categories . . . . . . . . . . . . . . . . 176
7.2.3 Sheaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
7.3 Monads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
7.3.1 Monads formalize context . . . . . . . . . . . . . . . . . . . . . . . 178
7.3.2 Definition and examples . . . . . . . . . . . . . . . . . . . . . . . . 178
7.3.3 Kleisli category of a monad . . . . . . . . . . . . . . . . . . . . . . 181
7.3.4 Monads in databases . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7.3.5 Monads and adjunctions . . . . . . . . . . . . . . . . . . . . . . . . 182
7.4 Operads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
7.4.1 Definition and classical examples . . . . . . . . . . . . . . . . . . . 183
7.4.2 Applications of operads and their algebras . . . . . . . . . . . . . . 185
