Category theory

Cat­e­gory the­ory stud­ies the ab­strac­tion of math­e­mat­i­cal ob­jects (such as sets, groups, and topolog­i­cal spaces) in terms of the mor­phisms be­tween them. Such a col­lec­tion of ob­jects and mor­phisms is a cat­e­gory. Mor­phisms of­ten rep­re­sent func­tions. For ex­am­ple, in the cat­e­gory of sets, mor­phisms rep­re­sent all func­tions, in the cat­e­gory of groups they rep­re­sent group ho­mo­mor­phism and in the cat­e­gory of topolog­i­cal spaces, they rep­re­sent con­tin­u­ous maps.

Cat­e­gories are usu­ally drawn as di­a­grams with the ob­jects rep­re­sented by vari­ables or points with (la­beled) ar­rows be­tween them rep­re­sent­ing mor­phisms. For this rea­son, mor­phisms are also referred to as ar­rows.

Mor­phisms do not have to rep­re­sent func­tions. For ex­am­ple, any par­tially or­dered set \((P, \leq)\) may be seen as a cat­e­gory where the ob­jects are the el­e­ments of the poset and there is a (unique) mor­phism \(x \rightarrow y\) be­tween two el­e­ments \(x\) and \(y\) if and only if \(x \leq y\).

Definition

A cat­e­gory con­sists of a col­lec­tion of ob­jects and a col­lec­tion of mor­phisms. A mor­phism \(f\) goes from one ob­ject, say \(X\), to an­other, say \(Y\), and is drawn as an ar­row from \(X\) to \(Y\). Note that \(X\) may equal \(Y\) (in which case \(f\) is referred to as an en­do­mor­phism). The ob­ject \(X\) is called the source or do­main of \(f\) and \(Y\) is called the tar­get or codomain of \(f\). This is writ­ten as \(f: X \rightarrow Y\).

Th­ese mor­phisms must satisfy three con­di­tions:

  1. Com­po­si­tion: For any two mor­phisms \(f: X \rightarrow Y\) and \(g: Y \rightarrow Z\), there ex­ists a mor­phism \(X \rightarrow Z\), writ­ten as \(g \circ f\) or sim­ply \(gf\).

  2. As­so­ci­a­tivity: For any mor­phisms \(f: X \rightarrow Y\), \(g: Y \rightarrow Z\) and \(h:Z \rightarrow W\) com­po­si­tion is as­so­ci­a­tive, i.e., \(h(gf) = (hg)f\).

  3. Iden­tity: For any ob­ject \(X\), there is a (unique) mor­phism, \(1_X : X \rightarrow X\) which, when com­posed with an­other mor­phism, leaves it un­changed. I.e., given \(f:W \rightarrow X\) and \(g:X \rightarrow Y\) it holds that: \(1_X f = f\) and \(g 1_X = g\).

Note that com­po­si­tion is writ­ten ‘back­wards’ since given an el­e­ment \(x \in X\) and two func­tions \(f: X \rightarrow Y\) and \(g: Y \rightarrow Z\), the re­sult of ap­ply­ing \(f\) then \(g\) is \(g(f(x))\) which equals \((g \circ f)(x)\).

Motivation

Many math­e­mat­i­cal con­struc­tions (such as prod­ucts) ap­pear across differ­ent fields of math­e­mat­ics, con­sist­ing of differ­ent in­gre­di­ents but nev­er­the­less cap­tur­ing a similar idea (and of­ten even un­der the same name). Cat­e­gory the­ory al­lows one to pre­cisely de­scribe the prop­erty that these differ­ent con­struc­tions all at once. This al­lows one to prove the­o­rems about all these struc­tures at once. Hence, once you prove that a spe­cific math­e­mat­i­cal struc­ture is, say, a product, then all the cat­e­gory-the­o­retic the­o­rems about prod­ucts are true for that struc­ture. In fact, some­times there are struc­tures which non-ob­vi­ously satisfy a cat­e­gory-the­o­retic prop­erty. Espe­cially when cat­e­gory-the­o­retic du­al­ity is in­volved.

In ad­di­tion, cat­e­gory the­ory al­lows the sim­ple de­scrip­tion of func­tors, nat­u­ral trans­for­ma­tions and ad­junc­tions. Th­ese are math­e­mat­i­cally pow­er­ful con­cepts which are very difficult to de­scribe with­out the lan­guage of cat­e­gory the­ory. In fact, one of the founders of cat­e­gory the­ory, Saun­ders Mac Lane, has re­marked that cat­e­gory the­ory was ini­tially de­vel­oped in or­der to provide a lan­guage in which to speak about nat­u­ral trans­for­ma­tions.

Pow­er­fully, func­tors and ad­junc­tions be­tween cat­e­gories al­low one to trans­late con­cepts from one math­e­mat­i­cal the­ory to an­other. They provide a “trans­la­tion” (ei­ther full or par­tial) that al­lows one type of ob­ject to be viewed as an­other, and the­o­rems to be trans­lated across do­mains. In fact, us­ing du­al­ity, very non-ob­vi­ous trans­la­tions can be found be­cause a the­o­rem in one cat­e­gory can be trans­lated to its “op­po­site the­ory” in the other cat­e­gory. Con­nec­tions which are not ob­vi­ous in the lan­guage of the math­e­mat­i­cal the­o­ries them­selves, be­come clear in the lan­guage of cat­e­gory the­ory.

Cat­e­gories Give an Ex­ter­nal View

Although the ob­jects and mor­phisms of a cat­e­gory are in­tended to rep­re­sent e.g. sets and func­tions, from the point of view of the cat­e­gory the ob­jects and mor­phisms have no in­ter­nal struc­ture. It is not pos­si­ble to talk di­rectly about the el­e­ments of an ob­ject or how a given mor­phism maps el­e­ments. In­stead (from the view­point of the cat­e­gory) the in­for­ma­tion about the ob­jects and mor­phisms are given com­pletely by which ob­jects are sources and tar­gets for the mor­phisms and how the mor­phisms are com­posed.

In fact, this is the strength of cat­e­gory the­ory: ab­stract­ing away the in­ter­nal de­tails al­lows one to fo­cus only on rele­vant in­for­ma­tion and also cap­ture in­for­ma­tion about mul­ti­ple similar types of struc­tures that act in a cer­tain way across differ­ent math­e­mat­i­cal the­o­ries.

This is similar to the way that a group ab­stracts away what el­e­ments are whilst only cap­tur­ing the in­for­ma­tion of how they are ‘added’ or ‘mul­ti­plied’.

It is also some­what similar to the con­cept of a pro­gram’s API (or an in­ter­face in Java); we can’t see in­side the pro­gram or know how it im­ple­ments some­thing, but we know what kind of in­puts and out­puts pro­grams have, and what kinds of in­puts and out­puts a com­po­si­tion of such pro­grams have.

Note that since it ab­stracts some­thing away, a cat­e­gory does not always cap­ture enough in­for­ma­tion for one’s pur­poses. For ex­am­ple, there is ad­di­tion of group ho­mo­mor­phisms defined poin­t­wise. For this pur­pose, other struc­tures such as en­riched cat­e­gories and n-cat­e­gories may be used. How­ever, for many pur­poses, cat­e­gories are at a very good be­tween iso­mor­phic ob­jects. This is con­sid­ered a fea­ture of cat­e­gory the­ory.

Com­mon Sym­bols: Convention

Differ­ent texts make use of differ­ent con­ven­tions. This site makes use of the fol­low­ing com­mon con­ven­tion:

  • Cat­e­gories are writ­ten in black­board bold up­per-case let­ters and are usu­ally near the be­gin­ning of the alpha­bet. E.g. \(\mathbb{A}, \mathbb{B}, \mathbb{C}\).

  • Ob­jects are writ­ten as up­per-case let­ters usu­ally near the be­gin­ning or end of the alpha­bet. E.g. \(A, B, C, W, X, Y, Z\).

  • Mor­phisms are la­bel­led with lower-case let­ters, usu­ally near f or near u. E.g. \(e, f, g, h, u, v, w\).

  • Ele­ments of an ob­ject, where nec­es­sary, are writ­ten as lower-case let­ters, usu­ally near the be­gin­ning or end of the alpha­bet. E.g. \(a, b, c, x, y, z\)

  • Func­tors are writ­ten as up­per-case let­ters usu­ally near F. E.g. \(E, F, G, H\).

  • Nat­u­ral trans­for­ma­tions are writ­ten as Greek let­ters, usu­ally near the be­gin­ning of the alpha­bet. E.g. \(\alpha, \beta, \gamma, \delta\).

  • The mor­phisms form­ing part of a cone or co­cone for a limit or col­imit are of­ten writ­ten as Greek let­ters with sub­scripts, usu­ally \(\kappa\) or \(\lambda\).

Th­ese con­ven­tions are merely guidelines and far from uni­ver­sally fol­lowed. Check the defi­ni­tion for the sym­bol in ques­tion to see what it represents

Iso­mor­phisms in Cat­e­gory Theory

In cat­e­gory the­ory, iso­mor­phic ob­jects are not dis­t­in­guished. Many uni­ver­sal con­struc­tions do not pin down a spe­cific con­struc­tion but in­stead only spec­ify it up to iso­mor­phism.

Do­ing some­thing in cat­e­gory the­ory which re­lies on a spe­cific con­struc­tion, that is, re­quiring ob­jects to be equal in­stead of merely iso­mor­phic, is col­lo­quially referred to as evil.

Univer­sal Properties

One of the most im­por­tant con­cepts in cat­e­gory the­ory is that of a uni­ver­sal prop­erty. An ob­ject in a cat­e­gory which satis­fies a uni­ver­sal prop­erty is in a sense the ‘best’ (of­ten mean­ing small­est or largest) ob­ject satis­fy­ing a cer­tain prop­erty. This can of­ten be used to de­scribe in a uni­ver­sal way con­struc­tions like prod­ucts which are defined for mul­ti­ple dis­tinct struc­tures. In cat­e­gory the­ory, it is defined once with­out refer­ring to a spe­cific con­struc­tion. This defi­ni­tion can then be ap­plied to mul­ti­ple cat­e­gories.

The sim­plest non-triv­ial uni­ver­sal con­struc­tion is the ter­mi­nal ob­ject. Given a cat­e­gory \(\mathbb{C}\), an ob­ject \(T\) in \(\mathbb{C}\) is called a ter­mi­nal ob­ject if, for any ob­ject \(X\) in \(\mathbb{C}\), there is a unique mor­phism \(f: X \rightarrow T\). In other words there is some \(f: X \rightarrow T\) and if there is also \(g: X \rightarrow T\) then \(f=g\). In the cat­e­gory of sets, the ter­mi­nal ob­jects are ex­actly the one el­e­ment sets. Given a one el­e­ment set \(\{a\}\), and any set \(X\), there is a unique mor­phism \(f: X \rightarrow \{a\}\), namely the func­tion tak­ing ev­ery \(x\) in \(X\) to \(a\). In the cat­e­gory of groups, ter­mi­nal ob­jects are ex­actly one-el­e­ment groups. Note that ter­mi­nal ob­jects need not ex­ist. Con­sider a poset seen as a cat­e­gory. If it has a largest el­e­ment \(T\), then each ob­ject is less than or equal to \(T\). So from each ob­ject there is a unique mor­phism to \(T\) and hence it is ter­mi­nal. If, how­ever, there is no largest el­e­ment then the cat­e­gory has no ter­mi­nal ob­ject.

As an­other ex­am­ple, prod­ucts can be defined by a uni­ver­sal prop­erty: Given a pair of ob­jects \(X\) and \(Y\), an ob­ject \(P\) along with a pair of mor­phisms \(f: P \rightarrow X\) and \(g: P \rightarrow Y\) is called the product of \(X\) and \(Y\) if, given any other ob­ject \(W\) and mor­phisms \(u: W \rightarrow X\) and \(v:W \rightarrow Y\) there is a unique mor­phism \(h: W \rightarrow P\) such that \(fh = u\) and \(gh = v\).

The above are both spe­cial cases of a very im­por­tant and more gen­eral uni­ver­sal con­struc­tion: the limit. This (along with the col­imit) is de­scribed in more de­tail fur­ther be­low.

Duality

For any no­tion in a cat­e­gory, its dual is ob­tained by `re­vers­ing all the ar­rows’ and ‘re­vers­ing the or­der of com­po­si­tion’. If a state­ment is true in any cat­e­gory, then its dual is true in any cat­e­gory. As a corol­lary, if a state­ment is true in some cat­e­gories, its dual is true in the du­als of those cat­e­gories.

As an ex­am­ple, con­sider the defi­ni­tion of a ter­mi­nal ob­ject given above. A state­ment about ter­mi­nal ob­ject is that any two ter­mi­nal ob­jects are iso­mor­phic. Let’s ex­am­ine the ex­act state­ment. As­sume \(T\) is ter­mi­nal. Then for any \(X\) there is unique \(f: X \rightarrow T\). If we re­verse the ar­rows, we get that for ev­ery \(X\) there is unique \(f: X \leftarrow T\). This is the defi­ni­tion of an ini­tial ob­ject. Con­sider an­other ter­mi­nal ob­ject \(T'\). The state­ment that \(T'\) is iso­mor­phic to \(T\) is means that there is some \(f: T \rightarrow T'\) and \(g: T' \rightarrow T\) such that \(gf = 1_T\) and \(fg = 1_{T'}\). The dual of this is just the state­ment that there is some \(f: T \leftarrow T'\) and \(g: T' \leftarrow T\) such that \(fg = 1_T\) and \(gf = 1_{T'}\), this is ex­actly the same prop­erty! (The mor­phisms \(f\) and \(g\) have just been re­named). Hence, the dual of the state­ment that a ter­mi­nal ob­ject is unique up to iso­mor­phism is the state­ment that ev­ery ini­tial ob­ject is unique up to iso­mor­phism.

Similarly, if some­thing is true for ev­ery cat­e­gory with an ini­tial ob­ject, its dual will be true for ev­ery cat­e­gory with a ter­mi­nal ob­ject.

The con­cept of du­al­ity can be a pow­er­ful way of ob­tain­ing new re­sults which come eas­ily within cat­e­gory the­ory, but which are not ob­vi­ous in the the­ory to which cat­e­gory the­ory is be­ing ap­plied. As an ad­vanced ex­am­ple, the cat­e­gory of Boolean Alge­bras is dual to the cat­e­gory of Stone Spaces. See, Stone Dual­ity on Wikipe­dia for the mo­ti­va­tion.

Add bet­ter ex­am­ple(s) of duality

Functors

A func­tor is a mor­phism be­tween cat­e­gories.

Given two cat­e­gories \(\mathbb{A}\) and \(\mathbb{B}\), a func­tor \(F\) from \(\mathbb{A}\) to \(\mathbb{B}\), writ­ten \(F: \mathbb{A} \rightarrow \mathbb{B}\) is defined as a pair of func­tions:

  • \(F_0:\) Ob­jects(\(\mathbb{A}\)) \(\rightarrow\) Ob­jects(\(\mathbb{B}\))

  • \(F_1:\) Mor­phisms(\(\mathbb{A}\)) \(\rightarrow\) Mor­phisms(\(\mathbb{B}\))

Which satisfy:

1. Preser­va­tion of do­main and codomain: If \(f: X \rightarrow Y\) then \(F_1(f): F_0(X) \rightarrow F_1(Y)\). ( Put differ­ently, Dom(\(F_1(f)\)) = \(F_0\)(Dom(\(f\))) and Cod(\(F_1(f)\)) = \(F_0\)(Cod(\(f\))) for ev­ery mor­phism \(f\). )

  1. Preser­va­tion of Iden­tity: If the mor­phism \(1_X: X \rightarrow X\) is the iden­tity on \(X\), then the mor­phism \(F_1(1_X): F_0(X) \rightarrow F_0(X)\) is the iden­tity on \(F_0(X)\).

  2. Preser­va­tion of com­po­si­tion: Given mor­phisms \(f: X \rightarrow Y\) and \(g: Y \rightarrow Z\), then the com­po­si­tion of their images \(F_1(g) \circ F_1(f): F_0(X) \rightarrow F_0(Z)\) is the image of their com­po­si­tion \(F_1(g \circ f): F_0(X) \rightarrow F_0(Z)\).

In­stead of differ­en­ti­at­ing \(F_0\) and \(F_1\), they are usu­ally both writ­ten sim­ply as \(F\). E.g. \(F(f): F(X) \rightarrow F(Y)\).

Prop­er­ties of Morphisms

Mor­phisms are the cen­tral ob­jects of study in cat­e­gory the­ory. For this rea­son, prop­er­ties of mor­phisms can be very im­por­tant. A mor­phism \(f: X \rightarrow Y\) is called the fol­low­ing if it satis­fies the given prop­erty:

  • Iso­mor­phism: (Self-dual)

There ex­ists some \(g: Y \rightarrow X\) such that \(gf = 1_X\) and \(fg = 1_Y\).

In­tu­itively, an iso­mor­phism is a way of trans­form­ing from one ob­ject to an­other in a way that makes them in­dis­t­in­guish­able us­ing the in­for­ma­tion of the cat­e­gory.

  • Monomor­phism: (Dual to epi­mor­phic)

For any ob­ject \(W\) and mor­phisms \(g,h: W \rightarrow X\), if \(fg = fh\) then \(g = h\).

In­tu­itively, \(f\) be­ing a monomor­phism in­di­cates that all of the in­for­ma­tion cap­tured by the col­lec­tion of mor­phisms into \(X\) is pre­served when com­pos­ing by \(f\). It gen­er­al­izes the no­tion of an in­jec­tive func­tion, since in most con­crete cat­e­gories (like sets, groups, and topolog­i­cal spaces) ev­ery in­jec­tive map is a monomor­phism. How­ever, even in con­crete cat­e­gories (and cer­tainly more gen­er­ally), monomor­phisms need not be in­jec­tive.

  • Epi­mor­phism: (Dual to monomor­phic)

For any ob­ject \(Z\) and mor­phisms \(g,h: X \rightarrow Z\), if \(gf = hf\) then \(g = h\).

In­tu­itively, \(f\) be­ing an epi­mor­phism in­di­cates that all the in­for­ma­tion cap­tured by the col­lec­tion of mor­phisms out of \(Y\) is pre­served when com­pos­ing by \(f\).. It gen­er­al­izes the no­tion of a sur­jec­tive func­tion. How­ever, in an even stronger sense than for monomor­phisms, a func­tion be­ing epi­mor­phic and a func­tion be­ing sur­jec­tive are far from equiv­a­lent.

Prop­er­ties that more closely match sur­jec­tivity in­clude Sec­tion /​ Split Epi­mor­phism, and reg­u­lar epi­mor­phism. strict epi­mor­phism, strong epi­mor­phism, and ex­tremal epi­mor­phism. Note that de­spite the names, not all of these are nec­es­sar­ily epi­mor­phisms, but are epi­mor­phisms in “nice” cat­e­gories.

  • En­do­mor­phism: (Self-dual)

\(X = Y\), i.e., \(f: X \rightarrow X\).

An en­do­mor­phism is a mor­phism from an ob­ject to it­self.

  • Au­to­mor­phism: (Self-dual)

The mor­phism \(f\) is both an en­do­mor­phism and an iso­mor­phism.

An au­to­mor­phism is a mor­phism from a struc­ture to it­self that pre­serves all the in­for­ma­tion of the struc­ture that is dis­t­in­guish­able by the cat­e­gory. In­tu­itively, it gives “an­other view” of a struc­ture (say, by mov­ing around its el­e­ments) that leaves it es­sen­tially un­changed.

  • Re­trac­tion /​ Split Monomor­phism: (Dual to split epi­mor­phic)

There ex­ists some \(g: Y \rightarrow X\) such that \(gf = 1_X\)

A mor­phism is a re­trac­tion if its effect can be “re­versed” or in­verted by an­other mor­phism ap­plied af­ter it. For ex­am­ple, ev­ery in­jec­tive map is a re­trac­tion. The mor­phism which in­verts the re­trac­tion is a sec­tion.

  • Sec­tion /​ Split Epi­mor­phism: (Dual to split monomor­phic)

There ex­ists some \(g: Y \rightarrow X\) such that \(fg = 1_Y\)

A mor­phism is a sec­tion if it “re­verses” the effect of some other mor­phism ap­plied be­fore it. The mor­phism which is in­verted is a re­trac­tion.

Limits and Colimits

Fur­ther Univer­sal Constructions

Nat­u­ral Transformations

Con­struc­tions on Categories

Ad­junc­tions and Ad­joint Functors

Children:

  • Category (mathematics)

    A de­scrip­tion of how a col­lec­tion of math­e­mat­i­cal ob­jects are re­lated to one an­other.

  • Equaliser (category theory)
  • Product (Category Theory)

    How a product is char­ac­ter­ized rather than how it’s constructed

  • Object identity via interactions

    If we think of ob­jects as opaque “black boxes”, how can we tell whether two ob­jects are differ­ent? By look­ing at how they in­ter­act with other ob­jects!

  • Universal property

    A uni­ver­sal prop­erty is a way of defin­ing an ob­ject based purely on how it in­ter­acts with other ob­jects, rather than by any in­ter­nal prop­erty of the ob­ject it­self.

  • Category of finite sets

    The cat­e­gory of finite sets is ex­actly what it claims to be. It’s a use­ful train­ing ground for some of the ideas of cat­e­gory the­ory.

Parents:

  • Mathematics

    Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.