Category Theory/Printable version

Category Theory

The current, editable version of this book is available in Wikibooks, the open-content textbooks collection, at
https://en.wikibooks.org/wiki/Category_Theory

Permission is granted to copy, distribute, and/or modify this document under the terms of the Creative Commons Attribution-ShareAlike 3.0 License.

Definition, examples

Definition (category):

A category ${\mathcal {C}}$ is a class of objects, together with a class of so-called morphisms, each of which have a domain and a target, and a composition of morphisms, such that the following set of axioms hold, if for any two objects $A$ and $B$ of ${\mathcal {C}}$ the subclass of morphisms with domain $A$ and target $B$ is denoted $\operatorname {Hom} (A,B)$:

1. Whenever either $A\neq A'$ or $B\neq B'$, $\operatorname {Hom} (A,B)$ and $\operatorname {Hom} (A',B')$ are disjoint
2. For any objects $A,B,C$ of ${\mathcal {C}}$ and any morphisms $f:A\to B$ and $g:B\to C$, there exists a morphism $h=g\circ f\in \operatorname {Hom} (A,C)$, called the composition of $f$ and $g$
3. Composition is associative, ie. $f\circ (g\circ h)=(f\circ g)\circ h$
4. Whenever $A$ is an object of ${\mathcal {C}}$, then there exists a unique morphism $1_{A}\in \operatorname {Hom} (A,A)$ that acts as an identity both on the left and on the right for the composition of morphisms.

Exercises

1. If both $f$ and $g$ are set mappings such that $f\circ g$ is injective, prove that $g$ is injective.

Natural transformations

Definition (natural transformation):

Let ${\mathcal {A}},{\mathcal {B}}$ be categories, and let $F,G:{\mathcal {A}}\to {\mathcal {B}}$ be two functors. A natural transformation between these two functors is a collection of morphisms of ${\mathcal {B}}$, one for each object $A$ of ${\mathcal {A}}$, namely $f_{A}:F(A)\to G(A)$, such that for all morphisms $g:A\to A'$ of ${\mathcal {A}}$, the following diagram commutes:

diagram placeholder

Old content

One further basic notion in the theory of categories, or, as it may be said, a basic item of categorical language, will now be introduced. This is the notion of a natural transformation of functors from one category to another. Indeed, the whole language and apparatus of categories and functors were developed initially by the U.S. mathematicians Samuel Eilenberg and Saunders MacLane in order to render precise the intuitive concept of naturality. First an example will be given, the example that may be said to have motivated the definition.

Motivating example

Let $\mathbb {V}$ be a vector space over some field $F$, and let $\mathbb {V} ^{*}$ be the dual space of $\mathbb {V}$; that is, the space of linear functionals on $\mathbb {V}$. There is then a linear transformation $T:\mathbb {V} \to \mathbb {V} ^{**}$ that is given. There is an intuitive feeling that the linear transformation $T$ is natural because its description only involves the terms u and f. Now if $\mathbb {V}$ is finite-dimensional, then it is known that $T$ is an isomorphism in the category of vector spaces over $F$ and linear transformations. One way of proving that $T$ is then an isomorphism is to show that $\mathbb {V}$ and $\mathbb {V} ^{**}$ are isomorphic and then to observe that $T$ is one–one. The usual proof that $\mathbb {V}$ and $\mathbb {V} ^{**}$ are isomorphic would be to proceed by establishing an isomorphism between $\mathbb {V}$ and $\mathbb {V} ^{*}$, in the case when $\mathbb {V}$ is finite-dimensional. Now if a base $(e_{1},\dots ,e_{N})$ for $\mathbb {V}$ is given, then a basis for $\mathbb {V} ^{*}$ may be set up, called the dual basis, by defining $e_{i}^{*}$ to be that linear functional on $\mathbb {V}$ given by certain rules (see 350). Then the correspondence $e_{i}\leftrightarrow e_{i}^{*}$ sets up an isomorphism between $\mathbb {V}$ and $\mathbb {V} ^{*}$.

On the other hand, this isomorphism does not look natural, because it depends on the choice of bases. Of course, the argument above could be generalized to set up a linear transformation from $\mathbb {V}$ to $\mathbb {V}$* even if $\mathbb {V}$ is not finite-dimensional over $F$, but, again, this transformation would not appear to be natural. What is required is a formal and precise expression of the feeling that, for finite-dimensional vector spaces $\mathbb {V}$ over the field $F$, $\mathbb {V}$ and $\mathbb {V} ^{**}$ are naturally isomorphic, while $\mathbb {V}$ and $\mathbb {V} ^{*}$ are isomorphic in some unnatural way. Eilenberg and MacLane solved this problem in their seminal article, “General Theory of Natural Equivalences,” published in 1945, which laid the foundation of the theory of categories.

Duality

For any category $C$ a new category $C^{op}$ can be formed by interchanging the domains and codomains of the morphisms of $C$. More precisely, in the category $C^{op}$ the objects are simply those of $C$ and the effect of interchange of domains is expressed in an equation (see 359). Moreover, the composition in $C^{op}$ is simply that of $C$, suitably interpreted. $C^{op}$ is called the category opposite to $C$; notice that $C^{op^{op}}$ = $C$. This apparently trivial operation leads to highly significant results when specific categories are used. In the general setting it enables any concept in the language of categories to be dualized. For example, the coproduct in $C$ is simply the product in $C^{op}$. Any theorem that holds in an arbitrary category has a dual form. For example, the theorem asserting that the product in an arbitrary category is associative may be effectively restated as asserting that the coproduct in an arbitrary category is associative. In the special cases, however, the second statement looks very different from the first. For example, in the category of sets, the coproduct becomes the disjoint union; in the category of groups it is the free product; and in a pre-ordered set regarded as a category, the coproduct is the least upper bound. In particular, for the set of natural numbers, ordered by divisibility, the coproduct is the LCM. Thus, the same universal argument that led to the deduction that the GCD is associative also indicates that the LCM is associative. The duality principle has very wide ramifications indeed. Here it is merely noted that the important concept of a contravariant functor $F:{\mathcal {C}}\to {\mathcal {D}}$ may be most simply defined as a functor $F:{\mathcal {C}}^{op}\to {\mathcal {D}}$. Thus the association of the dual vector space $\mathbb {V} ^{*}$ with $\mathbb {V}$ yields a contravariant functor from $\mathbb {V}$ to $\mathbb {V}$ itself.

Definition of natural transformation

Suppose $\Phi$, $\Psi$ are two functors, both from the category ${\mathcal {C}}$ to the category ${\mathcal {D}}$.

Then a natural transformation $\eta :\Phi \to \Psi$ is a rule that assigns to each object A of category ${\mathcal {C}}$ a morphism $\eta _{A}:\Phi (A)\to _{\mathcal {D}}\Psi (A)$.

The morphisms $\eta _{A}$involved must be subject to the condition that the diagram

should be commutative for every $f:A\to _{\mathcal {C}}B$ (note $f$ is a morphism in the category ${\mathcal {C}}$); that is, $\Psi (f)\circ \eta _{A}=\eta _{B}\circ \Phi (f)$ (note the commutative diagram is drawn in category ${\mathcal {D}}$).

Natural isomorphisms

Further, if $\eta _{A}$ is invertible for each A, then $\eta$ is said to be natural isomorphism (or a natural equivalence). It is clear that if $\eta$ is a natural equivalence from functors $\Phi$ to $\Psi$, then $\eta ^{-1}$, given by an equation (see 352), is a natural equivalence from functors $\Psi$ to $\Phi$. Thus the term equivalence used here is fully justified. Indeed, the functors from ${\mathcal {C}}$ to ${\mathcal {D}}$ may be collected into equivalence classes according to the existence of a natural equivalence between them.

Examples

This definition can be tested against the example. Consider two functors from K-Vect to K-Vect, in which K-Vect is the category of vector spaces over the field K and linear transformations. One functor is the identity functor. The other functor is the double dual functor ** that associates with every vector space V its double dual V** and with every linear transformation f : U → V in the linear transformation f**: U** → V** (see 353). A linear transformation T: V → V** was described above. It is easy to check that T is a natural transformation from the identity functor to the functor **. If the subcategory f of K-Vect that consists of finite-dimensional vector spaces over K and their linear transformations is considered, then it turns out that the functor ** transforms f into itself; and the natural transformation T, restricted to f, is then a natural equivalence. Further examples of natural transformations of functors can be given:

• The category of Abelian groups and homomorphisms is considered. With every Abelian group may be associated its torsion subgroup. The torsion subgroup AT of the Abelian group A consists of those elements of A that are of finite order. A homomorphism from A to B must necessarily send AT to BT. Thus a functor f is obtained from to (or to T, the category of torsion Abelian groups and their homomorphisms), by associating with every Abelian group A the Abelian group FA = AT. Now AT is a subgroup of A. Thus there is always an embedding iA of AT in A. It is easy to see that i is a natural transformation from the torsion functor f to the identity functor. Further, the quotient group Afr = A/AT may be considered. It is a torsion-free Abelian group. This gives a functor g from to (or from to fr, the category of torsion-free Abelian groups) by associating with the Abelian group A the Abelian group GA = Afr. Then the projection of A onto Afr yields a natural transformation from the identity functor to the torsion-free functor g.
• With every group may be associated its commutator subgroup. It is then not difficult to see that the embedding of the commutator subgroup in the group is a natural transformation from the commutator subgroup functor to the identity functor. On the other hand, the centre of every group may be associated with the group. Here, however, there is not a functor because a homomorphism from one group to another does not necessarily map the centre of the first group to the centre of the second. On the other hand, if the category of groups and surjective homomorphisms (a surjective homomorphism is one in which the image coincides with the codomain) is considered, then in this category the centre is a functor. It is a functor, however, from the category of groups and surjective homomorphisms to the category of groups and all homomorphisms, because a surjective homomorphism does not necessarily map the centre surjectively. Then the embedding of the centre of a group in the group may be regarded as a natural transformation from the centre functor to the inclusion functor, both of which are functors from the category of groups and surjective homomorphisms to the category of groups and homomorphisms.
• In algebraic topology, the singular homology groups and the homotopy groups of a pointed topological space (X, x) are considered. A Hurewicz homomorphism (see 354) exists, from the homotopy groups to the homology groups. Then pn and hn, n ≥ 2, are functors from the category of pointed spaces and pointed continuous functions to the category of Abelian groups, and the Hurewicz homomorphism is a natural transformation of functors.

The Yoneda lemma

Let ${\mathcal {C}}$ be a locally small category, let $X$ be an object in ${\mathcal {C}}$, let $K:{\mathcal {C}}\to \mathbf {Set}$, let $h^{X}$ denote the covariant Hom functor, and let ${\text{Nat}}(F,G)$ denote the natural transformations from $F$ to $G$. Then ${\text{Nat}}(h^{X},K)\cong KX$. In addition, if $K$ is another Hom functor $h^{W}$, then ${\text{Nat}}(h^{X},h^{W})\cong {\text{Hom}}_{\mathcal {C}}(W,X)$.

(Co-)cones and (co-)limits

Definition (cone):

Let ${\mathcal {C}}$ be a category and let $G=(V,A)$ be a diagram in ${\mathcal {C}}$. A cone over $G$ is an object $a$ of ${\mathcal {C}}$, together with morphisms $\phi _{a,b}:a\to b$ for each $b\in V$, so that for each $\psi :b\to b'\in A$ (so that $b,b'\in V$) we have

$\phi _{a,b'}=\psi \circ \phi _{a,b}$.

Definition (limit):

Let ${\mathcal {C}}$ be a category, let $G=(V,A)$ be a diagram in ${\mathcal {C}}$ and let

Definition (diagonal):

Let ${\mathcal {C}}$ be a category, and let $X$ be an object of ${\mathcal {C}}$. Further, suppose that the object $X\times X$ and the morphisms $\pi _{1}:X\times X\to X$ and $\pi _{2}:X\times X\to X$ constitute a product of $X$ with itself in ${\mathcal {C}}$. Then the diagonal (also called "diagonal morphism") is the unique morphism

$\Delta :X\to X\times X$

such that $\pi _{1}\circ \Delta =\pi _{2}\circ \Delta =\operatorname {Id} _{X}$.

Definition (anti-diagonal):

Let ${\mathcal {C}}$ be a category, and let $X$ be an object of ${\mathcal {C}}$. Further, suppose that the object $X\sqcup X$ and the morphisms $\iota _{1}:X\to X\sqcup X$ and $\iota _{2}:X\to X\sqcup X$ constitute a coproduct of $X$ with itself in ${\mathcal {C}}$. Then the anti-diagonal (also called "anti-diagonal morphism") is the unique morphism

$\nabla :X\sqcup X\to X$

such that $\nabla \circ \iota _{1}=\nabla \circ \iota _{2}=\operatorname {Id} _{X}$.

Exercises

1. 1. Let ${\mathcal {D}}$ be a category such that every two objects of ${\mathcal {D}}$ have a product. Suppose further that ${\mathcal {C}}$ is another category, and that $T:{\mathcal {C}}\to {\mathcal {D}}$ is a functor. Let $Y$ be an object of ${\mathcal {D}}$. Use the universal property of the product in order to show that there exists a functor $S_{Y}:{\mathcal {C}}\to {\mathcal {D}}$ that sends an object $X$ of ${\mathcal {C}}$ to the object $T(X)\times Y$ of ${\mathcal {D}}$.
   2. Prove that any morphism $g:Y\to Z$ in ${\mathcal {D}}$ gives rise to a natural transformation $S_{Y}\to S_{Z}$.
   3. Can we weaken the assumption that every two objects of ${\mathcal {D}}$ have a product? (Hint: Consider the image of the class function on objects associated to the functor $T$.)

Adjoint functors

Definition (adjoint functors):

Let ${\mathcal {A}},{\mathcal {B}}$ be categories. A pair of adjoint functors consists of two functors $L:{\mathcal {A}}\to {\mathcal {B}}$ and $R:{\mathcal {B}}\to {\mathcal {A}}$ (where $L$ is the left adjoint and $R$ is the right adjoint) such that the two bifunctors

$\operatorname {Hom} _{\mathcal {B}}(L\cdot ,\cdot )$ and $\operatorname {Hom} _{\mathcal {A}}(\cdot ,R\cdot )$

from $({\mathcal {A}},{\mathcal {B}})$ to $\operatorname {Set}$ are naturally isomorphic to each other.

Proposition (left adjoint functors preserve epimorphisms):

Let ${\mathcal {A}},{\mathcal {B}}$ be categories, and let $L:{\mathcal {A}}\to {\mathcal {B}}$ and $R:{\mathcal {B}}\to {\mathcal {A}}$ be an adjoint pair of functors. Suppose that $x,y\in A$ and $f\in \operatorname {Hom} _{\mathcal {A}}(X,Y)$ is an epimorphism. Then $Lf:LX\to LY$ is also an epimorphism.

Proof: Let $g,h:LY\to Z$ be arrows in ${\mathcal {B}}$ so that $g\circ Lf=h\circ Lf$. $\Box$

Proposition (right adjoint functors preserve monomorphisms):

Subcategories

Definition (subcategory):

Let ${\mathcal {C}}$ be a category. Then a subcategory ${\mathcal {D}}=(\operatorname {Ob} ({\mathcal {D}}),\operatorname {Mor} ({\mathcal {D}}))$ of ${\mathcal {C}}$ is a category such that $\operatorname {Ob} ({\mathcal {D}})\subseteq \operatorname {Ob} ({\mathcal {C}})$ and $\operatorname {Mor} ({\mathcal {D}})\subseteq \operatorname {Mor} ({\mathcal {C}})$.

Definition (full):

A subcategory ${\mathcal {D}}$ of a category ${\mathcal {C}}$ is called full iff for all $a,b\in {\mathcal {D}}$, we have

$\operatorname {Hom} _{\mathcal {D}}(a,b)=\operatorname {Hom} _{\mathcal {C}}(a,b)$.

Proposition (limits are preserved when restricting to a full subcategory):

Let ${\mathcal {C}}$ be a category, let $J:{\mathcal {J}}\to {\mathcal {C}}$ be a diagram in ${\mathcal {C}}$, and let ${\mathcal {D}}$ be a full subcategory of ${\mathcal {C}}$. Suppose that $(L,(\phi _{\alpha })_{\alpha \in A})$ is a limit over $J$ in ${\mathcal {C}}$ such that $L$ and all targets of the $\phi _{\alpha }$ are in ${\mathcal {D}}$. Then $(L,(\phi _{\alpha })_{\alpha \in A})$ is a limit over $J$ in ${\mathcal {D}}$.

Proof: Certainly, the underlying cone of $(L,(\phi _{\alpha })_{\alpha \in A})$ is contained within ${\mathcal {D}}$, because the subcategory is full. Now let another cone $(Q,(\psi _{\alpha })_{\alpha \in A})$ in ${\mathcal {D}}$ over the diagram $J$ (which, analogously, is a diagram in ${\mathcal {D}}$) be given. By the universal property of $(L,(\phi _{\alpha })_{\alpha \in A})$ in ${\mathcal {C}}$, there exists a unique morphism $f:Q\to L$ which satisfies $\psi _{\alpha }=\phi _{\alpha }\circ f$ for all $\alpha \in A$. Since ${\mathcal {D}}$ is full, $f$ is in ${\mathcal {D}}$. $\Box$

Analogously, we have:

Proposition (colimits are preserved when restricting to a full subcategory):

Let ${\mathcal {C}}$ be a category, let $J:{\mathcal {J}}\to {\mathcal {C}}$ be a diagram in ${\mathcal {C}}$, and let ${\mathcal {D}}$ be a full subcategory of ${\mathcal {C}}$. Suppose that $(C,(\phi _{\alpha })_{\alpha \in A})$ is a colimit over $J$ in ${\mathcal {C}}$ such that $C$ and all domains of the $\phi _{\alpha }$ are in ${\mathcal {D}}$. Then $(C,(\phi _{\alpha })_{\alpha \in A})$ is a colimit over $J$ in ${\mathcal {D}}$.

Proof: This follows from its "dual" proposition, reversing all arrows in its statement and proof except the direction of the diagram functor. $\Box$

Categories of ordered sets

Definition (category of preordered sets):

The category ${\textbf {Ord}}$ of preordered sets is the category whose objects $\operatorname {Ob} ({\textbf {Ord}})$ are given by the preordered sets and whose morphisms are given by the order homomorphisms.

Definition (category of posets):

The category ${\textbf {Pos}}$ of posets is the category whose objects are the posets and whose morphisms are the order homomorphisms.

Directly from the definitions, we have:

Proposition (posets form full subcategory of preordered sets):

${\textbf {Pos}}$ is a full subcategory of ${\textbf {Ord}}$.

Proposition (products in the category of preordered sets):

Let $(S_{\alpha })_{\alpha \in A}$ be a family of preordered sets. Then a product of this family in the category ${\textbf {Ord}}$ is given by the set $\prod _{\alpha \in A}S_{\alpha }$ together with the product order, where the projections are given by the functions

$p_{\beta }:\prod _{\alpha \in A}S_{\alpha }\to S_{\beta },p_{\beta }((s_{\alpha })_{\alpha \in A})=s_{\beta }$.

Proof: The functions $p_{\beta }$ are order homomorphisms, because if $\beta \in A$ and $(s_{\alpha })_{\alpha \in A}\leq (t_{\alpha })_{\alpha \in A}$, then $p_{\beta }((s_{\alpha })_{\alpha \in A})=s_{\beta }\leq t_{\beta }=p_{\beta }((t_{\alpha })_{\alpha \in A})$ by definition. Thus, we have a cone. Moreover, if the order homomorphisms $q_{\alpha }:Q\to S_{\alpha }$ define another cone, then as for the set product, the function given by

$f:Q\to \prod _{\alpha \in A},f(x)=(q_{\alpha }(x))_{\alpha \in A}$

is the unique function from $Q$ to $\prod _{\alpha \in A}S_{\alpha }$ such that $q_{\alpha }=p_{\alpha }\circ f$ for all $\alpha \in A$, and it is an order homomorphism, because if $x\leq y$, then for all $\alpha \in A$ we have $q_{\alpha }(x)\leq q_{\alpha }(y)$. $\Box$

Proposition (coproducts in the category of preordered sets):

Let $(S_{\alpha })_{\alpha \in A}$ be a family of preordered sets. Then a coproduct of this family in the category ${\textbf {Ord}}$ is given by the parallel composition of the $S_{\alpha }$, where the inclusions are given by the functions

$i_{\beta }:S_{\beta }\to \bigsqcup _{\alpha \in A}S_{\alpha },i_{\beta }(s_{\beta })=(s_{\beta },\beta )$.

Proof: The $i_{\beta }$ are order homomorphisms by definition of the parallel order, so that we do have a cocone. Suppose now that the maps $j_{\alpha }:S_{\alpha }\to D$ define another cocone in the category ${\textbf {Ord}}$. Then the unique function $f:\bigsqcup _{\alpha \in A}S_{\alpha }\to D$ such that $f\circ i_{\alpha }=j_{\alpha }$ for all $\alpha \in A$ is given by

$f:\bigsqcup _{\alpha \in A}S_{\alpha }\to D,f((s,\alpha ))=j_{\alpha }(s)$

as in set theory, and it is an order homomorphism because if $(s,\beta )\leq (t,\beta )$, then $s\leq _{\beta }t$ by def. of the parallel order and consequently $f((s,\beta ))=j_{\beta }(s)\leq j_{\beta }(t)=f((t,\beta ))$. $\Box$

Proposition (products and coproducts in the category of posets):

In the category $\mathbf {Pos}$, products and coproducts are given by the respective products and coproducts in the category $\mathbf {Ord}$.

Proof: This follows since limits and colimits are preserved when restricting to a full subcategory. $\Box$

Additive categories

Definition (biproduct):

Let ${\mathcal {C}}$ be a category, and let $(X_{\alpha })_{\alpha \in A}$ be a family of objects in ${\mathcal {C}}$. A biproduct of $(X_{\alpha })_{\alpha \in A}$ is an object of ${\mathcal {C}}$ that is usually denoted as

$\bigoplus _{\alpha \in A}X_{\alpha }$

and for which there exist arrows

$\iota _{\alpha }:X_{\alpha }\to \bigoplus _{\alpha \in A}X_{\alpha }$ and $\pi _{\alpha }:\bigoplus _{\alpha \in A}X_{\alpha }\to X_{\alpha }$

for all $\alpha \in A$ that have the following properties:

1. $\alpha \neq \beta \Rightarrow \pi _{\alpha }\circ \iota _{\beta }=0$ and $\forall \alpha \in A:\pi _{\alpha }\circ \iota _{\alpha }=\operatorname {Id} _{X_{\alpha }}$
2. $\bigoplus _{\alpha \in A}X_{\alpha }$, together with the morphisms $(\iota _{\alpha })_{\alpha \in A}$, constitutes a coproduct in the category ${\mathcal {C}}$
3. $\bigoplus _{\alpha \in A}X_{\alpha }$, together with the morphisms $(\pi _{\alpha })_{\alpha \in A}$, constitutes a product in the category ${\mathcal {C}}$

Definition (additive category):

An additive category is a category ${\mathcal {C}}$ that satisfies each of the following requirements:

1. Every morphism in ${\mathcal {C}}$ has a kernel and a cokernel
2. For every two objects $X,Y$ of ${\mathcal {C}}$, there exists a biproduct $X\oplus Y$
3. For every two objects $X,Y$ of ${\mathcal {C}}$, the assignment $(f,g)\mapsto h$, where $h:X\to Y$ is the morphism that arises from postcomposing the morphism $X{\overset {\Delta }{\to }}X\oplus X{\overset {f\times g}{\to }}Y\oplus Y$ (where $\Delta$ shall denote the diagonal) with the anti-diagonal $\nabla :Y\oplus Y\to Y$, turns $\operatorname {Hom} (X,Y)$ into an abelian group

Abelian categories

Proposition (object in abelian category is decomposed into sum by subobject):

Let ${\mathcal {C}}$ be an abelian category, and let $X\in {\mathcal {C}}$ be an object. Let $f:Y\to X$ be a subobject, and let $Z=\operatorname {Coker} f$ be the corresponding quotient object. Moreover, denote $g=\operatorname {coker} f$. Then there exists a unique isomorphism $\theta :X\to Y\oplus Z$ such that

$\pi _{Z}\circ \theta =g$ and $\theta ^{-1}\circ \iota _{Y}=f$.

Proof: $Y\oplus Z$ is a biproduct. First we apply the universal property of a product in order to obtain a morphism

$\phi :X\to Y\oplus Z$ such that $\pi _{Z}\circ \phi =g$ and $\pi _{Y}\circ \phi =0$.

Then we apply the universal property of a coproduct in order to obtain a morphism

$\chi :Y\oplus Z\to X$ such that $\chi \circ \iota _{Y}=f$ and $\chi \circ \iota _{Y}=0$.

Moreover, we get a morphism $Y\otimes X\to Y\otimes 0$ from the projection to $Y$, and a morphism $0\otimes Z\to Y\oplus Z$ from the inclusion of $Z$. The latter morphism is the kernel of ${\tilde {f}}:Y\oplus Z\to X$, and the cokernel of that kernel is $\Box$

Categories

This is the Categories chapter of Category Theory.

Definition

A category ${\mathcal {C}}$ consists of four kinds of data subject to three axioms, as listed below:

Data

Objects

${\mathcal {C}}$ has objects denoted by $A$, $B$, $C$,…

Morphisms

For each ordered pair of objects $A$, $B$ in ${\mathcal {C}}$, there is a class of morphisms or arrows from $A$ to $B$. The notation $f:A\to B$ means that $f$ is a morphism from $A$ to $B$. The class of all morphisms from $A$ to $B$ is denoted by ${\text{Hom}}_{\mathcal {C}}(A,B)$ or sometimes simply ${\mathcal {C}}(A,B)$.

Composition

For each ordered triple of objects $A$, $B$, $C$ in ${\mathcal {C}}$, there is a law of composition: If $f:A\to B$ and $g:B\to C$, then the composite of $f$ and $g$ is a morphism $gf:A\to C$

Identity

For each object $A$ there is a designated identity morphism on $A$, notated as $1_{A}$, from $A$ to $A$.

Axioms

These data satisfy the following three axioms, of which the first is in the nature of a convention, while the remaining two are more substantial:

Unique typing

${\text{Hom}}(A_{1},B_{1})$ and ${\text{Hom}}(A_{2},B_{2})$ are disjoint unless $A_{1}=A_{2}$, $B_{1}=B_{2}$.

Associative Law

$h(gf)=(hg)f$ if the composites are defined. Note that if one composite is defined, the other is necessarily defined.

Identity is a “neutral element”

For the identity morphism $1_{B}:B\to B$ associated to each object $B$, two equations must hold for each pair of objects $A$ and $C$ and each pair of arrows $f:A\to B$, $g:B\to C$:

• $1_{B}\,f=f$
• $g\,1_{B}=g$

Terminology and fine points

• If $f:A\to B$ in a category, $A$ is called the domain or source of $f$, and $B$ is called the codomain or target of $f$.
• ${\text{Hom}}(A,B)$ is called a hom class (or a hom set if it is indeed a set). In general a hom set may be empty, but for any object $A$, ${\text{Hom}}(A,A)$ is not empty because it contains the identity morphism.
• The hom class ${\text{Hom}}(A,B)$ may be denoted by ${\text{Hom}}_{\mathcal {C}}(A,B)$ or ${\mathcal {C}}(A,B)$ if it is necessary to specify which category is referred to.
• An object in a category need not be a set; the object need not have anything called elements.
• Morphisms may also be called maps. This does not mean that every morphism in any category is a set function (see #Baby examples and #Preorders). Arrow is a less misleading name.
• The composite $gf$ may be written $g\circ f$.
• It might be more natural to write the composite of $f:A\to B$ and $g:B\to C$ as $fg$ instead of $gf$ but the usage given here is by far the most common. This stems from the fact that if the arrows are set functions and $x\in A$, then $(gf)(x)=g(f(x))$. Thus $gf$ is best read as "do $g$ after $f$".

Large and small

The definition says that a category 'has' objects and 'has' morphisms. This means that for any category ${\mathcal {C}}$ and $X$ is any mathematical object, the statement '$X$ is an object of ${\mathcal {C}}$' is either true or false, and similarly for the statement '$X$ is a morphism of ${\mathcal {C}}$'. The objects (or arrows) of a category need not constitute a set. If they do, the category is said to be small. If they don't, the category is large.

The requirement that the collection of morphisms from $A$ to $B$ be a set makes a category locally small. In this book, all categories are locally small.

Discrete

A category is discrete if every morphism is an identity.

Preorder

A category ${\mathcal {P}}$ is a preorder if for every pair of objects $P,P'$, there exists at most one morphism $f:P\to P'$.

Examples of categories

Baby examples

These examples are trivial and maybe uninteresting. But do not underestimate the power of baby examples. For one thing, they are sometimes counterexamples to possible theorems.

0 (the empty category)

This category has no objects and no morphisms.

1

The category 1 has one object and one morphism, which must necessarily be the object's identity arrow.

1+1

This category has two objects and two morphisms: the identities on each object.

2

This category has two objects and three morphisms. The third morphism goes from one object to the other.

Remarks

• The objects of these baby categories are nodes in a graph (not sets) and the morphisms are arrows in the graph (not functions).
• For these baby categories we don't have to say what the composition operation does: it is always forced.
• It is impolite to say that categorists think that 1 + 1 is not equal to 2.

The category of sets

The category of sets, denoted by Set, is this category:

• The objects are all sets
• A morphism from a set $A$ to a set $B$ is a function with domain $A$ and codomain $B$.
• The composition is the usual composition: If $f:A\to B$ and $g:B\to C$ then $gf:A\to C$ is defined by $gf(x)=g(f(x))$ for all $x\in A$.
• The identity morphism $1_{A}$ on a set $A$ is the identity function defined by $1_{A}(x)=x$ for $x\in A$.

Terminology and fine points

• In order to preserve the unique typing in a function definition, it is necessary to include its codomain. For example, $1_{A}:A\to A$ is a different function from the inclusion function $i:A\to B$ to some set $B$ properly including $A$.
• In most approaches to the foundations of math, the collection of all sets is not a set. This makes Set a large category. However, it is still locally small since the class of all functions between two sets, $A$ and $B$ is a subclass of the power set of their Cartesian product $A\times B$ which is by definition a set.

Mathematical structures as categories

Preorders

A preorder $\preccurlyeq$ on a set $A$ is a reflexive and transitive relation on $A$, which means that for all $a\in A$, $a\preccurlyeq a$ and for all $a$, $b$, $c$ in $A$, if $a\preccurlyeq b$ and $b\preccurlyeq c$, then $a\preccurlyeq c$.

A preorder "is" a category in the following sense: Given a preorder ($A$, $\preccurlyeq$) the category structure is this:

• The objects of the category are the elements of $A$.
• There is exactly one morphism from $a$ to $b$ if and only if $a\preccurlyeq b$.

The existence of identities is forced by reflexivity and the composition law is forced by transitivity. It follows that the category structure has the property that there is at most one morphism from any object $a$ to any object $b$.

Conversely, suppose you have a category with set $A$ of objects, with the property that there is at most one morphism between any two objects. Define a relation $\preccurlyeq$ on $A$ by requiring that $a\preccurlyeq b$ if and only if there is a morphism from $a$ to $b$. Then ($A$, $\preccurlyeq$) is a preorder.

The statements in the two preceding paragraphs describe an equivalence of categories between the category of small categories with at most one morphism between any two objects and all functors between such categories, and the category of preorders and order-preserving maps.

Remark: Given a preorder, the morphisms of the corresponding category exist by definition. There is exactly one morphism from $a$ to $b$ if and only if $a\preccurlyeq b$. This is an axiomatic definition; in a model a morphism from $a$ to $b$ could be anything, for example the pair ($a$, $b$). In no sense is the morphism required to be a function.

Groups

Every group $G$ can be viewed as a category ${\mathcal {G}}$ as follows: ${\mathcal {G}}$ has one single object; call it $e$. Therefore it has only one homset ${\text{Hom}}_{\mathcal {G}}(e,e)$, which is defined to be the underlying set of the group $G$ (in other words, the arrows are the group elements.) We take as composition the group multiplication. It follows that the identity element of $G$ is $1_{e}$. Notice that in the category ${\mathcal {G}}$, every morphism is an isomorphism (invertible under composition). Conversely, any one-object category in which all arrows are isomorphisms can be viewed as a group; the elements of the group are the arrows and the multiplication is the composition of the category. This describes an equivalence between the category of groups and homomorphisms and the category of small categories with a single object in which every morphism is an isomorphism.

This can be generalized in two ways.

A category ${\mathcal {G}}$ is called a groupoid if every morphism is an isomorphism. Thus a groupoid can be called "a group with many objects."

A monoid is a set with an associative binary operation that has an identity element. By the same technique as for groups, any monoid "is" a category with exactly one object and any category with exactly one object "is" a monoid.

Matrices

This is a good example of a category whose objects are not sets and whose arrows are not functions. $\mathbf {Matr} _{K}$ is the category whose objects are the positive integers and whose arrows $A:n\to m$ are $m\times n$ matrices where composition is matrix multiplication, for any commutative ring $K$. For any object $n$, $1_{n}=I_{n}$, the $n\times n$ identity matrix.

Categories of sets with structure

finite sets and functions; denoted FinSet.

monoids and morphisms; denoted Mon.

groups and homomorphisms; denoted Grp.

abelian groups and homomorphisms; denoted Ab.

rings and unit-preserving homomorphisms; denoted Rng.

commutative rings and unit-preserving homomorphisms; denoted CRng.

left modules over a ring $R$ and linear maps; denoted $R$-Mod.

right modules over a ring $R$ and linear maps; denoted Mod-$R$.

modules over a commutative ring $K$ and linear maps; denoted $K$-Mod.

subsets of Euclidean space of 3 dimensions and Euclidean movements

subsets of Euclidean space of n dimensions and continuous functions

topological spaces and continuous functions; denoted Top.

topological spaces and homotopy classes of functions; denoted Toph.

Remarks

The law of composition is not specified explicitly in describing these categories. This is the custom when the objects have underlying set-structure, the morphisms are functions of the underlying sets (transporting the additional structure), and the law of composition is merely ordinary function-composition. Indeed, sometimes even the specification of the morphisms is suppressed if no confusion would arise—thus one speaks of the category of groups.

The examples of sets with structure suggest a conceptual framework. For example, the concept of group may be regarded as constituting a first-order abstraction or generalization from various concrete, familiar realizations such as the additive group of integers, the multiplicative group of nonzero rationals, groups of permutations, symmetry groups, groups of Euclidean motions, and so on. Then, again, the notion of a category constitutes a second-order abstraction, the concrete realizations of which consist of such first-order abstractions as the category of groups, the category of rings, the category of topological spaces, and so on.

Properties of objects and morphisms

Isomorphisms

A morphism $f:A\to B$ in a category is said to be an isomorphism if there is a morphism $g:B\to A$ in the category with $gf=1_{A}$, $fg=1_{B}$. It is easy to prove that $g$ is then uniquely determined by $f$. The morphism $g$ is called the inverse of f, written $g=f^{-1}$. It follows that $f=g^{-1}$. If there is an isomorphism from $A$ to $B$, we say $A$ is isomorphic to $B$, and it is easy to prove that "isomorphism" is an equivalence relation on the objects of the category.

Examples

• A function from $A$ to $B$ in the category of sets is an isomorphism if and only if it is bijective.
• A homomorphism of groups is an isomorphism if and only if it is bijective.
• The isomorphisms of the category of topological spaces and continuous maps are the homeomorphisms. In contrast to the preceding example, a bijective continuous map from one topological space to another need not be a homeomorphism because its inverse (as a set function) may not be continuous. An example is the identity map on the set of real numbers, with the domain having the discrete topology and the codomain having the usual topology.

Monomorphisms and Epimorphisms

A morphism $f$ in a category ${\mathcal {C}}$ is a monomorphism if, for any morphisms $g$ and $h$, if $fg$ and $fh$ are defined and $fg=fh$ then $g=h$.

A morphism $f$ in a category ${\mathcal {C}}$ is an epimorphism if, for any morphisms $g$ and $h$, if $gf$ and $hf$ are defined and $gf=hf$ then $g=h$.

Initial and terminal objects

$T$ is said to be a terminal (or final) object when $X\to T$ is a unique morphism for any $X$ in ${\mathcal {C}}$. The law of composition ensures that if $T$ and $T'$ are terminal objects in ${\mathcal {C}}$, they are isomorphic, i.e., $T(')$ is unique up to isomorphism. In the categories of sets, groups, and topological spaces, the terminal objects are singletons, trivial groups, and one-point spaces, respectively. "b" is the terminal object in 2 as depicted above.

Constructions on categories

Subcategories

A subcategory ${\mathcal {S}}$ of a category ${\mathcal {C}}$ is a category in which:

• The class of objects of ${\mathcal {S}}$ is contained in the class of objects of ${\mathcal {C}}$.
• The class of arrows of ${\mathcal {S}}$ is contained in the class of arrows of ${\mathcal {C}}$.
• For every arrow $f$ in ${\mathcal {S}}$, the domain and codomain of $f$ are in ${\mathcal {S}}$.
• For every object $s$ in ${\mathcal {S}}$, the identity arrow $1_{s}$ is in ${\mathcal {S}}$.
• For every pair of arrows $f,g$ in ${\mathcal {S}}$, the arrow $g\circ f$ is in ${\mathcal {S}}$ where it is defined.

Opposite category

Given a category ${\mathcal {C}}$, the opposite (or dual) category ${\mathcal {C}}^{\text{op}}$ has the same objects as ${\mathcal {C}}$ and for every arrow $f:a\to b$ in ${\mathcal {C}}$, the arrow $f^{\text{op}}:b\to a$ is in ${\mathcal {C}}^{\text{op}}$. In other words, it has the same objects, and arrows are reversed.

The product of two categories

Given two categories ${\mathcal {B}}$ and ${\mathcal {C}}$, the product category, denoted ${\mathcal {B}}\times {\mathcal {C}}$, is given by the following data:

• The objects of ${\mathcal {B}}\times {\mathcal {C}}$ are $(b,c)$ where $b$ is an object of ${\mathcal {B}}$ and $c$ is an object of ${\mathcal {C}}$.
• The arrows of ${\mathcal {B}}\times {\mathcal {C}}$ are $(f,g)$ where $f$ is an arrow of ${\mathcal {B}}$ and $g$ is an arrow of ${\mathcal {C}}$.
• Composition is given by $(f',g')\circ (f,g)=(f'\circ f,g'\circ g)$.

The product ${\mathcal {C}}\times \mathbf {2}$ is called the cylinder category, denoted ${\text{Cyl}}({\mathcal {C}})$.

Arrow categories

• A functor category ${\mathcal {B}}^{\mathcal {C}}$ is a category whose objects are functors $T:{\mathcal {C}}\to {\mathcal {B}}$ and arrows are natural transformations.
• A functor category ${\mathcal {C}}^{\mathbf {2} }$ is called an arrow category, denoted ${\mathcal {C}}^{\rightarrow }$. Its objects are arrows $f:a'\to b'$ in ${\mathcal {C}}$ and its arrows are pairs of arrows $(h,k):f\to f'$ such that $f'\circ h=k\circ f$.

Comma categories

• Given categories and functors $T:{\mathcal {E}}\to {\mathcal {C}}$ and $S:{\mathcal {D}}\to {\mathcal {C}}$, the comma category $(T\downarrow S)$ has objects $(e,d,f)$ where $e$ is an object in ${\mathcal {E}}$, $d$ is an object in ${\mathcal {D}}$, and $f:Te\to Sd$ is an arrow in ${\mathcal {C}}$. Its arrows are $(k,h):(e,d,f)\to (e',d',f')$ where $k:e\to e'$ is an arrow in ${\mathcal {E}}$ and $h:d\to d'$ is an arrow in ${\mathcal {D}}$ such that $Sh\circ f=f'\circ Tk$. Composition is given by $(k,h)\circ (k',h')=(k\circ k',h\circ h')$. The identity is $1_{(e,d,f)}=(1_{e},1_{d})$.

Special types of comma categories

Using the definition of comma category above, assume that we have ${\mathcal {D}}=\mathbf {1}$, ${\mathcal {E}}={\mathcal {C}}$, and $T=1_{\mathcal {C}}$. Let $1$ denote the object in $\mathbf {1}$. Then $S1=A$ for some object $A$ in ${\mathcal {C}}$. In this case, we write the comma category as $({\mathcal {C}}\downarrow A)$ and call it the slice category of $A$ (or the category of objects over $A$).

Now assume, instead, that we have ${\mathcal {E}}=\mathbf {1}$, ${\mathcal {D}}={\mathcal {C}}$, and $S=1_{\mathcal {C}}$. Let $1$ denote the object in $\mathbf {1}$. Then $T1=A$ for some object $A$ in ${\mathcal {C}}$. In this case, we write the comma category as $(A\downarrow {\mathcal {C}})$ and call it the coslice category of $A$ (or the category of objects under $A$).

Finally, if we have ${\mathcal {E}}={\mathcal {D}}={\mathcal {C}}$ and $T=S=1_{\mathcal {C}}$, then the comma category $(1_{\mathcal {C}}\downarrow 1_{\mathcal {C}})={\mathcal {C}}^{\rightarrow }$.