In mathematics, a category (sometimes called an abstract category to distinguish it from a concrete category) is a collection of "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose objects are sets and whose arrows are functions.
Category theory is a branch of mathematics that seeks to generalize all of mathematics in terms of categories, independent of what their objects and arrows represent. Virtually every branch of modern mathematics can be described in terms of categories, and doing so often reveals deep insights and similarities between seemingly different areas of mathematics. As such, category theory provides an alternative foundation for mathematics to set theory and other proposed axiomatic foundations. In general, the objects and arrows may be abstract entities of any kind, and the notion of category provides a fundamental and abstract way to describe mathematical entities and their relationships.
In addition to formalizing mathematics, category theory is also used to formalize many other systems in computer science, such as the semantics of programming languages.
Two categories are the same if they have the same collection of objects, the same collection of arrows, and the same associative method of composing any pair of arrows. Two different categories may also be considered "equivalent" for purposes of category theory, even if they do not have precisely the same structure. A mapping between two categories compatible with their respective structures is called a functor.
Well-known categories are denoted by a short capitalized word or abbreviation in bold or italics: examples include Set, the category of sets and set functions; Ring, the category of rings and ring homomorphisms; and Top, the category of topological spaces and continuous maps. All of the preceding categories have the identity map as identity arrows and composition as the associative operation on arrows. Any monoid can be understood as a special sort of category (with a single object whose self-morphisms are represented by the elements of the monoid), and so can any preorder.
The classic and still much used text on category theory is Categories for the Working Mathematician by Saunders Mac Lane. Other references are given in the References below. The basic definitions in this article are contained within the first few chapters of any of these books.
There are many equivalent definitions of a category. One commonly used definition is as follows. A category
l{C}
\operatorname{ob}(l{C})
\operatorname{mor}(l{C})
\operatorname{dom}:\operatorname{mor}(l{C})\to\operatorname{ob}(l{C})
\operatorname{cod}:\operatorname{mor}(l{C})\to\operatorname{ob}(l{C})
a,b,c
\operatorname{hom}(a,b) x \operatorname{hom}(b,c)\to\operatorname{hom}(a,c)
\operatorname{hom}(a,b)
f
\operatorname{mor}(l{C})
\operatorname{dom}(f)=a
\operatorname{cod}(f)=b
f:a\tob
f:a\tob
g:b\toc
g\circf
gf
f:a\tob
g:b\toc
h:c\tod
h\circ(g\circf)=(h\circg)\circf
x
1x:x\tox
\operatorname{id}x
x
f:a\tox
1x\circf=f
g:x\tob
g\circ1x=g
We write
f:a\tob
f
a
b
\operatorname{hom}(a,b)
\operatorname{hom}l{C
\operatorname{hom}(a,b)
a
b
Some authors write the composite of morphisms in "diagrammatic order", writing
f;g
fg
g\circf
From these axioms, one can prove that there is exactly one identity morphism for every object. Often the map assigning each object its identity morphism is treated as an extra part of the structure of a category, namely a class function
i:\operatorname{ob}(l{C})\to\operatorname{mor}(l{C})
Some authors use a slight variant of the definition in which each object is identified with the corresponding identity morphism. This stems from the idea that the fundamental data of categories are morphisms and not objects. In fact, categories can be defined without reference to objects at all using a partial binary operation with additional properties.
A category
l{C}
\operatorname{ob}(l{C})
\operatorname{mor}(l{C})
a
b
\operatorname{hom}(a,b)
The class of all sets (as objects) together with all functions between them (as morphisms), where the composition of morphisms is the usual function composition, forms a large category, Set. It is the most basic and the most commonly used category in mathematics. The category Rel consists of all sets (as objects) with binary relations between them (as morphisms). Abstracting from relations instead of functions yields allegories, a special class of categories.
I
I
(P,\leq)
P
x
y
x\leqy
\leq
Any monoid (any algebraic structure with a single associative binary operation and an identity element) forms a small category with a single object
x
x
x
x
x
Similarly any group can be seen as a category with a single object in which every morphism is invertible, that is, for every morphism
f
g
f
A groupoid is a category in which every morphism is an isomorphism. Groupoids are generalizations of groups, group actions and equivalence relations. From the point of view of category theory, a group is just a groupoid with exactly one object. Consider a topological space
X
x0
X
\pi1(X,x0)
X
x0
x0
X
\pi1(X,x0)
X
Any directed graph (or, more generally, a quiver) generates a small category: the objects are the vertices of the graph, and the morphisms are the paths in the graph (augmented with loops as needed) where composition of morphisms is concatenation of paths. Such a category is called the free category generated by the graph.
The class of all preordered sets with order-preserving functions (i.e., monotone-increasing functions) as morphisms forms a category, Ord. It is a concrete category, i.e. a category whose objects can be identified with sets with some type of additional structure, while the morphisms are functions that respect this structure.
The class of all groups with group homomorphisms as morphisms and function composition as the composition operation forms a large category, Grp. Like
Ord
Grp
Grp
The class of all graphs forms another concrete category, where morphisms are graph homomorphisms (i.e., mappings between graphs which send vertices to vertices and edges to edges in a way that preserves all adjacency and incidence relations).
Examples of concrete categories are given by the following table.
| Category | Objects | Morphisms | |
|---|---|---|---|
| Set | sets | functions | |
| Ord | preordered sets | monotone-increasing functions | |
| Mon | monoids | monoid homomorphisms | |
| Grp | groups | group homomorphisms | |
| Grph | graphs | graph homomorphisms | |
| Ring | rings | ring homomorphisms | |
| Field | fields | field homomorphisms | |
| R-Mod | R-modules, where R | R-module homomorphisms | |
| VectK | vector spaces over the field K | K-linear maps | |
| RepK(G) | representations of a group G over a field K | equivariant maps | |
| Met | metric spaces | short maps | |
| Meas | measure spaces | measurable functions | |
| Stoch | measure spaces | Markov kernels | |
| Top | topological spaces | continuous functions | |
| Manp | smooth manifolds | p | |
| Sch | schemes | morphisms of schemes |
Fiber bundles with bundle maps between them form a concrete category.
The category Cat consists of all small categories, with functors between them as morphisms. In turn, a functor category has as objects functors between two fixed categories and as morphisms natural transformations between them.
Any category
l{C}
l{C}op
If
l{C}
l{D}
l{C} x l{D}
l{C}
l{D}
l{C}
l{D}
By identifying a collection of morphisms in
lC
\sim
lC/\sim
For a fixed object
X
lC
lC/X
(A,f)
A
lC
f:A\toX
(A,f)
(A',f')
g:A\toB
lC
X
f'\circg=f
Given a class
W
lC
lC[W-1]
W
f:a\tob
fg1=fg2
g1=g2
g1,g2:x\toa
g1f=g2f
g1=g2
g1,g2:b\tox
g:b\toa
fg=1b
g:b\toa
gf=1a
g:b\toa
fg=1b
gf=1a
a=b
a
end(a)
end(a)
f
a
aut(a)
a
Every retraction is an epimorphism. Every section is a monomorphism. The following three statements are equivalent:
f
f
f
Relations among morphisms (such as
fg=h
\operatorname{hom}(a,b)
CPO
