This is a file in the archives of the Stanford Encyclopedia of Philosophy.

version history

Stanford Encyclopedia of Philosophy

A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

This document uses XHTML/Unicode to format the display. If you think special symbols are not displaying correctly, see our guide Displaying Special Characters.
last substantive content change

Category Theory

Category theory now occupies a central position not only in contemporary mathematics, but also in theoretical computer science and even in mathematical physics. It can roughly be described as a general mathematical theory of structures and sytems of structures. However, it is still evolving and the precise meaning of category theory, that is what it is in the end about, remains to be fully clarified. It is at the very least a very powerful language or conceptual framework which allows us to see, among other things, how structures of different kinds are related to one another as well as the universal components of a family of structures of a given kind. Beside its intrinsic mathematical interest and its role in the development of contemporary mathematics, thus as an object of study for the epistemology of mathematics itself, the theory is philosophically relevant in many other ways. As a general formal tool, it can be used to study and clarify fundamental concepts such as the concept of space, the concept of system or even the concept of truth. It can also be applied for the study of logical systems, which in this context are called "categorical doctrines", both at the syntactic level, and more generally the proof-theoretical level, and at the semantic level. As a framework, it is considered by many as constituting an alternative to set theory as a foundation for mathematics. As such, it raises many issues with respect to the nature of mathematical entities and mathematical knowledge. Thus, there is much for philosophers and philosophical logicians to learn, to use and to think about.

1. General Definitions, Examples and Applications

Categories are algebraic structures with many different complementary nature, e.g., geometric, logical, computational, combinatorial, just as groups are many-faceted algebraic structures. When categories were introduced by Eilenberg and Mac Lane in 1945, they were entirely auxiliary and were defined simply to provide a formal ground for functors and natural transformations. As such, and as Eilenberg and Mac Lane themselves recognized, they were at first entirely dispensable in practice. The very definition of a category changed through time and varied according to the choice of metamathematical framework one decided to work in and the goals one had. Eilenberg and Mac Lane first gave a purely abstract definition of a category, along the lines of an axiomatic definition of a group, but then soon after and for practical reasons, various mathematicians decided to define categories in a set-theoretical framework. (See, for instance Grothendieck 1957 or Freyd 1964.) An alternative, initiated by Lawvere already in his Ph.D. thesis in 1963 and developed in his paper published in 1966, consists in characterizing the category of categories and to stipulate that a category is an object of that universe. The latter approach, being presently developed by various mathematicians, logicians and mathematical physicists for different purposes, leads to what are now called "higher dimensional categories". (See, for instance, Baez 1997, Baez & Dolan 1998a, Batanin 1998, Leinster 2002, Hermida et. al. 2000, 2001, 2002.) The very definition of a category is not without philosophical importance, since one of the objections to category theory as a foundational framework is the claim that since categories are defined as sets, category theory cannot provide a philosophically enlightening foundation for mathematics.

In terms of collections, a category C can be described as a collection Ob, the objects of C, which satisfy the following conditions:

For every pair a, b of objects, there is a collection Mor(a, b), namely, the morphisms from a to b in C (when f is a morphism from a to b, we write f: ab);

For every triple a, b and c of objects, there is a partial operation from pairs of morphisms in Mor(a, b) X Mor(b, c) to morphisms in Mor(a, c), called the composition of morphisms in C
(when f: ab and g: bc, (g o f): ac is their composition);

For every object a, there is a morphism ida in Mor(a, a), called the identity on a.

Furthermore, morphisms have to satisfy two axioms:
Associativity: if f: ab, g: bc and h: cd, then h o (g o f) = (h o g) o f

Identity: if f: ab, then (idb o f) = f and (f o ida) = f.

One of the interesting features of category theory is that it provides a uniform treatment of the notion of structure. This can be seen, first, by considering the variety of examples of categories. Almost every known example of a mathematical structure with the appropriate structure preserving map yields a category. Thus, sets with functions between them constitute a category, usually called the category of sets. Groups with group homomorphisms constitute a category. Topological spaces with continuous maps constitute a category. Vector spaces and linear maps constitute a category. Differential manifolds with smooth maps constitute a category. And so on. It is important to note that what characterizes a category is its morphisms and not its objects. Thus, the category of topological spaces with open maps is a different category than the category of topological spaces with continuous maps. In particular, the latter will have different properties as a category than the former. The previous examples have something in common: the objects are all structured sets with structure preserving maps. However, any entity satisfying the conditions given in the definition is a category. Thus, any preordered set is a category. For, given two elements p, q of the preordered set, there is a morphism f: pq if and only if p is less than or equal to q. Hence, a preordered set is a category in which there is at most one morphism between any two objects. A deductive system such that the entailment relation is reflexive and transitive is a category. Any monoid (and thus any group) can be seen as a category: in this case, the category has only one object and the morphisms of the category are given by the elements of the monoid. Composition of morphisms corresponds to multiplication of elements of the monoid. It is easily checked that the axioms of a monoid corresponds to the axioms of a category in this particular case. It can therefore be said that the notion of a category is a generalization of the concept of preorder and at the same time a generalization of the notion of monoid. These two classes of examples also show that a categery need not be a collection of structured sets and structure preserving functions. A slightly different example of this phenomenon is provided by the following important case: the category hTop has as its objects topological spaces and as morphisms equivalence classes of homotopic functions between spaces.

Let us briefly come back to the case of deductive systems. A category can be defined as a deductive system satisfying certain equations. We first start with the notion of a graph: it consists of two classes Arrows and Objects and two mappings between them, s: ArrowsObjects and t: ArrowsObjects, namely the source and the target mappings. The arrows are usually called the "oriented edges" and the objects "nodes" or "vertices". Then, a deductive system is a graph with a specified arrow

R1. ida:aa
and a binary operation on arrows
R2. given f: ab and g: bc, the composition of f and g is (g o f): ac.
Of course, as usual, the objects of a deductive system are thought of as formulas, the arrows are thought of as proofs or deductions and operations on arrows are thought of as rules of inference. A category is then defined as a deductive system in which the following equations hold between proofs: for all f: ab, g: bc and h: cd,
E1. f o ida = f, idb o f = f, h o (g o f) = (h o g) o f.

Thus, by imposing an adequate equivalence relation on proofs, any deductive system can be turned into a category. It is therefore legitimate to think of a category as an algebraic encoding of a deductive system. This phenomenon is already well-known to logicians, but probably not to its full extent. Indeed, the Lindenbaum-Tarski algebra of a theory in classical propositional logic is a Boolean algebra. Since the latter is a poset, it is also a category. This in itself is merely a change of vocabulary. Things become more interesting when first-order and higher-order logics are considered. For, the Lindenbaum-Tarski algebra for these systems yield, when properly carried out, categories, sometimes called "conceptual categories" or "syntactic categories". (See Mac Lane & Moerdijk 1992, Makkai & Reyes 1977, Pitts 2000.)

Categories also appear at the semantical level. Even for propositional logics, models of such systems are usually algebras, e.g., Boolean or Heyting algebras, and as such they are categories. The collections of such models also form categories, e.g., the category of distributive lattices, the category of Heyting algebras, the category of Boolean algebras. It can be shown that completeness theorems for propositional systems are equivalent to representation theorems for the appropriate category of algebras. For instance, the completeness theorem for classical propositional logic becomes equivalent to Stone's representation theorem for boolean algebras. Similar results can be provided for intuitionistic logic and Heyting algebras and various modal logics. (See, for instance, Ghilardi 1989, Ghilardi & Zawadowski 2002, Makkai & Reyes 1995, Reyes & Zawadowski 1991, Reyes & Zolfaghari 1991, 1996.) Again, this can be lifted to higher order levels and completeness theorems are again equivalent to representation theorems, but this time of categories.

Category theory unifies mathematical structures in a second, perhaps even more important, manner. Once a type of structure has been defined, it quickly becomes imperative to determine how new structures can be constructed out of the given one and how given structures can be decomposed into more elementary substructures. For instance, given two sets A and B, set theory allows us to construct their cartesian product A X B. For an example of the second sort, given a finite abelian group, it can be decomposed into a product of some of its subgroups. In both cases, it is necessary to know how structures of a certain kind combine. The nature of these combinations might appear to be considerably different when looked at from too close. Category theory reveals that many of these constructions are in fact special cases of objects in a category with what is called a "universal property". Indeed, from a categorical point of view, a set-theoretical cartesian product, a direct product of groups, a direct product of abelian groups, a product of topological spaces and a conjunction of propositions in a deductive system are all instances of a categorical concept: the categorical product. What characterizes the latter is a universal property. Formally, a product for two objects a and b in a category C is an object c of C together with two morphisms, called the projections, p: ca and q: cb such that, and this is the universal property, for all object d with morphisms f: da and g: db, there is a unique morphism h: dc such that p o h = f and q o h = g. Notice that we have defined a product for a and b and not the product for a and b. Indeed, products and, in fact, every object with a universal property, are defined up to (a unique) isomorphism. Thus, in category theory, the nature of the elements constituting a certain construction is irrelevant. What matters is the way an object is related to the other objects of the category, that is, the morphisms going in and the morphisms going out, or, put differently, how certain structures can be mapped into it and how it can map its structure into other structures of the same kind.

Another crucial aspect of category theory is that it allows to see how different kind of structures are related to one another. For instance, in algebraic topology, topological spaces are related to groups by various means (homology, cohomology, homotopy, K-theory). It was precisely in order to clarify how these connections are made and to compare them with one another that Eilenberg and Mac Lane invented category theory. Indeed, topological spaces with continuous maps constitute a category and similarly groups with group homomorphisms. In the very spirit of category theory, what should matter here are the morphisms between categories. These are given by functors and are informally structure preserving maps between categories. This simply means that, given two categories C and D, a functor F from C to D, should send objects of C to objects of D and morphisms of C to morphisms of D in such a way that composition of morphisms in C is preserved, i.e., F(g o f) = F(g) o F(f), and identity morphisms are preserved, i.e., F(ida) = idFa. It follows immediately that a functor preserves commutativity of diagrams between categories. Homology, cohomology, homotopy, K-theory are all example of functors. A more direct example is provided by the power set operation which yields two functors on the category of sets, depending on how one defines its action on functions. Thus, given a set X, P(X) is the usual set of subsets of X and given a function f: X → Y, P(f): P(X) → P(Y) takes a subset A of X and maps it to B = f(A), the image of f restricted to A in Y. It is easily verified that it is a functor. There are in general many functors between two given categories and it becomes natural to ask how they are connected. For instance, given a category C, there is always the identity functor from C to C which sends every object of C to itself and every morphism of C to itself. In particular, there is the identity functor over the category of sets. Now, the identity functor is related to the power set functor described above in a natural manner. Indeed, given a set X and its power set P(X), there is a function hX which takes an element x of X and send it to the singleton set {x}, a subset of X, i.e., an element of P(X). This function in fact belongs to a family of functions indexed by the objects of the category of sets {hY: Y → P(Y)| Y in Ob(Set)}. Moreover, it satisfies the following commutativity condition. Given any function f: X → Y, the identity functor yields the same function Id(f): Id(X) → Id(Y). The commutativity condition thus becomes: hY o Id(f) = P(f) o hX. Thus the family of functions h(-) relates the two functors in a natural manner. Such families of morphisms are called natural transformations between functors.

The above notions constitute the elementary concepts of category theory. However it should be noted that they are not fundamental notions of category theory. These are arguably the notions of limits/colimits which are, in turn, special cases of what is certainly the cornerstone of the theory, the concept of adjoint functors. We will not present the definition here. Suffice it to say that adjoint functors pervade mathematics and this pervasiveness is certainly one of the most mysterious fact that category theory reveals about mathematics and probably thinking in general.

2. Brief Historical Sketch

It is difficult to do justice to the short but intricate history of the field, in particular it is not possible to mention all those who have contributed to its rapid development. This warning being given, here are some of the main threads that have to be mentioned.

Categories, functors, natural transformations, limits and colimits appeared almost out of nowhere in 1945 in Eilenberg & Mac Lane's paper entitled "General Theory of Natural Equivalences". We said "almost", because when one looks at their 1942 paper "Group Extensions and Homology", one discovers specific functors and natural transformations at work, limited to groups. In fact, it was basically the need to clarify and abstract from their 1942 results that Eilenberg & Mac Lane came up with the notions of category theory. The central notion for them, as the title indicates, was the notion of natural transformation. In order to give a general definition of the latter, they defined the notion of functor, borrowing the terminology from Carnap, and in order to give a general definition of functor, they defined the notion of category, borrowing this time from Kant and Aristotle. After their 1945 paper, it was not clear that the concepts of category theory would be more than a convenient language and so it remained for approximately fifteen years. It was used as such by Eilenberg and Steenrod in their influential book on the foundations of algebraic topology, published in 1952 and by Cartan and Eilenberg in their ground breaking book on homological algebra, published in 1956. (It is interesting to note, however, that although categories are defined in Eilenberg & Steenrod's book, they are not in Cartan & Eilenberg's work! They are simply assumed in that latter.) These books allowed new generations of mathematicians to learn algebraic topology and homological algebra directly in the categorical language and to master the method of diagrams. Indeed, many results published in these two books seems to be inconceivable, or at the very least considerably more intricate, without the method of diagram chasing. Then, in 1957 and in 1958, the situation radically changed. In 1957, Grothendieck published his landmark "Sur quelques points d'algebre homologique" in which categories are used intrinsically to define and construct more general theories which are then applied to specific fields, in particular, in the following years, algebraic geometry, and in 1958 Kan published "Adjoint functors" and showed that the latter concept subsumes the important concepts of limits and colimits and could be used to capture fundamental conceptual situations (which in his case were in homotopy theory). From then on, category theory became more than a convenient language and this, for two reasons. First, using the axiomatic method and the categorical language, Grothendieck defined abstractly types of categories, e.g., additive and abelian categories, showed how to perform various constructions in these categories and proved various results for them. In a nutshell, Grothendieck showed how a part of homological algebra could be developed in such an abstract setting. From then on, a specific category of structures, e.g., a category of sheaves over a topological space X, could be seen as being a token of an abstract category of a certain type, e.g., an abelian category, and one could therefore immediately see how the methods homological algebra for instance could be applied in this case, e.g., in algebraic geometry. Furthermore, it made sense to look for other types of abstract categories, types of abstract categories which would encapsulate the fundamental and formal aspects of various mathematical fields in the same way that abelian categories encapsulated fundamental aspects of homological algebra. Second, mostly under the influence of Freyd and Lawvere, category theorists progressively saw how pervasive the concept of adjoint functors is. Not only can the existence of adjoints to given functors be used to define abstract categories, and presumably those which are defined by such means have a priviledged status, but as we have mentioned, many important theorems and even theories in various fields can be seen as being equivalent to the existence of specific functors between particular categories. By the early seventies, the concept of adjoint functors was considered to be the central concept of category theory.

With these developments, category theory became an autonomous part of mathematics, and pure category theory could be developed. And indeed, it did grow rapidly as a discipline but also in its applications, mainly in its original context, namely algebraic topology and homological algebra, but also in algebraic geometry and, after the appearance of Lawvere's thesis in 1963, in universal algebra. The latter work also constitutes a landmark in this history of the field. For it is in his thesis that Lawvere proposed the idea of developing the category of categories as a foundation for category theory, set theory and, thus, the whole of mathematics, as well as using categories for the study of theories, that is the logical aspects of mathematics. In the sixties, Lawvere outlined that basic framework for the development of an entirely original approach to logic and the foundations of mathematics: he proposed an axiomatization of the category of categories (Lawvere 1966), an axiomatization of the category of sets (Lawvere 1964), characterized cartesian closed categories and showed their connections to logical systems and various logical paradoxes (Lawvere 1969), showed that the quantifiers and the comprehension schemes could be captured as adjoint functors to given elementary operations (Lawvere 1969, 1970, 1971) and finally argued for the role of adjoint functors in foundations in general, through the notion of "categorical doctrines" (Lawvere 1969). At the same time, Lambek described categories in terms of deductive systems and used categorical methods for proof theoretical purposes. (See Lambek 1968, 1969, 1972.) All this work culminated in the development of an other idea due to Grothendieck and his school: the notion of a topos.

Even though the concept of a topos was presented in the sixties in the context of algebraic geometry, it was certainly Lawvere & Tierney's work on the elementary axiomatization of the concept, published in the early 1970s, which gave to the notion its foundational status and impetus. Very roughly, a topos is a category which also possess a rich logical structure, rich enough to develop most of "ordinary mathematics", that is, most of what is taught in an undergraduate degree in mathematics. Thus, as such, it can be thought of as a categorical theory of sets. But it is also a generalized topological space and thus provides a direct connection between logic and geometry. The 1970s saw the development and application of the concept in many different directions. (For more on the history of topos theory, see McLarty 1992.) The very first applications outside algebraic geometry were in set theory where various independence results were given a topos theoretical analysis. (See, for instance Tierney 1972, Bunge 1974 but also Blass & Scedrov 1989, Blass & Scedrov 1992, Freyd 1980, Mac Lane & Moerdijk 1992, Scedrov 1984.) Connections with intuitionistic mathematics were noticed early on and toposes are still used to investigate models of various aspects of intuitionism. (See, for instance, Lambek & Scott 1986, Mac Lane & Moerdijk 1992, Van der Hoeven & Moerdijk 1984a, 1984b, 1984c, Moerdijk 1984, Moerdijk 1995a, Moerdijk 1998, Moerdijk & Palmgren 1997, Moerdijk & Palmgren 2002.) More generally, toposes can be used to investigate various forms of constructive mathematics or set theory. (See, for instance, Joyal & Moerdijk 1995 and Taylor 1996.) They are also used in the study of recursiveness and more generally models of higher order type theories. The introduction of the so-called "effective topos" and the search for axioms for synthetic domain theory are worth mentioning. (See, for instance, Hyland 1982, Hyland 1988, 1991, Hyland et. al., 1990, Mc Larty 1992, Jacobs 1999, Van Oosten 2002 and the references therein.) Lawvere's early motivation was to provide a new foundation for differential geometry, a lively research area which is now called "synthetic differential geometry". (See, for instance, Lawvere 2000, 2002, Kock 1981, Bell 1988, 1995, 1998, Moerdijk & Reyes 1991.) This is only the tip of the iceberg, for toposes could very well be to the twenty-first century what Lie groups have been to the twentieth century.

Finally, from the 1980s to this day, category theory found new applications. On the one hand, it now has many applications to theoretical computer science where it has firm roots and contributes, among other things, to the development of the semantics of programming and the development of new logical systems. (See, for instance Pitts 2000, Plotkin 2000, Scott 2000 and the references therein.) On the other hand, its applications to mathematics are becoming more diversified and it even touches upon theoretical physics where higher-dimensional category theory, which is to category theory what higher-dimensional geometry is to plane geometry, is used in the study of the so-called "quantum groups", or in quantum field theory. (See, for instance, Baez & Dolan 2001 and other publications by the same authors.)

3. Philosophical Significance

Category theory challenges philosophers in two non-exclusive ways. On the one hand, it is certainly the task of philosophy to clarify the general epistemological status of category theory and, in particular, its foundational status. On the other hand, category theory can be used by philosophers in their exploration of philosophical and logical problems. These two aspects can be illustrated briefly in turn.

Category theory is now a common tool in the toolbox of mathematicians. That much is clear. It is also clear that category theory unifies and provides a fruitful organization of mathematics. Given these simple facts, it remains to be seen whether category theory should be "on the same plane", so to speak, with set theory, whether it should be considered seriously as providing a foundational alternative to set theory or whether it is foundational in a different sense altogether. (The same question applies, in fact and even with more force, to topos theory, but we will unfortunately ignore this area here.) Arguments in favor of category theory and arguments against category theory as a foundational framework have been advanced. (See Blass 1984 for a survey of the relationships between category theory and set theory. See Feferman 1977, Bell 1981 and Hellman 2003 for arguments against category theory. See Marquis 1995 for a quick overview and a proposal.) This is in itself a complicated issue which is rendered even more difficult by the fact that the foundations of category theory itself still have to be clarified. Given that most of philosophy of mathematics of the last 50 years or so has been done under the assumption that mathematics is more or less set theory in disguise, the retreat of set theory in favor of category theory would necessarily have an important impact on philosophical thinking.

The use of category theory for logical and philosophical studies is already well underway. Indeed, categorical logic, the study of logic with the help of categorical means, has been around for about 30 years now and is still vigorous. On that front, many important results have been obtained but are still largely ignored by philosophers. Suffice it to mention the generalization of Kripke-Beth semantics for intuitionistic logic to sheaf semantics by Joyal, the discovery of the so-called geometric or coherent logic, whose practical and conceptual significance still has to be exposed, the notion and theorems of strong conceptual completeness, the geometric proofs of the independence of the continuum hypothesis and other strong axioms of set theory, the development of synthetic differential geometry which provides an alternative to standard and non-standard analysis, the construction of the so-called effective topos in which every funtion on the natural numbers is recursive, categorical models of linear logic, modal logic and higher-order type theories in general and the development of a graphical syntax, called sketches. Category theory also provides relevant information to more general philosophical questions. For instance, Ellerman 1987 has tried to show that category theory constitutes a theory of universals which has properties radically different from set theory considered as a theory of universals. (See also Marquis 2000.) If we move from universals to concepts in general, we can see how category theory could be useful even in cognitive science. Indeed, Macnamara and Reyes have already tried to use categorical logic to provide a different logic of reference. (See, for instance, Macnamara & Reyes 1994.) Awodey, Landry, Makkai, Marquis and McLarty have tried to show how it sheds an interesting light on structuralists approach to mathematical knowledge. (See Awodey 1996, Landry 1999, 2001, Makkai 1995, 1999, Marquis 1993, 1995, 2000, McLarty 1993, 1994.)

Thus, category theory is philosophically relevant in many ways and which will undoubtedly have to be taken into account in the years to come.


Other Internet Resources

Related Entries

mathematics, philosophy of | set theory

Copyright © 2004
Jean-Pierre Marquis

A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

Stanford Encyclopedia of Philosophy