Category theory

Category theory studies the abstraction of mathematical objects (such as sets, groups, and topological spaces) in terms of the morphisms between them. Such a collection of objects and morphisms is a category. Morphisms often represent functions. For example, in the category of sets, morphisms represent all functions, in the category of groups they represent group homomorphism and in the category of topological spaces, they represent continuous maps.

Categories are usually drawn as diagrams with the objects represented by variables or points with (labeled) arrows between them representing morphisms. For this reason, morphisms are also referred to as arrows.

Morphisms do not have to represent functions. For example, any partially ordered set may be seen as a category where the objects are the elements of the poset and there is a (unique) morphism $x \to y$ between two elements $x$ and $y$ if and only if $x \leq y$ .

Definition

A category consists of a collection of objects and a collection of morphisms. A morphism $f$ goes from one object, say $X$ , to another, say $Y$ , and is drawn as an arrow from $X$ to $Y$ . Note that $X$ may equal $Y$ (in which case $f$ is referred to as an endomorphism). The object $X$ is called the source or domain of $f$ and $Y$ is called the target or codomain of $f$ . This is written as $f : X \to Y$ .

These morphisms must satisfy three conditions:

Composition: For any two morphisms $f : X \to Y$ and $g : Y \to Z$ , there exists a morphism $X \to Z$ , written as $g \circ f$ or simply $g f$ .
Associativity: For any morphisms $f : X \to Y$ , $g : Y \to Z$ and $h : Z \to W$ composition is associative, i.e., $h (g f) = (h g) f$ .
Identity: For any object $X$ , there is a (unique) morphism, $1_{X} : X \to X$ which, when composed with another morphism, leaves it unchanged. I.e., given $f : W \to X$ and $g : X \to Y$ it holds that: $1_{X} f = f$ and $g 1_{X} = g$ .

Note that composition is written 'backwards' since given an element $x \in X$ and two functions $f : X \to Y$ and $g : Y \to Z$ , the result of applying $f$ then $g$ is $g (f (x))$ which equals $(g \circ f) (x)$ .

Motivation

Many mathematical constructions (such as products) appear across different fields of mathematics, consisting of different ingredients but nevertheless capturing a similar idea (and often even under the same name). Category theory allows one to precisely describe the property that these different constructions all at once. This allows one to prove theorems about all these structures at once. Hence, once you prove that a specific mathematical structure is, say, a product, then all the category-theoretic theorems about products are true for that structure. In fact, sometimes there are structures which non-obviously satisfy a category-theoretic property. Especially when category-theoretic duality is involved.

In addition, category theory allows the simple description of functors, natural transformations and adjunctions. These are mathematically powerful concepts which are very difficult to describe without the language of category theory. In fact, one of the founders of category theory, Saunders Mac Lane, has remarked that category theory was initially developed in order to provide a language in which to speak about natural transformations.

Powerfully, functors and adjunctions between categories allow one to translate concepts from one mathematical theory to another. They provide a "translation" (either full or partial) that allows one type of object to be viewed as another, and theorems to be translated across domains. In fact, using duality, very non-obvious translations can be found because a theorem in one category can be translated to its "opposite theory" in the other category. Connections which are not obvious in the language of the mathematical theories themselves, become clear in the language of category theory.

Categories Give an External View

Although the objects and morphisms of a category are intended to represent e.g. sets and functions, from the point of view of the category the objects and morphisms have no internal structure. It is not possible to talk directly about the elements of an object or how a given morphism maps elements. Instead (from the viewpoint of the category) the information about the objects and morphisms are given completely by which objects are sources and targets for the morphisms and how the morphisms are composed.

In fact, this is the strength of category theory: abstracting away the internal details allows one to focus only on relevant information and also capture information about multiple similar types of structures that act in a certain way across different mathematical theories.

This is similar to the way that a group abstracts away what elements are whilst only capturing the information of how they are 'added' or 'multiplied'.

It is also somewhat similar to the concept of a program's API (or an interface in Java); we can't see inside the program or know how it implements something, but we know what kind of inputs and outputs programs have, and what kinds of inputs and outputs a composition of such programs have.

Note that since it abstracts something away, a category does not always capture enough information for one's purposes. For example, there is addition of group homomorphisms defined pointwise. For this purpose, other structures such as enriched categories and n-categories may be used. However, for many purposes, categories are at a very good between isomorphic objects. This is considered a feature of category theory.

Common Symbols: Convention

Different texts make use of different conventions. This site makes use of the following common convention:

Categories are written in blackboard bold upper-case letters and are usually near the beginning of the alphabet. E.g. $A, B, C$ .
Objects are written as upper-case letters usually near the beginning or end of the alphabet. E.g. $A, B, C, W, X, Y, Z$ .
Morphisms are labelled with lower-case letters, usually near f or near u. E.g. $e, f, g, h, u, v, w$ .
Elements of an object, where necessary, are written as lower-case letters, usually near the beginning or end of the alphabet. E.g. $a, b, c, x, y, z$
Functors are written as upper-case letters usually near F. E.g. $E, F, G, H$ .
Natural transformations are written as Greek letters, usually near the beginning of the alphabet. E.g. $α, β, γ, δ$ .
The morphisms forming part of a cone or cocone for a limit or colimit are often written as Greek letters with subscripts, usually $κ$ or $λ$ .

These conventions are merely guidelines and far from universally followed. Check the definition for the symbol in question to see what it represents

Isomorphisms in Category Theory

In category theory, isomorphic objects are not distinguished. Many universal_constructions do not pin down a specific construction but instead only specify it up to isomorphism.

Doing something in category theory which relies on a specific construction (instead of being up to isomorphism) is colloquially referred to as evil.

Universal Properties

One of the most important concepts in category theory is that of a universal property. An object in a category which satisfies a universal property is in a sense the 'best' (often meaning smallest or largest) object satisfying a certain property. This can often be used to describe in a universal way constructions like products which are defined for multiple distinct structures. In category theory, it is defined once without referring to a specific construction. This definition can then be applied to multiple categories.

The simplest non-trivial universal construction is the terminal object. Given a category $C$ , an object $T$ in $C$ is called a terminal object if, for any object $X$ in $C$ , there is a unique morphism $f : X \to T$ . In other words there is some $f : X \to T$ and if there is also $g : X \to T$ then $f = g$ . In the category of sets, the terminal objects are exactly the one element sets. Given a one element set ${a}$ , and any set $X$ , there is a unique morphism $f : X \to {a}$ , namely the function taking every $x$ in $X$ to $a$ . In the category of groups, terminal objects are exactly one-element groups. Note that terminal objects need not exist. Consider a poset seen as a category. If it has a largest element $T$ , then each object is less than or equal to $T$ . So from each object there is a unique morphism to $T$ and hence it is terminal. If, however, there is no largest element then the category has no terminal object.

As another example, products can be defined by a universal property: Given a pair of objects $X$ and $Y$ , an object $P$ along with a pair of morphisms $f : P \to X$ and $g : P \to Y$ is called the product of $X$ and $Y$ if, given any other object $W$ and morphisms $u : W \to X$ and $v : W \to Y$ there is a unique morphism $h : W \to P$ such that $f h = u$ and $g h = v$ .

The above are both special cases of a very important and more general universal construction: the limit. This (along with the colimit) is described in more detail further below.

Duality

For any notion in a category, its dual is obtained by `reversing all the arrows' and 'reversing the order of composition'. If a statement is true in any category, then its dual is true in any category. As a corollary, if a statement is true in some categories, its dual is true in the duals of those categories.

As an example, consider the definition of a terminal object given above. A statement about terminal object is that any two terminal objects are isomorphic. Let's examine the exact statement. Assume $T$ is terminal. Then for any $X$ there is unique $f : X \to T$ . If we reverse the arrows, we get that for every $X$ there is unique $f : X \leftarrow T$ . This is the definition of an initial object. Consider another terminal object $T^{'}$ . The statement that $T^{'}$ is isomorphic to $T$ is means that there is some $f : T \to T^{'}$ and $g : T^{'} \to T$ such that $g f = 1_{T}$ and $f g = 1_{T^{'}}$ . The dual of this is just the statement that there is some $f : T \leftarrow T^{'}$ and $g : T^{'} \leftarrow T$ such that $f g = 1_{T}$ and $g f = 1_{T^{'}}$ , this is exactly the same property! (The morphisms $f$ and $g$ have just been renamed). Hence, the dual of the statement that a terminal object is unique up to isomorphism is the statement that every initial object is unique up to isomorphism.

Similarly, if something is true for every category with an initial object, its dual will be true for every category with a terminal object.

The concept of duality can be a powerful way of obtaining new results which come easily within category theory, but which are not obvious in the theory to which category theory is being applied. As an advanced example, the category of Boolean Algebras is dual to the category of Stone Spaces. See, Stone Duality on Wikipedia for the motivation.

Functors

A functor is a morphism between categories.

Given two categories $A$ and $B$ , a functor $F$ from $A$ to $B$ , written $F : A \to B$ is defined as a pair of functions:

$F_{0} :$ Objects( $A$ ) $\to$ Objects( $B$ )
$F_{1} :$ Morphisms( $A$ ) $\to$ Morphisms( $B$ )

Which satisfy:

1. Preservation of domain and codomain: If $f : X \to Y$ then $F_{1} (f) : F_{0} (X) \to F_{1} (Y)$ . ( Put differently, Dom( $F_{1} (f)$ ) = $F_{0}$ (Dom( $f$ )) and Cod( $F_{1} (f)$ ) = $F_{0}$ (Cod( $f$ )) for every morphism $f$ . )

Preservation of Identity: If the morphism $1_{X} : X \to X$ is the identity on $X$ , then the morphism $F_{1} (1_{X}) : F_{0} (X) \to F_{0} (X)$ is the identity on $F_{0} (X)$ .
Preservation of composition: Given morphisms $f : X \to Y$ and $g : Y \to Z$ , then the composition of their images $F_{1} (g) \circ F_{1} (f) : F_{0} (X) \to F_{0} (Z)$ is the image of their composition $F_{1} (g \circ f) : F_{0} (X) \to F_{0} (Z)$ .

Instead of differentiating $F_{0}$ and $F_{1}$ , they are usually both written simply as $F$ . E.g. $F (f) : F (X) \to F (Y)$ .

Properties of Morphisms

Morphisms are the central objects of study in category theory. For this reason, properties of morphisms can be very important. A morphism $f : X \to Y$ is called the following if it satisfies the given property:

Isomorphism: (Self-dual)

There exists some $g : Y \to X$ such that $g f = 1_{X}$ and $f g = 1_{Y}$ .

Intuitively, an isomorphism is a way of transforming from one object to another in a way that makes them indistinguishable using the information of the category.

Monomorphism: (Dual to epimorphic)

For any object $W$ and morphisms $g, h : W \to X$ , if $f g = f h$ then $g = h$ .

Intuitively, $f$ being a monomorphism indicates that all of the information captured by the collection of morphisms into $X$ is preserved when composing by $f$ . It generalizes the notion of an injective function, since in most concrete categories (like sets, groups, and topological spaces) every injective map is a monomorphism. However, even in concrete categories (and certainly more generally), monomorphisms need not be injective.

Epimorphism: (Dual to monomorphic)

For any object $Z$ and morphisms $g, h : X \to Z$ , if $g f = h f$ then $g = h$ .

Intuitively, $f$ being an epimorphism indicates that all the information captured by the collection of morphisms out of $Y$ is preserved when composing by $f$ .. It generalizes the notion of a surjective function. However, in an even stronger sense than for monomorphisms, a function being epimorphic and a function being surjective are far from equivalent.

Properties that more closely match surjectivity include Section / Split Epimorphism, and regular epimorphism. strict epimorphism, strong epimorphism, and extremal epimorphism. Note that despite the names, not all of these are necessarily epimorphisms, but are epimorphisms in "nice" categories.

Endomorphism: (Self-dual)

$X = Y$ , i.e., $f : X \to X$ .

An endomorphism is a morphism from an object to itself.

Automorphism: (Self-dual)

The morphism $f$ is both an endomorphism and an isomorphism.

An automorphism is a morphism from a structure to itself that preserves all the information of the structure that is distinguishable by the category. Intuitively, it gives "another view" of a structure (say, by moving around its elements) that leaves it essentially unchanged.

Retraction / Split Monomorphism: (Dual to split epimorphic)

There exists some $g : Y \to X$ such that $g f = 1_{X}$

A morphism is a retraction if its effect can be "reversed" or inverted by another morphism applied after it. For example, every injective map is a retraction. The morphism which inverts the retraction is a section.

Section / Split Epimorphism: (Dual to split monomorphic)

There exists some $g : Y \to X$ such that $f g = 1_{Y}$

A morphism is a section if it "reverses" the effect of some other morphism applied before it. The morphism which is inverted is a retraction.

LESSWRONG
LW

LESSWRONG
LW

Definition

Motivation

Categories Give an External View

Common Symbols: Convention

Isomorphisms in Category Theory

Universal Properties

Duality

Functors

Properties of Morphisms

Limits and Colimits

Further Universal Constructions

Natural Transformations

Constructions on Categories

Adjunctions and Adjoint Functors