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.

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.

Con­struc­tions on Categories

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.

• This is still very much a work in progress. Any­one is wel­come to sub­mit more info or edit. I’ll add more de­tails later. The cur­rent page prob­a­bly won’t re­main the main lens.

• Prob­a­bly you will want to pre­cisely define mor­phism at some point, but I recom­mend you do it sooner rather than later to en­force co­her­ence.

• I don’t un­der­stand? A mor­phism is just an ab­stract el­e­ment of a cat­e­gory. Its be­havi­our is com­pletely char­ac­ter­ized by the ax­ioms of a cat­e­gory. It would be like for­mally defin­ing an el­e­ment of a set.

• @2mn I am imag­in­ing my­self in the shoes of some­body who doesn’t know any­thing about cat the­ory get­ting frus­trated when they find that the ar­ti­cle keeps talk­ing about mor­phisms with­out giv­ing a clue of what they are.

I think that it would be valuable to spend some time work­ing on an in­tu­itive defi­ni­tion of mor­phism in its cor­re­spond­ing page to alle­vi­ate that.

• @2vh I’ve sub­mit­ted an edit to the page on mor­phisms and wrote an in­tu­itive guide to iso­mor­phisms. I hope it’s suit­able for now.

My plan is also even­tu­ally to write an in­tu­itive guide to cat­e­gories with lots of con­crete ex­am­ples which hope­fully tie in to some real-world ideas and are not as re­li­ant on ab­stract math­e­mat­ics.

How­ever, I’d like to get some of the ba­sic con­cepts down for the sake of the main lens. Also I’m for­mally trained in pure math so these are the set­ting and ex­am­ples with which I’m more familar.

• It looks like there is a word miss­ing from this sen­tence. I’m not sure what it is try­ing to say.