Category (mathematics)
In mathematics, a category is a collection of "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose objects are sets and whose arrows are functions.
Category theory is a branch of mathematics that seeks to generalize all of mathematics in terms of categories, independent of what their objects and arrows represent. Virtually every branch of modern mathematics can be described in terms of categories, and doing so often reveals deep insights and similarities between seemingly different areas of mathematics. As such, category theory provides an alternative foundation for mathematics to set theory and other proposed axiomatic foundations. In general, the objects and arrows may be abstract entities of any kind, and the notion of category provides a fundamental and abstract way to describe mathematical entities and their relationships.
In addition to formalizing mathematics, category theory is also used to formalize many other systems in computer science, such as the semantics of programming languages.
Two categories are the same if they have the same collection of objects, the same collection of arrows, and the same associative method of composing any pair of arrows. Two different categories may also be considered "equivalent" for purposes of category theory, even if they do not have precisely the same structure.
Well-known categories are denoted by a short capitalized word or abbreviation in bold or italics: examples include Set, the category of sets and set functions; Ring, the category of rings and ring homomorphisms; and Top, the category of topological spaces and continuous maps. All of the preceding categories have the identity map as identity arrows and composition as the associative operation on arrows.
The classic and still much used text on category theory is Categories for the Working Mathematician by Saunders Mac Lane. Other references are given in the [|References] below. The basic definitions in this article are contained within the first few chapters of any of these books.
Any monoid can be understood as a special sort of category, and so can any preorder.
Definition
There are many equivalent definitions of a category. One commonly used definition is as follows. A category consists of- a class of objects,
- a class of morphisms or arrows,
- a domain or source class function,
- a codomain or target class function,
- for every three objects, a binary operation called composition of morphisms. Here denotes the subclass of morphisms in such that and. Morphisms in this subclass are written, and the composite of and is often written as or.
- the associative law: if, and then, and
- the : for every object, there exists a morphism called the identity morphism for , such that every morphism satisfies, and every morphism satisfies.
Some authors write the composite of morphisms in "diagrammatic order", writing or instead of.
From these axioms, one can prove that there is exactly one identity morphism for every object. Often the map assigning each object its identity morphism is treated as an extra part of the structure of a category, namely a class function.
Some authors use a slight variant of the definition in which each object is identified with the corresponding identity morphism. This stems from the idea that the fundamental data of categories are morphisms and not objects. In fact, categories can be defined without reference to objects at all using a partial binary operation with additional properties.
Small and large categories
A category is called small if both and are actually sets and not proper classes, and large otherwise. A locally small category is a category such that for all objects and, the hom-class is a set, called a homset. Many important categories in mathematics, although not small, are at least locally small. Since, in small categories, the objects form a set, a small category can be viewed as an algebraic structure similar to a monoid but without requiring closure properties. Large categories on the other hand can be used to create "structures" of algebraic structures.Examples
The class of all sets together with all functions between them, where the composition of morphisms is the usual function composition, forms a large category, Set. It is the most basic and the most commonly used category in mathematics. The category Rel consists of all sets with binary relations between them. Abstracting from relations instead of functions yields allegories, a special class of categories.Any class can be viewed as a category whose only morphisms are the identity morphisms. Such categories are called discrete. For any given set, the discrete category on I is the small category that has the elements of as objects and only the identity morphisms as morphisms. Discrete categories are the simplest kind of category.
Any preordered set forms a small category, where the objects are the members of, the morphisms are arrows pointing from to when. Furthermore, if is antisymmetric, there can be at most one morphism between any two objects. The existence of identity morphisms and the composability of the morphisms are guaranteed by the reflexivity and the transitivity of the preorder. By the same argument, any partially ordered set and any equivalence relation can be seen as a small category. Any ordinal number can be seen as a category when viewed as an ordered set.
Any monoid forms a small category with a single object. The morphisms from to are precisely the elements of the monoid, the identity morphism of is the identity of the monoid, and the categorical composition of morphisms is given by the monoid operation. Several definitions and theorems about monoids may be generalized for categories.
Similarly any group can be seen as a category with a single object in which every morphism is invertible, that is, for every morphism there is a morphism that is both left and right inverse to under composition. A morphism that is invertible in this sense is called an isomorphism.
A groupoid is a category in which every morphism is an isomorphism. Groupoids are generalizations of groups, group actions and equivalence relations. Actually, in the view of category the only difference between groupoid and group is that a groupoid may have more than one object but the group must have only one. Consider a topological space and fix a base point of, then is the fundamental group of the topological space and the base point, and as a set it has the structure of group; if then let the base point runs over all points of, and take the union of all, then the set we get has only the structure of groupoid : two loops may not have the same base point so they cannot multiply with each other. In the language of category, this means here two morphisms may not have the same source object so they can not compose with each other.
Any directed graph generates a small category: the objects are the vertices of the graph, and the morphisms are the paths in the graph where composition of morphisms is concatenation of paths. Such a category is called the free category generated by the graph.
The class of all preordered sets with order-preserving functions as morphisms forms a category, Ord. It is a concrete category, i.e. a category obtained by adding some type of structure onto, and requiring that morphisms are functions that respect this added structure.
The class of all groups with group homomorphisms as morphisms and function composition as the composition operation forms a large category, Grp. Like, is a concrete category. The category Ab, consisting of all abelian groups and their group homomorphisms, is a full subcategory of, and the prototype of an abelian category.
The class of all graphs forms another concrete category, where morphisms are graph homomorphisms.
Other examples of concrete categories are given by the following table.
| Category | Objects | Morphisms |
| Set | sets | functions |
| Ord | preordered sets | monotone-increasing functions |
| Mon | monoids | monoid homomorphisms |
| Grp | groups | group homomorphisms |
| Grph | graphs | graph homomorphisms |
| Ring | rings | ring homomorphisms |
| Field | fields | field homomorphisms |
| R-Mod | R-modules, where is a ring | R-module homomorphisms |
| VectK | vector spaces over the field | K-linear maps |
| Met | metric spaces | short maps |
| Meas | measure spaces | measurable functions |
| Stoch | measure spaces | Markov kernels |
| Top | topological spaces | continuous functions |
| Manp | smooth manifolds | - |
Fiber bundles with bundle maps between them form a concrete category.
The category Cat consists of all small categories, with functors between them as morphisms.