This page is about the concept in mathematics. For the concept of the same name in philosophy see at category (philosophy).
A category consists of a collection of things and binary relationships (or transitions) between them, such that these relationships can be combined and include the “identity” relationship “is the same as.”
A category is a quiver (a directed graph with multiple edges) with a rule saying how to compose two edges that fit together to get a new edge. Furthermore, each vertex has an edge starting and ending at that vertex, which acts as an identity for this composition.
A category is a combinatorial model for a directed space – a “directed homotopy 1-type” in some sense. It has “points”, called objects, and also directed “paths”, or “processes” connecting these points, called morphisms. There is a rule for how to compose paths; and for each object there is an identity path that starts and ends there.
More precisely, a category consists of a collections of objects and a collection of morphisms. Every morphism has a source object and a target object. If $f$ is a morphism with $x$ as its source and $y$ as its target, we write
and we say that $f$ is a morphism from $x$ to $y$. In a category, we can compose a morphism $g : x \to y$ and a morphism $f : y \to z$ to get a morphism $f \circ g : x \to z$. Composition is associative and satisfies the left and right unit laws.
A good example to keep in mind is the category Set, in which the objects are sets and a morphism $f : x \to y$ is a function from the set $x$ to the set $y$. Here composition is the usual composition of functions.
For more background on and context for categories see
There are two broad ways to write down the definition of category; in the usual foundations of mathematics, these two definitions are equivalent. It is good to know both, for several reasons:
The two definitions may be distinguished by whether they use a single collection of all morphisms or several collections of morphisms, a family of collections indexed by pairs of objects.
A category $C$ consists of
a collection (see Size issues) $C_0$ of objects;
a collection $C_1$ of morphisms (or arrows);
two functions $s, t\colon C_1 \to C_0$ which assign, to every morphism, its source (or domain) and target (or codomain);
a partial function $\circ\colon C_1 \times C_1 \to C_1$ which assigns, to any pair of morphisms $f, g$ such that $t(f) = s(g)$, their composite morphism $g \circ f \in C_1$ (also written $g f$ or sometimes $f;g$— see diagrammatic order);
a function $id\colon C_0 \to C_1$ which assigns to each object $x$ a morphism $id_x$ or $1_x$, the identity morphism on $x$;
such that the following properties are satisfied:
source and target are respected by composition: $s(g \circ f) = s(f)$ and $t(g\circ f) = t(g)$;
source and target are respected by identities: $s(1_x) = x$ and $t(1_x) = x$;
composition is associative: $(h \circ g)\circ f = h\circ (g \circ f)$ whenever $t(f) = s(g)$ and $t(g) = s(h)$;
composition satisfies the left and right unit laws: if $s(f) = x$ and $t(f) = y$, then $1_y \circ f = f = f \circ 1_x$.
People also often write $x \in C$ instead of $x \in C_0$ as a short way to indicate that $x$ is an object of $C$. Also, some people write $Ob(C)$ and $Mor(C)$ instead of $C_0$ and $C_1$. One usually writes $f\colon x \to y$ if $f \in C_1$ to state that $s(f) = x$ and $t(f) = y$. Finally, people often write $hom(x,y)$, $hom_C(x,y)$, or $C(x,y)$ for the collection of morphisms $f\colon x \to y$.
If the identity-assigning map and its axiom is omitted, then one speaks of a semicategory.
A category $C$ consists of
a collection (see Size issues) $C_0$ of objects;
for each pair $x,y$ of objects, a collection $C_1(x,y)$ of morphisms from $x$ to $y$;
for each triple $x,y,z$ of objects, a function $\circ\colon C_1(y,z) \times C_1(x,y) \to C_1(x,z)$ which assigns, to any appropriate pair of morphisms $f, g$, their composite morphism $g \circ f$ (also written $g f$ or sometimes $f;g$— see diagrammatic order);
for each object $x$, an element $id_x$ or $1_x$ of $C_1(x,x)$, the identity morphism on $x$;
such that the following properties are satisfied:
composition is associative: for each quadruple $w,x,y,z$ of objects, if $f \in C_1(y,z)$, $g \in C_1(x,y)$, and $h \in C_1(w,x)$, then $(f \circ g)\circ h = f\circ (g \circ h)$;
composition satisfies the left and right unit laws: for each pair $x,y$ of objects, if $f \in C_1(x,y)$, then $1_y \circ f = f = f \circ 1_x$.
People also often write $x \in C$ instead of $x \in C_0$ as a short way to indicate that $x$ is an object of $C$. Also, some people write $Ob(C)$ instead of $C_0$ and $hom(x,y)$, $hom_C(x,y)$, or $C(x,y)$ instead of $C_1(x,y)$. One usually writes $f\colon x \to y$ to state that $f \in C_1(x,y)$. Finally, people often write $C_1$ or $Mor(C)$ for the disjoint union $\biguplus_{x \in C_0} \biguplus_{y \in C_0} C_1(x,y)$.
We said a category has a ‘collection’ of objects and ‘collection’(s) of morphisms. A category is said to be small if these collections are all sets — as opposed to proper classes, for example. (The alternatives depend on ones foundations for mathematics.)
Similarly, a category is locally small if $C_1(x,y)$ is a set for every pair of objects $x,y$ in that category. The most common motivating examples of categories (such as Set) are all locally small but not small (unless one restricts their objects in some way).
For some purposes it is useful or necessary to vary the way the ordinary definition of category is expressed. See
single-sorted definition of a category – a variant of the first definition, with only one collection at all ($C_1$, no $C_0$). This is sometimes convenient for technical reasons.
type-theoretic definition of category – a variant of the second definition, interpreted explicitly in dependent type theory.
protocategory – a sort of mixture of the two definitions, in which all the hom-sets $C_1(x,y)$ are subsets of a single set $C_1$, but not necessarily disjoint.
A category is equivalently
a monad in the 2-category of spans of sets;
a monoid in the monoidal category of endospans on the set of objects;
a simplicial set which satisfies the Segal conditions;
a simplicial set which satisfies the weak Kan complex conditions strictly:
hence a directed homotopy type which is “1-truncated”;
The first definition, with a single collection $C_1$ of morphisms, generalises to the notion of internal category. Essentially, we define a category internal to (some other category) $D$ as above, with ‘collection’ interpreted as an object of $D$ and ‘function’ interpreted as a morphism of $D$. In particular, a category internal to Set is the same thing as a small category.
The second definition of a category, as a family $C_1(x,y)$ of collections of morphisms, generalises to the notion of enriched category: we define a category enriched over (some other category) $D$ as above, with the collection of objects still a ‘collection’ as before, but with objects of $D$ in place of the collections of morphisms and morphisms of $D$ in place of the various functions. In particular, a category enriched over Set is the same thing as a locally small category.
The notion of indexed category captures the idea of woking “over a base” other than Set.
There is a generalization of the notion of catgeory where one allows a morphism to go from several objects to a single object. This is called a multicategory or operad. If we additionally allow a morphism to go to several objects, we obtain a polycategory or PROP.
There is the beginning of a database of categories listing well-known categories (with links to articles on these categories, if such articles exist) and some of their properties.
The classic example of a category is Set, the category with sets as objects and functions as morphisms, and the usual composition of functions as composition. Here are some other famous examples, which arise as variations on this theme:
Vect - vector spaces as objects, linear maps as morphisms.
Top - topological spaces as objects, continuous functions as morphisms.
Diff - smooth manifolds as objects, smooth maps as morphisms.
Note that in all these cases the morphisms are actually special sorts of functions. these are concrete categories. That need not be the case in general!
These classic examples are the original motivation for the term “category”: all of the above categories encapsulate one “kind of mathematical structure”. These are often called “concrete” categories (that term also has a technical definition that these examples all satisfy). But just as widespread in applications as these categorization examples of categories are are other categories (often “small” ones) which, roughly, model something like states and processes of some system.
Poset A poset can be thought of as a category with its elements as objects and one morphism in each $hom(x,y)$ if $x$ is less than or equal to $y$, but none otherwise.
Group A group is just a category where there’s one object and all the morphisms have inverses - we call the morphisms “elements” of the group. This may seem weird, but it’s actually a very useful viewpoint. Here’s another way to say it: A group is a groupoid with a single object.
Monoid More generally, a monoid is a category with a single object. In fact, this is one way to motivate the concept of categories: categories are the many object version of monoids.
Groupoid A groupoid is a category in which all morphisms are isomorphisms.
Quiver A quiver may be identified with the free category on its directed graph. Given a directed graph $G$ with collection of vertices $G_0$ and collection of edges $G_1$, there is the free category $F(G)$ on the graph whose collection of objects coincides with the collection of vertices, and whose collection of morphisms consists of finite sequences of edges in $G_1$ that fit together head-to-tail. The composition operation in this free category is the concatenation of sequences of edges.
Universal structure A category bearing a structure making it initial (or 2-initial) in some doctrine. Examples include the permutation category as the free symmetric monoidal category generated by a single object, or the simplex category which is initial among monoidal categories equipped with a monoid.
A homomorphism between categories is a functor.
This way small categories themselves form a category, the category Cat whose objects are small categories and whose morphisms are functors. This naturally enhances to a 2-category whose 2-morphisms are natural transformations between functors.
An equivalence of categories is an equivalence in Cat, hence a pair of functors going back and forth, that are each others inverse up to natural isomorphism.
Weaker than the notion of a pair of functors exhibiting an equivalence is the notion of a pair of adjoint functors.
Other standard operations on categories include
category
(See also the references at category theory.)
The concept originates in
The standard textbook is
Expositions include
Jaap van Oosten, Basic category theory.
Andrea Schalk and H. Simmons, An introduction to category theory in four easy movements, notes for a course offered as part of the MSc. in Mathematical Logic, Manchester University.
Daniele Turim, Category theory lecture notes, 1996-2001. Based on Mac Lane’s book (1998).
A. Martini, H. Ehrig, and D. Nunes, Elements of basic category theory, Technical Report 96-5, Technical University Berlin.
A textbook that introduces categories by examples arising in mathematical physics is
A textbook with an eye towards the theory of categories of sheaves and their application in homological algebra is
The definition of categories in the foundations of homotopy type theory (see at internal category in homotopy type theory) is discussed in
Benedikt Ahrens, Chris Kapulkin, Michael Shulman, Univalent categories and the Rezk completion (arXiv:1303.0584)
Paolo Capriotti, Nicolai Kraus, Univalent Higher Categories via Complete Semi-Segal Types (arXiv:1707.03693)
Jason Gross, Adam Chlipala, David Spivak, Experience Implementing a Performant Category-Theory Library in Coq (arXiv:1401.7694)
For more references see category theory.
Last revised on April 14, 2018 at 11:58:02. See the history of this page for a list of all contributions to it.