Category theory

Categories

Since the mid-1940s mathematicians have found it valuable to formalize the notions of areas of mathematical discourse and interrelations between such areas; the formalization used is the language of categories and functors. A rapidly developing mathematical theory accompanied this formalization so that the theory of categories and functors has become an autonomous part of mathematics. This section deals with the role of this formalization in providing an appropriate language for the expression of mathematical ideas.

The study of mathematics involves certain domains of mathematical discourse, their structural properties, and their interrelations. For example, there is the idea of a set (see set theory) and of functions that are transformations of sets. There is arithmetic, the study of the domain of natural numbers, rational numbers, and integers. Geometry involves subsets of Euclidean space of three dimensions together with the appropriate transformations of such subsets—for example, translations, rotations, and reflections. Algebra is concerned with rational numbers, real numbers, and complex numbers; and abstract algebra involves further mathematical domains such as groups, rings, fields, and lattices. The calculus is again concerned in the first instance with subsets of the real numbers, or of Euclidean space of higher dimension, and with particular transformations of such subsets; e.g., differential operators.

Algebraic topology relates domains of interest in geometry to domains of interest in algebra. Algebraic geometry, on the other hand, goes in the opposite direction, associating, for example, with each commutative ring its spectrum of prime ideals.

Set theory is concerned with a class of objects A, B, C, … called sets, and a class of transformations f, g, h, … called functions. With each function f is associated a domain, which is a set A, and a range or codomain, which is a set B. The notation f: A → B, or A →_f B, indicates that f is a function from the domain A to the codomain B. There is a strict distinction between the codomain of the function f and the image of the function f, which is simply the set of values taken by the function f. Thus, in particular, two functions can only be identical if not only their domains but also their codomains coincide. They are then, of course, identical if, and only if, they each take the same value at each element of the domain.

Further, functions may be composed under certain conditions. To be precise, the functions f: A → B and g: B¢ → C may be composed to yield a function, written gf or g f (see 339), if, and only if, B = B¢. Further, the law of composition is associative (see 340), provided, of course, that the relevant compositions are defined. With each set A may be associated its identity function 1_A: A → A. This function 1_A has basic properties (see 341) provided the compositions are defined. Thus, 1_A behaves very much like the integer 1 in the ring of integers, a fact that leads to the habit of dropping the subscript A and simply writing 1: A → A. It is an easy exercise to see that the identity function is entirely characterized by the properties of 1_A (see 341). That is to say, if the function u: A → A also satisfies the conditions fu = f, ug = g for all appropriate f, g, then indeed u = 1_A.

Of course set theory has more structure than this, but if the ideas described above are abstracted from set theory, a model for the notion of a category is obtained.

The notion of a category

A formal definition can be given in the following way: A category $𝒞$ consists of the below families of data:

Basic concepts

Objects

There is a class of objects A, B, C,…

Morphisms

To each ordered pair of objects A, B in $𝒞$, there is associated a set (see 342) called the hom-set: the set of morphisms, or maps or transformations, from A to B in $𝒞$, notated as ${\mathrm{H}\mathrm{o}\mathrm{m}}_{𝒞}(A,B)$. For short, we often write $f:A{\to }_{𝒞}B$ meaning $f\in {\mathrm{H}\mathrm{o}\mathrm{m}}_{𝒞}(A,B)$.

Composition

To each ordered triple of objects A, B, C in $𝒞$, there is associated a law of composition, or composition function (see 343), the image of (f, g), f (A, B), g (B, C), under this law of composition being written gf or g f, so that gf is a morphism from A to C.

Identity

To each object A among the morphism from A to A itself, there is a designated one, notated as $1_A$. In generally, we say nothing about whether there are any $A\to A$ morphisms more, but at least this $1_A$ must exist, and we can always “call it by name”. We shall see below what equations are required for $1_A$ to hold.

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

(A₁,B₁) and (A₂,B₂) are disjoint unless A₁ = A₂, B₁ = B₂.

Associative Law

h(gf) = (hg)f, provided the compositions are defined.

Identity behaves analogously to a “neutral element”

For the identity morphism $1_B:B\to B$ associated to each object B, two equations must hold for each A, C, $f:A\to B$, $g:B\to C$ (see 344) provided the compositions are defined:

• $1_B\circ f=f$
• $g\circ 1_B=g$

Examples

As a first example, the category Set is considered, called the category of sets and functions, or simply the category of sets. Precisely, the objects of are sets A, B, C, … A morphism in from the set A to the set B is merely a function with domain A and codomain (not necessarily image!) B. Thus either of two notations (see 345) can be adopted in an arbitrary category as a convenient representation of the statement f (A, B). The law of composition in is simply the familiar composition of functions. The axioms are then certainly satisfied. Moreover, this example serves to explain the notation gf for the composition of f: A → B with g: B → C. It is usual to write functions on the left of their arguments, so that the image of A A under the composite of f and g appears as g (f (A)). A less conservative attitude, defying this tradition and leading to a happier notation, would be to write fg for the composite of f and g, especially in view of the natural notational convention (see 346). In this discussion, however, tradition is not defied.

Just as in the special case of the category , the equations relating to the identities (344) entirely determine the morphism 1_A in (A, A); 1 is often written for 1_A.

Some further examples of categories follow: finite sets and functions; groups and homomorphisms; Abelian groups and homomorphisms; rings and homomorphisms; 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.

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 given 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.

It should not be supposed that, in every category, the objects are sets (probably with additional structure) and that the morphisms are certain preferred functions. One example serves to dispel this misconception. X is a set with a pre-ordering relation ≥. Thus the relation A ≥ B holds for certain elements a, B of X and the following axioms are satisfied: A ≥ A; if A ≥ b, b ≥ c, then A ≥ C. For example, the integers may be ordered by size or they may be preordered by the divisibility condition: A|B if A is a factor of B. Then if (X, ≥) is a set with a pre-order, a category X is formed, the objects of which are the elements of X and such that X(a, b) is the single element A → B if A ≥ B and is empty otherwise. There is evidently a unique law of composition and the category axioms obviously hold.

A morphism f: A → B in the category is said to be invertible, or a unit, or an equivalence, if there is a morphism g: B → A in with gf = 1_A, fg = 1_B. It is easy to prove that g is then invertible and is determined by f (g is the inverse of f, written g = f -1), and that if A is isomorphic to B, there existing an invertible f: A → B, then the relation of isomorphism is an equivalence relation on the objects of . Thus every category carries automatically with it a notion of the isomorphism of objects, proper to that category. The concept gives a great gain in universality compared with traditional procedures, which involve the definition, as distinct concepts, of one–one correspondence between sets, isomorphism between groups, isomorphism between rings, homeomorphism between topological spaces, bi-continuous isomorphism between topological groups, order type of ordered sets, and so on. It is particularly offensive, from the categorical point of view, to define an isomorphism of groups f: g → h to be a homomorphism that is one–one and onto H; for an isomorphism of groups should be just an invertible morphism of the category of groups. It is a theorem that, in this category, a morphism that is one–one and onto its codomain is an isomorphism. This theorem is false in the category of topological spaces, so that the definition masks the universality of the concept of isomorphism.

Functors

The notion of category being established as that which gives precision to the concept of domain of mathematical discourse, the formalization of the precise notion corresponding to the intuitive idea of the interrelation or connection between different domains is now considered. Within any particular category not only the objects must be specified but also the morphisms. Furthermore, these morphisms are, in the principal examples, required in some sense to transport the structure characteristic of the objects of the category; e.g., group structure, topological structure. In the same way a functor $\mathrm{\Phi }$ from the category $𝒞$ to the category $𝒟$ is defined as a rule that associates with every object A of $𝒞$ an object $\mathrm{\Phi }(A)$ of $𝒟$, and with every morphism $f:A{\to }_{𝒞}B$ a morphism $\mathrm{\Phi }(f):\mathrm{\Phi }(A){\to }_{𝒟}\mathrm{\Phi }(B)$, subject to the conditions of transport of structure (see 347, 348):

$\mathrm{\Phi }(1_{𝒞,A})=1_{𝒟,\mathrm{\Phi }(A)}$

$\mathrm{\Phi }(g{\circ }_{𝒞}f)=\mathrm{\Phi }(g){\circ }_{𝒟}\mathrm{\Phi }(f)$

In expressing the relation (347), there is a tacit assumption that the composition fb is defined. This is standard practice, to avoid unnecessarily complicated statements.

A functor f always sends isomorphisms to isomorphisms, a very crucial property. Otherwise expressed, if Ff is not an isomorphism, then f cannot be an isomorphism. This yields a basic methodological procedure; to demonstrate that A and B, two objects of , really are different—i.e., non-isomorphic—it may be possible to find a functor f from to a category in which it is far easier to make the comparison. This procedure may be regarded as a massive generalization of the classical arithmetical test of casting out nines.

Some examples of functors are now given:

• For any group $𝔊$ it is possible to render $𝔊$ commutative by adjoining the relations xy = yx for all x, y in its universe G. The resulting group may be written ${𝔊}_{\mathrm{a}\mathrm{b}}$. If $f:𝔊{\to }_{𝐆𝐫𝐩}ℌ$ is a homomorphism (in the category of groups notated as Grp), it is easy to see that f induces a uniquely determined homomorphism $f_{\mathrm{a}\mathrm{b}}:{𝔊}_{\mathrm{a}\mathrm{b}}{\to }_{𝐀𝐛}{ℌ}_{\mathrm{a}\mathrm{b}}$ in the category of Abelian groups (notated as Ab). Thus there is a functor from the category of groups Grp to the category of Abelian groups Ab. This should be the first functor tried in an attempt to prove two groups nonisomorphic.
• For any pointed topological space (X, x)—that is, a topological space X, together with a distinguished point X in X—it is possible to construct the Poincaré fundamental group p(X, x). Then p is a functor from the category of pointed topological spaces and pointed continuous functions to the category of groups. Because, for example, the sphere and the torus (a surface in the shape of a doughnut) have non-isomorphic fundamental groups, it follows that they are not homeomorphic.
• If x, y are two pre-ordered sets regarded as categories, as above, then a functor from X to Y is merely an order-preserving function.
• There are many important functors, called forgetful or underlying functors, that simply forget part of the structure present in the objects and transported by the morphisms. Thus, the objects in the examples in The notion of a category all have underlying set structures and the morphisms are all functions; moreover, the law of composition is simply that of functions. Thus, in all these cases, there is an underlying functor to . It is also possible to take a ring, forget the multiplication in it, and thereby obtain an Abelian group; this yields an underlying functor. Underlying functors may seem trivial things; actually, they are fundamental to categorical language.

Natural transformations

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 V be a vector space over some field K, and let V* be the dual space of V; that is, the space of linear functionals on V. There is then a linear transformation T: V → V** that is given (see 349). There is an intuitive feeling that the linear transformation T is natural because its description only involves the terms u and f. Now if V is finite-dimensional, then it is known that T is an isomorphism in the category of vector spaces over K and linear transformations. One way of proving that T is then an isomorphism is to show that V and V** are isomorphic and then to observe that T is one–one. The usual proof that V and V** are isomorphic would be to proceed by establishing an isomorphism between V and V*, in the case when V is finite-dimensional. Now if a base $(e_1,e_2,\dots ,e_K)$ for V is given, then a basis for V* may be set up, called the dual basis, by defining ei* to be that linear functional on V given by certain rules (see 350). Then the correspondence ei « ei* sets up an isomorphism between V and 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 V to V* even if V is not finite-dimensional over K, 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 V over the field K, V and V** are naturally isomorphic, while V and 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 may be said to have laid the foundation of the theory of categories.

Definition

The precise definition is:

If $\mathrm{\Phi },\mathrm{\Psi }:𝒞\to 𝒟$ (that is, $\mathrm{\Phi }$, $\mathrm{\Psi }$ are two functors, both from the category $𝒞$ to the category $𝒟$), then

• $\eta :\mathrm{\Phi }\to \mathrm{\Psi }$ (that is, a natural transformation $\eta$ from functor $\mathrm{\Phi }$ to functor $\mathrm{\Psi }$) is a rule that assigs to each object A of category $𝒞$ a morphism ${\eta }_A$ of the arrows of the category $𝒟$, typed as member of the hom-set from $\mathrm{\Phi }(A)$ to $\mathrm{\Psi }(A)$, that is, ${\eta }_A:\mathrm{\Phi }(A){\to }_{𝒟}\mathrm{\Psi }(A)$ (or with the hom-set notation, ${\eta }_A\in {\mathrm{H}\mathrm{o}\mathrm{m}}_{𝒟}(\mathrm{\Phi }(A),\mathrm{\Psi }(A))$ can be written);
• morover, the morphisms involved must subject to the condition that a diagram (see 351) should be commutative for every $f:A{\to }_{𝒞}B$ (note f is an arrow in category $𝒞$); that is, $\mathrm{\Psi }(f)\circ {\eta }_A={\eta }_B\circ \mathrm{\Phi }(f)$ (note the communicative diagram is drawn in category $𝒟$).

Natural isomorphism

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 $\mathrm{\Phi }$ to $\mathrm{\Psi }$, then ${\eta }^{-1}$, given by an equation (see 352), is a natural equivalence from functors $\mathrm{\Psi }$ to $\mathrm{\Phi }$. Thus the term equivalence used here is fully justified. Indeed, the functors from $𝒞$ to $𝒟$ 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. There are two functors from to , in which 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. If it is now written as TV, it is easy to check that T is a natural transformation from the identity functor to the functor **. If the subcategory f of 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.

Universal constructions

An important procedure that is made possible by the use of categorical language is the relation of apparently distinct concepts in various categories. Here an example is given, but it should be pointed out that the technique described is of extremely broad application.

In the category of sets, the notion of Cartesian product is vital. Its description, however, involves mention of the elements of the sets: the Cartesian product of the sets X and Y consists of the ordered pairs (x, y), X x, y Y. In a definition of the product of two objects in an arbitrary category, this definition cannot be imitated because, in the definition of a category, it is not required that the objects should be sets with elements. Therefore, a property of the Cartesian product X ´ Y must be found that characterizes the Cartesian product and that can be expressed in the language of categories. Such a property must be entirely expressible in terms of the data of a category: in terms of objects, morphisms, and composition of morphisms.

For any given set A and functions f: A → X, g: A → Y, there is a unique function h: A → X ´ Y such that equations involving two projections hold (see 355), in which p1: X ´ Y → X, p2: X ´ Y → Y are the projections. This is the clue to the generalization. For two objects X and Y of the category , the triple (Z; p1, p2) is taken to be a product of X and Y if p1: Z → X and p2: Z → Y are morphisms of , and if the universal property holds that, given any object A of and morphisms f: A → X, g: A → Y, there exists a unique morphism h: A → Z such that certain relations hold (see 355).

It is easy to prove that the triple (Z; p1, p2) is, essentially, uniquely determined by the universal property. This means that if (Z¢; p1¢, p2¢) is also a product, then there exists a unique isomorphism w: Z → Z¢ in such that two equalities hold (see 356). Therefore, it is permissible to speak of the product of X and Y in . Of course, X and Y do not necessarily have a product in . If they do have a product in , in the sense defined above, however, then that product is unique. Now the product may be sought in various other categories. For example, in the category of Abelian groups the product, as defined, characterizes the direct sum; in the category of topological spaces it characterizes the topological product. In any category corresponding to a pre-ordered set, the product characterizes the greatest lower bound. Thus, in particular, in the category corresponding to the natural numbers ordered by divisibility, the product is precisely the GCD. It is possible to prove that the product in any category in which it exists is associative in the following sense. Given three objects X1, X2, and X3, then there is an equivalence (see 357). This is, of course, a completely familiar—and trivial—fact for sets: in considering the Cartesian product of three sets, the way in which the sets are to be associated is not relevant. If a proof has been given that is valid in any category, however, it is immediately possible to deduce, for example, that the greatest common divisor satisfies associativity. That is, if a, b, c are any three natural numbers, then a relation involving the GCD holds (see 358). Here there are two points to be made. First, there was no apparent connection between this statement (358) and the statement that the Cartesian product of sets is associative. Second, by proving the statement in sufficient generality—i.e., at the categorical level—it is possible to obtain many more instances of the theorem than could have been obtained by simply being confined to the original category in which the definition of product was carried out; that is, the category of sets.

The duality principle

For any category a new category 0 can be formed by interchanging the domains and codomains of the morphisms of . More precisely, in the category 0 the objects are simply those of and the effect of interchange of domains is expressed in an equation (see 359). Moreover, the composition in 0 is simply that of , suitably interpreted. 0 is called the category opposite to ; notice that (0)0 = . 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 is simply the product in 0. 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 from to may be most simply defined as a functor from 0 to . Thus the association of the dual vector space V* with V yields a contravariant functor from .

Conclusion

Because the concept of a category is so general, it is to be expected that theorems provable for all categories will not usually be very deep. Consequently, many theorems of category theory are stated and proved for particular classes of categories. For example, homological algebra is concerned with Abelian categories, which exhibit features suggested by the category of Abelian groups. In mathematics one seeks generality and depth, but there is a certain conflict between these two aims because the more general the setting, the less likely that the results will be profound. The art of mathematics might be said to be that of finding the best possible compromise between these two aims. Further, a not unimportant purpose of the language of categories and categorical reasoning is to identify within a given argument that part which is trivial and separate it from the part which is deep and proper to the particular context. For example, in the study of the theory of the GCD, the fact that it is essentially unique simply follows from the uniqueness of the product in any category and is thus really trivial. Similarly, as has been demonstrated, the fact that it is associative is trivial. On the other hand, the fact that the GCD of the integers A and B can be expressed as a linear combination of A and B with integer coefficients—gcd(a, b) = ma + nb, m, n integers—is a much deeper fact that is special to the particular situation, or, at least, to a highly restricted class of situations.