Category theory

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.

[edit] 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 id_A. Identity morphisms must leave any other morphism fixed when composed with them. That is for any , it must be the case that .

The canonical example (which most of the above terminology and notation is derived from) is functions, where the objects are sets, the source is the domain and the target is the range (that is, codomain, not necessarily the image) and, unsurprisingly, the composition operation is function composition and the identity morphism for a set A is the identity function on A.^[1] Many special kinds of function are closed under composition (i.e. the composition of two functions of that kind is also of that kind), and will therefore form a category in their own right. For example the composition of two injective functions is itself injective. Generally the composition of two structure-preserving maps (e.g. two group homomorphisms, two linear maps, two isometries, two diffeomorphisms etc etc) will preserve the same structure, so each of these forms a category. Although it is the morphisms that determine the category, it is often the objects that mathematicians are interested in, and so many categories are named after the objects. The category whose objects are all the group homomorphisms is denoted Grp for example. A simple example where the composition is not function composition is paths in the plane, where the source is the initial point and the target is the terminal point. If one path starts where the other finishes then the two paths can be juxtaposed to get a composite path. Here the objects are points and the identity morphisms are constant paths.

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^[2]. 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.

[edit] Notes

1. ↑ 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.
2. ↑ 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.