Category theory is the mathematical field that studies categories, which are a certain kind of mathematical structure. Categories are found throughout mathematics, and category theory thus has many mathematical applications. It is a basis for intuitionistic type theory, and as such has applications in computer science as a basis for functional programming semantics.
Definition and examples
To constitute a category, some things (called the morphisms of the category) must have three main features:
- i) Each morphism should have associated with them two objects, called the source and the target (or sometimes the domain and codomain) of the morphism. We write to say that f is a morphism with source S and target T. The things that are sources and targets of morphisms are called the objects of the category.
- ii) There must be a way of combining any pair of morphisms, say f and g whenever the target of f is the same as the source of g, and the result of combining them, which is typically denoted by must have the same source as f and the same target as g. This operation of combining is called the composition of the category. Additionally composition must be associative. That is it must always be the case that (so long as the sources and targets agree in the appropriate way).
- iii) For every object of the category there must be an identity morphism, whose source and target are both that object. The identity for an object A is usually written idA. Identity morphisms must leave any other morphism fixed when composed with them. That is for any , it must be the case that .
A more concrete example would be geometric transformations. Think of a thing on a table, say a tray. The tray can be shifted (S) across the table and then rotated (R), and these can be viewed as morphisms in a category of just one object: the tray. Composition simply means that two actions such as S and R can be thought of as combined into a single action R∘S, which is the act of performing both consecutively, S and then R (note the annoying change in order that the notation requires: "S then R" is R∘S).
These actions are indeed associative. Think of three motions of the tray:
- F: Flipping the tray over.
- R: Rotation of the tray 180 degrees.
- S: Shifting of the tray 1 m north across the table.
If we perform all three, the flip and rotation can be thought of as combined into a single motion, then followed by the shift; this would be denoted S∘(R∘F). Alternatively, the rotation and shift can be thought of as a single motion following the flip: (S∘R)∘F. Associativity simply means that S∘(R∘F) = (S∘R)∘F, which is true, as both correspond to doing all three in order. The identity motion for the tray is to leave it where it is, that is the tray starts and ends up in the same position. For example if T denotes shifting the tray 1m South then T∘S and S∘T are identity motions. We say in these circumstances that T is an inverse for S.
Many applications of category theory such as this can be thought of as based on two concepts: objects and the things which act on objects. When diverse mathematical structures are recognized to be categorial objects and the relationships between objects to be categorial morphisms, the theory expresses features shared by diverse subjects. For example, arithmetic has the product of a pair of numbers, set theory has the Cartesian product of a pair of sets and logic has the conjunction of a pair of assertions. These three products and many others are instances of the categorial product. Furthermore, the product is a specific instance of the more general notion of a limit and a limit is a specific universal property. By such generalizations, category theory unifies mathematics at a high level of abstraction.
- ↑ Technically we are talking about typed functions. For example if we consider the function that takes a natural number and doubles it, we may regard this as a function from N to N, but we might just as well regard it as a function from N to the even numbers. We would normally say that the two functions were one and the same, but in category theory we must distinguish between them because they have different targets.
- ↑ We ignore the possibility that moving the tray might make it fall of the table. It's a big table.
|Some content on this page may previously have appeared on Citizendium.|