Definitions

Categories are algebraic structures with many complementary natures, e.g., geometric, logical, computational, combinatorial, just as groups are many-faceted algebraic structures. Eilenberg & Mac Lane (1945) introduced categories in a purely auxiliary fashion, as preparation for what they called functors and natural transformations. The very definition of a category evolved over time, according to the author's chosen goals and metamathematical framework. Eilenberg & Mac Lane at first gave a purely abstract definition of a category, along the lines of the axiomatic definition of a group. Others, starting with Grothendieck (1957) and Freyd (1964), elected for reasons of practicality to define categories in set-theoretic terms.

An alternative approach, that of Lawvere (1963, 1966), begins by characterizing the category of categories, and then stipulates that a category is an object of that universe. This approach, under active development by various mathematicians, logicians and mathematical physicists, lead to what are now called “higher-dimensional categories” (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. We will briefly go over some of these definitions, starting with Eilenberg's & Mac Lane's (1945) algebraic definition. However, before going any further, the following definition will be required.

Definition: A mapping e will be called an identity if and only if the existence of any product eα or βe implies that eα = α and βe = β

Definition (Eilenberg & Mac Lane 1945): A category C is an aggregate Ob of abstract elements, called the objects of C, and abstract elements Map, called mappings of the category. The mappings are subject to the following five axioms:

(C1) Given three mappings α₁, α₂ and α₃, the triple product α₃(α₂α₁) is defined if and only if (α₃α₂)α₁ is defined. When either is defined, the associative law

α₃(α₂α₁) = (α₃α₂)α₁

holds. This triple product is written α₃α₂α₁.

(C2) The triple product α₃α₂α₁ is defined whenever both products α₃α₂ and α₂α₁are defined.

(C3) For each mapping α, there is at least one identity e₁ such that αe₁ is defined, and at least one identity e₂ such that e₂α is defined.

(C4) The mapping e_X corresponding to each object X is an identity.

(C5) For each identity e there is a unique object X of C such that e_X = e.

As Eilenberg & Mac Lane promptly remark, objects play a secondary role and could be entirely omitted from the definition. Doing so, however, would make the manipulation of the applications less convenient. It is practically suitable,and perhaps psychologically more simple to think in terms of mappings and objects. The term “aggregate” is used by Eilenberg & Mac Lane themselves, presumably so as to remain neutral with respect to the background set theory one wants to adopt.

Eilenberg & Mac Lane defined categories in 1945 for reasons of rigor. As they note:

It should be observed first that the whole concept of a category is essentially an auxiliary one; our basic concepts are essentially those of a functor and of natural transformation (…). The idea of a category is required only by the precept that every function should have a definite class as domain and a definite class as range, for the categories are provided as the domains and ranges of functors. Thus one could drop the category concept altogether and adopt an even more intuitive standpoint, in which a functor such as “Hom” is not defined over the category of “all” groups, but for each particular pair of groups which may be given. The standpoint would suffice for applications, inasmuch as none of our developments will involve elaborate constructions on the categories themselves. (1945, chap. 1, par. 6, p. 247)

Things changed in the following ten years, when categories started to be used in homology theory and homological algebra. Mac Lane, Buchsbaum, Grothendieck and Heller were considering categories in which the collections of morphisms between two fixed objects have an additional structure. More specifically, given any two objects X and Y of a category C, the set Hom(X, Y) of morphisms from X to Y form an abelian group. Furthermore, for reasons related to the ways homology and cohomology theories are linked, the definition of a category had to satisfy an additional formal property (which we will leave aside for the moment): it had to be self-dual. These requirements lead to the following definition.

Definition: A category C can be described as a set Ob, whose members are the objects of C, satisfying the following three conditions:

Morphism : For every pair X, Y of objects, there is a set Hom(X, Y), called the morphisms from X to Y in C. If f is a morphism from X to Y, we write f : X → Y.

Identity : For every object X, there exists a morphism id_X in Hom(X, X), called the identity on X.

Composition : For every triple X, Y and Z of objects, there exists a partial binary operation from Hom(X, Y) × Hom(Y, Z) to Hom(X, Z), called the composition of morphisms in C. If f : X → Y and g : Y → Z, the composition of f and g is notated (g ○ f ) : X → Z.

Identity, morphisms, and composition satisfy two axioms:

Associativity : If f : X → Y, g : Y → Z and h : Z → W, then h ○ (g ○ f) = (h ○ g) ○f.

Identity : If f : X → Y, then (id_Y ○ f) = f and (f ○ id_X) = f.

This is the definition one finds in most textbooks of category theory. As such it explicitly relies on a set theoretical background and language. An alternative, suggested by Lawvere in the early sixties, is to develop an adequate language and background framework for a category of categories. We will not present the formal framework here, for it would take us too far from our main concern, but the basic idea is to define what are called weak n-categories (and weak ω-categories), and what had been called categories would then be called weak 1-categories (and sets would be weak 0-categories). (See, for instance, Baez 1997, Makkai 1998, Leinster 2004, Baez & May 2010, Simpson 2011.)

Also in the sixties, Lambek proposed to look at categories as deductive systems. This begins with the notion of a graph, consisting of two classes Arrows and Objects, and two mappings between them, s : Arrows → Objects and t : Arrows → Objects, namely the source and the target mappings. The arrows are usually called the “oriented edges” and the objects “nodes” or “vertices”. Following this, a deductive system is a graph with a specified arrow:

(R1) id_X : X → X,

and a binary operation on arrows:

(R2) Given f : X → Y and g : Y → Z, the composition of f and g is (g ○ f) : X → Z.

Of course, the objects of a deductive system are normally thought of as formulas, the arrows are thought of as proofs or deductions, and operations on arrows are thought of asrules of inference. A category is then defined thus:

Definition (Lambek): A category is a deductive system in which the following equations hold between proofs: for all f : X → Y, g : Y → Z and h: Z → W,

(E1) f ○ id_X = f,   id_Y ○ f = f,   h ○ (g ○ f) = (h ○ g) ○ f.

Thus, by imposing an adequate equivalence relation upon 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 fullest extent. An example of such an algebraic encoding is the Lindenbaum-Tarski algebra, a Boolean algebra corresponding to classical propositional logic. Since a Boolean algebra is a poset, it is also a category. (Notice also that Boolean algebras with appropriate homomorphisms between them form another useful category in logic.) Thus far we have merely a change of vocabulary. Things become more interesting when first-order and higher-order logics are considered. The Lindenbaum-Tarski algebra for these systems, when properly carried out, yields categories, sometimes called “conceptual categories” or “syntactic categories” (Mac Lane & Moerdijk 1992, Makkai & Reyes 1977, Pitts 2000).

• –––, 2004, “An Answer to Hellman's Question: Does Category Theory Provide a Framework for Mathematical Structuralism”, Philosophia Mathematica, 12: 54–64.
• –––, 2006, Category Theory, Oxford: Clarendon Press.
• –––, 2007, “Relating First-Order Set Theories and Elementary Toposes”, The Bulletin of Symbolic, 13 (3): 340–358.
• –––, 2008, “A Brief Introduction to Algebraic Set Theory”, The Bulletin of Symbolic, 14 (3): 281–298.
• Awodey, S., et al., 2013, Homotopy Type Theory: Univalent Foundations of Mathematics, The Univalent Foundations Program.
• Awodey, S. & Butz, C., 2000, “Topological Completeness for Higher Order Logic”, Journal of Symbolic Logic, 65 (3): 1168–1182.
• Awodey, S. & Reck, E. R., 2002, “Completeness and Categoricity I. Nineteen-Century Axiomatics to Twentieth-Century Metalogic”, History and Philosophy of Logic, 23 (1): 1–30.
• –––, 2002, “Completeness and Categoricity II. Twentieth-Century Metalogic to Twenty-first-Century Semantics”, History and Philosophy of Logic, 23 (2): 77–94.
• Awodey, S. & Warren, M., 2009, “Homotopy theoretic Models of Identity Types”, Mathematical Proceedings of the Cambridge Philosophical Society, 146 (1): 45–55.
• Baez, J., 1997, “An Introduction to n-Categories”, Category Theory and Computer Science, Lecture Notes in Computer Science (Volume 1290), Berlin: Springer-Verlag, 1–33.
• Baez, J. & Dolan, J., 1998a, “Higher-Dimensional Algebra III. n-Categories and the Algebra of Opetopes”, Advances in Mathematics, 135: 145–206.
• –––, 1998b, “Categorification”, Higher Category Theory (Contemporary Mathematics, Volume 230), Ezra Getzler and Mikhail Kapranov (eds.), Providence: AMS, 1–36.
• –––, 2001, “From Finite Sets to Feynman Diagrams”, Mathematics Unlimited – 2001 and Beyond, Berlin: Springer, 29–50.
• Baez, J. & Lauda, A.D., 2011, “A Pre-history of n-Categorical Physics”, Deep Beauty: Understanding the Quantum World Through Mathematical Innovation, H. Halvorson, ed., Cambridge: Cambridge University Press, 13–128.
• Baez, J. & May, P. J., 2010, Towards Higher Category Theory, Berlin: Springer.
• Baez, J. & Stay, M., 2010, “Physics, Topology, Logic and Computation: a Rosetta Stone”, New Structures for Physics (Lecture Notes in Physics 813), B. Coecke (ed.), New York, Springer: 95–172.
• Baianu, I. C., 1987, “Computer Models and Automata Theory in Biology and Medecine”, in Witten, Matthew, Eds. Mathematical Modelling, Vol. 7, 1986, chapter 11, Pergamon Press, Ltd., 1513–1577.
• Bain, J., 2013, “Category-theoretic Structure and Radical Ontic Structural Realism”, Synthese, 190: 1621–1635.
• Barr, M. & Wells, C., 1985, Toposes, Triples and Theories, New York: Springer-Verlag.
• –––, 1999, Category Theory for Computing Science, Montreal: CRM.
• Batanin, M., 1998, “Monoidal Globular Categories as a Natural Environment for the Theory of Weak n-Categories”, Advances in Mathematics, 136: 39–103.
• Bell, J. L., 1981, “Category Theory and the Foundations of Mathematics”, British Journal for the Philosophy of Science, 32: 349–358.
• –––, 1982, “Categories, Toposes and Sets”, Synthese, 51 (3): 293–337.
• –––, 1986, “From Absolute to Local Mathematics”, Synthese, 69 (3): 409–426.
• –––, 1988, “Infinitesimals”, Synthese, 75 (3): 285–315.
• –––, 1988, Toposes and Local Set Theories: An Introduction, Oxford: Oxford University Press.
• –––, 1995, “Infinitesimals and the Continuum”, Mathematical Intelligencer, 17 (2): 55–57.
• –––, 1998, A Primer of Infinitesimal Analysis, Cambridge: Cambridge University Press.
• –––, 2001, “The Continuum in Smooth Infinitesimal Analysis”, Reuniting the Antipodes — Constructive and Nonstandard Views on the Continuum (Synthese Library, Volume 306), Dordrecht: Kluwer, 19–24.
• –––, 2005, “The Development of Categorical Logic”, in Handbook of Philosophical Logic(Volume 12), 2nd ed., D.M. Gabbay, F. Guenthner (eds.), Dordrecht: Springer, pp. 279–362.
• Birkoff, G. & Mac Lane, S., 1999, Algebra, 3^rd ed., Providence: AMS.
• Blass, A., 1984, “The Interaction Between Category Theory and Set Theory”, in Mathematical Applications of Category Theory (Volume 30), Providence: AMS, 5–29.
• Blass, A. & Scedrov, A., 1983, “Classifying Topoi and Finite Forcing”, Journal of Pure and Applied Algebra, 28: 111–140.
• –––, 1989, Freyd's Model for the Independence of the Axiom of Choice, Providence: AMS.
• –––, 1992, “Complete Topoi Representing Models of Set Theory”, Annals of Pure and Applied Logic , 57 (1): 1–26.
• Blute, R. & Scott, P., 2004, “Category Theory for Linear Logicians”, in Linear Logic in Computer Science, T. Ehrhard, P. Ruet, J-Y. Girard, P. Scott, eds., Cambridge: Cambridge University Press, 1–52.
• Boileau, A. & Joyal, A., 1981, “La logique des topos”, Journal of Symbolic Logic, 46 (1): 6–16.
• Borceux, F., 1994, Handbook of Categorical Algebra, 3 volumes, Cambridge: Cambridge University Press.
• Brading, K. & Landry, E., 2006, “Scientific Structuralism: Presentation and Representation”, Philosophy of Science, 73: 571–581.
• Brown, R. & Porter, T., 2006, “Category Theory: an abstract setting for analogy and comparison”, What is Category Theory?, G. Sica, ed., Monza: Polimetrica: 257–274.
• Bunge, M., 1974, “Topos Theory and Souslin's Hypothesis”, Journal of Pure and Applied Algebra, 4: 159–187.
• –––, 1984, “Toposes in Logic and Logic in Toposes”, Topoi, 3 (1): 13–22.
• Caramello, O., 2011, “A Characterization Theorem for Geometric Logic”, Annals of Pure and Applied Logic,162, 4: 318–321.
• –––, 2012a, “Universal Models and Definability”, Mathematical Proceedings of the Cambridge Philosophical Society, 152 (2): 279–302.
• –––, 2012b, “Syntactic Characterizations of Properties of Classifying Toposes”, Theory and Applications of Categories, 26 (6): 176–193.
• Carter, J., 2008, “Categories for the working mathematician: making the impossible possible”, Synthese, 162 (1): 1–13.
• Cheng, E. & Lauda, A., 2004, Higher-Dimensional Categories: an illustrated guide book, available at: http://cheng.staff.shef.ac.uk/guidebook/index.html
• Cockett, J. R. B. & Seely, R. A. G., 2001, “Finite Sum-product Logic”, Theory and Applications of Categories (electronic), 8: 63–99.
• Coecke, B., 2011, “A Universe of Processes and Some of its Guises”, Deep Beauty: Understanding the Quantum World through Mathematical Innovation, Cambridge: Cambridge University Press: 129–186.
• Couture, J. & Lambek, J., 1991, “Philosophical Reflections on the Foundations of Mathematics”, Erkenntnis, 34 (2): 187–209.
• –––, 1992, “Erratum:”Philosophical Reflections on the Foundations of Mathematics“”, Erkenntnis, 36 (1): 134.
• Crole, R. L., 1994, Categories for Types, Cambridge: Cambridge University Press.
• Dieudonné, J. & Grothendieck, A., 1960 [1971], Éléments de Géométrie Algébrique, Berlin: Springer-Verlag.
• Döring, A., 2011, “The Physical Interpretation of Daseinisation”, Deep Beauty: Understanding the Quantum World through Mathematical Innovation, Cambridge: Cambridge University Press: 207-238.
• Ehresmann, A. & Vanbremeersch, J.-P., 2007, Memory Evolutive Systems: Hierarchy, Emergence, Cognition, Amsterdam: Elsevier
• –––, 1987, “Hierarchical Evolutive Systems: a Mathematical Model for Complex Systems”, Bulletin of Mathematical Biology, 49 (1): 13–50.
• Eilenberg, S. & Cartan, H., 1956, Homological Algebra, Princeton: Princeton University Press.
• Eilenberg, S. & Mac Lane, S., 1942, “Group Extensions and Homology”, Annals of Mathematics, 43: 757–831.
• –––, 1945, “General Theory of Natural Equivalences”, Transactions of the American Mathematical Society, 58: 231–294.
• Eilenberg, S. & Steenrod, N., 1952, Foundations of Algebraic Topology, Princeton: Princeton University Press.
• Ellerman, D., 1988, “Category Theory and Concrete Universals”, Erkenntnis, 28: 409–429.
• Feferman, S., 1977, “Categorical Foundations and Foundations of Category Theory”, Logic, Foundations of Mathematics and Computability, R. Butts (ed.), Reidel, 149–169.
• –––, 2004, “Typical Ambiguity: trying to have your cake and eat it too”, One Hundred Years of Russell's Paradox, G. Link (ed.), Berlin: De Gruyter, 135–151.
• Freyd, P., 1964, Abelian Categories. An Introduction to the Theory of Functors, New York: Harper & Row.
• –––, 1965, “The Theories of Functors and Models”. Theories of Models, Amsterdam: North Holland, 107–120.
• –––, 1972, “Aspects of Topoi”, Bulletin of the Australian Mathematical Society, 7: 1–76.
• –––, 1980, “The Axiom of Choice”, Journal of Pure and Applied Algebra, 19: 103–125.
• –––, 1987, “Choice and Well-Ordering”, Annals of Pure and Applied Logic, 35 (2): 149–166.
• –––, 1990, Categories, Allegories, Amsterdam: North Holland.
• –––, 2002, “Cartesian Logic”, Theoretical Computer Science, 278 (1–2): 3–21.