nLab category

Redirected from "Categories".
Contents

This page is about the concept in mathematics. For the concept of the same name in philosophy see at category (philosophy).

Contents

Idea

  • 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 collection of objects and a collection of morphisms. Every morphism has a source object and a target object. If ff is a morphism with xx as its source and yy as its target, we write

    f:xyf : x \to y

    and we say that ff is a morphism from xx to yy. In a category, we can compose a morphism g:xyg : x \to y and a morphism f:yzf : y \to z to get a morphism fg:xzf \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:xyf : x \to y is a function from the set xx to the set yy. Here composition is the usual composition of functions.

For more background on and context for categories see

Definitions

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:

  • Each introduces its own system of notation, both of which are useful in other parts of category theory, so one should know them.

  • One definition generalises quite nicely to the notion of internal category, while the other generalises quite nicely to the notion of enriched category; these are both important concepts.

  • When examining alternative foundations, sometimes one definition or the other may be more appropriate; in any case, one will want to examine the question of their equivalence.

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.

With one collection of morphisms

[Grothendieck 61, Section 4]

A category CC consists of

  • a collection (see Foundational issues and Size issues) C 0C_0 of objects;

  • a collection C 1C_1 of morphisms (or arrows);

  • for every morphism ff, an object s(f)s(f) (called its source or domain), and an object t(f)t(f) (called its target or codomain);

  • for every pair of morphisms ff and gg, where t(f)=s(g)t(f) = s(g), a morphism gfg \circ f, called their composite (also written gfg f or sometimes f;gf;g— see diagrammatic order);

  • for every object xx, a morphism id xid_x (or 1 x1_x), called the identity morphism on xx;

  • such that the following properties are satisfied:

    • source and target are respected by composition: s(gf)=s(f)s(g \circ f) = s(f) and t(gf)=t(g)t(g\circ f) = t(g);

    • source and target are respected by identities: s(1 x)=xs(1_x) = x and t(1 x)=xt(1_x) = x;

    • composition is associative: (hg)f=h(gf)(h \circ g)\circ f = h\circ (g \circ f) whenever t(f)=s(g)t(f) = s(g) and t(g)=s(h)t(g) = s(h);

    • composition satisfies the left and right unit laws: if s(f)=xs(f) = x and t(f)=yt(f) = y, then 1 yf=f=f1 x1_y \circ f = f = f \circ 1_x.

People also often write xCx \in C instead of xC 0x \in C_0 as a short way to indicate that xx is an object of CC. Also, some people write Ob(C)Ob(C) and Mor(C)Mor(C) instead of C 0C_0 and C 1C_1. One usually writes f:xyf\colon x \to y if fC 1f \in C_1 to state that s(f)=xs(f) = x and t(f)=yt(f) = y. Finally, people often write hom(x,y)hom(x,y), hom C(x,y)hom_C(x,y), or C(x,y)C(x,y) for the collection of morphisms f:xyf\colon x \to y.

If the identity-assigning map and its axiom is omitted, then one speaks of a semicategory.

With a family of collections of morphisms

A category CC consists of

  • a collection (see Foundational issues and Size issues) C 0C_0 of objects;

  • for each pair x,yx,y of objects, a collection C 1(x,y)C_1(x,y) of morphisms from xx to yy;

  • for each pair of morphisms ff in C 1(x,y)C_1(x,y) and gg in C 1(y,z)C_1(y,z), a morphism gfg \circ f in C 1(x,z)C_1(x,z), called their composite (also written gfg f or sometimes f;gf;g— see diagrammatic order);

  • for each object xx, a morphism id xid_x (or 1 x1_x) in C 1(x,x)C_1(x,x), called the identity morphism on xx;

  • such that the following properties are satisfied:

    • composition is associative: for each quadruple w,x,y,zw,x,y,z of objects, if fC 1(y,z)f \in C_1(y,z), gC 1(x,y)g \in C_1(x,y), and hC 1(w,x)h \in C_1(w,x), then (fg)h=f(gh)(f \circ g)\circ h = f\circ (g \circ h);

    • composition satisfies the left and right unit laws: for each pair x,yx,y of objects, if fC 1(x,y)f \in C_1(x,y), then 1 yf=f=f1 x1_y \circ f = f = f \circ 1_x.

People also often write xCx \in C instead of xC 0x \in C_0 as a short way to indicate that xx is an object of CC. Also, some people write Ob(C)Ob(C) instead of C 0C_0 and hom(x,y)hom(x,y), hom C(x,y)hom_C(x,y), or C(x,y)C(x,y) instead of C 1(x,y)C_1(x,y). One usually writes f:xyf\colon x \to y to state that fC 1(x,y)f \in C_1(x,y). Finally, people often write C 1C_1 or Mor(C)Mor(C) for the disjoint union xC 0 yC 0C 1(x,y)\biguplus_{x \in C_0} \biguplus_{y \in C_0} C_1(x,y).

Equivalence between the two definitions

Given a one-collection-of-morphisms category C 1C 0C_1\rightrightarrows C_0, we define a family-of-collections-of-morphisms category by taking C 1(x,y)C_1(x,y) to be the preimage of (x,y)(x,y) under the function (s,t):C 1C 0×C 0(s,t):C_1 \to C_0\times C_0. Conversely, given a family-of-collections-of-morphisms category we define a one-collection-of-morphisms category by taking C 1C_1 to be the disjoint union of the families of morphisms C 1= x,yC 0C 1(x,y)C_1 = \coprod_{x,y\in C_0} C_1(x,y). With the straightforward definitions of functor and natural transformation in both cases, this sets up a strict 2-equivalence? of 2-categories.

Note, though, that this 2-equivalence is not an isomorphism of 2-categories, because the disjoint union operation has to “tag” each morphism with its domain and codomain. It seems that the strongest thing that can be said is that, in a material set theory, if a family-of-collections-of-morphisms category CC has the property that sets C 1(x,y)C_1(x,y) are all disjoint, then there is a one-collection-of-morphisms category with C 1= x,yC 0C 1(x,y)C_1 = \bigcup_{x,y\in C_0} C_1(x,y) (the non-disjoint union) that gives rise to CC on the nose. The notion of protocategory is a way to formalize a family-of-collections-of-morphisms category together with the information about how its hom-sets “overlap”.

In ordinary category theory one rarely specifies which of the two definitions is being used, although often language implicitly suggests that it is the latter, e.g. when defining a category one first specifies the objects and then specifies what “the morphisms from XX to YY are” rather than specifying what “a morphism” is and then what the domain and codomain of each morphism are. Indeed, when defining a category in this way, one rarely worries about whether the hom-sets are disjoint, meaning that it must be the second definition in use. Even for the prototypical category Set, if constructed in a material-set-theoretic foundation like ZFC, the natural definition “a morphism from XX to YY is a function, i.e. a subset of X×YX\times Y that is total and functional”, produces hom-sets that are not disjoint, since a total and functional set of ordered pairs can have any codomain that is a superset of its range. Moreover, categorical constructions do not “naturally” preserve disjointness of homsets, e.g. in the category of elements el(P)el(P) of a functor P:CSetP:C\to Set a given morphism in CC can “be” a morphism between many different elements of PP, and similarly for a slice category and so on.

Foundational issues

We said a category has a ‘collection’ of objects and ‘collection’(s) of morphisms. However, different mathematical foundations have different notions of equality. For foundations whose notion of ‘collection’ have proposition-valued equality, such as in set theory, class-set theory, or extensional type theory, the two definitions above suffice for defining a category. However, in for other foundations, with a weaker notion of equality, such as internally in a (2,1)-topos like Grpd, in Thomas Streicher‘s groupoid model of types, or in homotopy type theory, there are multiple definitions of a category. The naive definition of the category above with a collection of objects and a collection of morphisms results in a wild category. If the morphism collections are sets, then the resulting structure is a precategory, and if the collection of objects is a set as well, then the resulting structure is a strict category. The above definitions in set theory foundations are the same as strict categories in the alternative foundations, but in the alternative foundations categories like Set are not strict categories. Instead, they happen to be a special kind of precategory called univalent categories, where equality of objects is isomorphism of objects.

Size issues

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)C_1(x,y) is a set for every pair of objects x,yx,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).

Alternative definitions

For some purposes it is useful or necessary to vary the way the ordinary definition of category is expressed. See

Equivalent definitions

A category is equivalently

Generalizations

Internal categories

The first definition, with a single collection C 1C_1 of morphisms, generalises to the notion of internal category. Essentially, we define a category internal to (some other category) DD as above, with ‘collection’ interpreted as an object of DD and ‘function’ interpreted as a morphism of DD. In particular, a category internal to Set is the same thing as a small category.

Enriched categories

The second definition of a category, as a family C 1(x,y)C_1(x,y) of collections of morphisms, generalises to the notion of enriched category: we define a category enriched over (some other category) DD as above, with the collection of objects still a ‘collection’ as before, but with objects of DD in place of the collections of morphisms and morphisms of DD in place of the various functions. In particular, a category enriched over Set is the same thing as a locally small category.

Indexed categories

The notion of indexed category captures the idea of woking “over a base” other than Set.

Multicategories etc.

There is a generalization of the notion of category 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.

Higher categories

See higher category theory.

Examples

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:

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)hom(x,y) if xx is less than or equal to yy, 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 GG with collection of vertices G 0G_0 and collection of edges G 1G_1, there is the free category F(G)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 1G_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.

Basic notions

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

algebraic structureoidification
magmamagmoid
pointed magma with an endofunctionsetoid/Bishop set
unital magmaunital magmoid
quasigroupquasigroupoid
looploopoid
semigroupsemicategory
monoidcategory
anti-involutive monoiddagger category
associative quasigroupassociative quasigroupoid
groupgroupoid
flexible magmaflexible magmoid
alternative magmaalternative magmoid
absorption monoidabsorption category
cancellative monoidcancellative category
rigCMon-enriched category
nonunital ringAb-enriched semicategory
nonassociative ringAb-enriched unital magmoid
ringringoid
nonassociative algebralinear magmoid
nonassociative unital algebraunital linear magmoid
nonunital algebralinear semicategory
associative unital algebralinear category
C-star algebraC-star category
differential algebradifferential algebroid
flexible algebraflexible linear magmoid
alternative algebraalternative linear magmoid
Lie algebraLie algebroid
monoidal poset2-poset
strict monoidal groupoid?strict (2,1)-category
strict 2-groupstrict 2-groupoid
strict monoidal categorystrict 2-category
monoidal groupoid(2,1)-category
2-group2-groupoid/bigroupoid
monoidal category2-category/bicategory

References

(For more extensive references see at category theory.)

The concept originates in

The definition “with a single set of morphisms” (i.e. as internal categories in Set) appears in:

  • Alexander Grothendieck, Section 4 of: Techniques de construction et théorèmes d’existence en géométrie algébrique III: préschémas quotients, Séminaire Bourbaki: années 1960/61, exposés 205-222, Séminaire Bourbaki, no. 6 (1961), Exposé no. 212, (numdam:SB_1960-1961__6__99_0, pdf)

Textbook accounts:

Expositions:

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

For more references see category theory.

Last revised on November 18, 2023 at 05:01:27. See the history of this page for a list of all contributions to it.