Basic notions of category theory

In this first blog post (and some uncertain amount of future posts) I hope to delve a bit into something I've always been curious about, but have only recently read a bit into, namely, the subject of category theory. Now, this is something which does not have any particularly strong connection with the research I'm doing at the moment, and indeed, for the kind of physics I do everyday, category theory seems like a hopelessly abstract toolkit which is practically useless. However, it has become clear to me, by reading some abstracts and skimming through papers on the arXiv by Xiao-Gang Wen, Kitaev, and a lot of other people, along with finding the nLab and John Baez's stuff, that this area of mathematics is extremely important in a variety of extremely captivating and fundamental topics in physics, like topological quantum field theory, knots and many theoretical aspects within condensed matter. Of particular interest to me is the notion of topological order, topological quantum computation, anyons, the fractional quantum hall effect, etc.

I will hopefully cover a lot of different cool stuff while I focus on category theory in this blog. For starters, thanks to my lovely girlfriend, I've had the chance to follow along a course on quantum logic, in which categorical quantum mechanics was a main topic of discussion. So, in some following posts I hope to write down some of the things I've been reading about, namely how category theory comes into play in foundations of quantum mechanics, quantum information, and models for quantum computation such as the measurement based approach. I will follow first the book of Chris Heunen and Jamie Vicary called "Categories for Quantum Theory - An introduction", but I might sprinkle in some other stuff from Coecke's and Kissinger's "Picturing Quantum Processes". Nevertheless I will most definitely get to covering the more solid-state-centric concepts and topological order eventually.

I should also note that these blog posts may have a fairly self-centered purpose, and will always be very unpolished. Mainly, they are just about me presenting my reading and coalescence of thoughts on certain topics. Things may not always be very clear or self-contained and mistakes will be unavoidable: Such is the learning process, which is what I hope to document here. Hopefully they will be mostly correct! Anyway, if anyone ever ends up reading these things and wishes to discuss or correct something I've written, feel free to contact me.

Ok, so what will I talk about today? The main point is to introduce some ideas of category theory: The concept of a category, the notion of functors, equivalences, natural transformations, and universal properties, such as products and coproducts, initial and terminal objects, as well as equalizers and kernels. This sets up the basics for the next, hopefully more interesting post, which will be about monoidal categories.

Categories, functors and natural transformations

Let's start with the definition of a category:

Definition:

A category \(\boldsymbol{C}\) is made up of:

A collection of objects \(\text{Ob}(\boldsymbol{C})\);
For every pair of objects \(A,B\in\text{Ob}(\boldsymbol{C})\), a collection of morphisms \(\boldsymbol{C}(A,B)\) with domain \(A\) and codomain \(B\). Such a morphism is an arrow \(f:A\to B\), when \(f\in\boldsymbol{C}(A,B)\). Sometimes this is also written \(\text{Hom}(A,B)\) and called the Hom-set.

Such that:

There exists an identity endomorphism (an arrow from an object to itself) for every \(A\), i.e. \(\forall A\in\text{Ob}(\boldsymbol{C}):\exists\text{id}_{A}:A\to A\);
There is a composition of arrows, i.e. \(\exists\circ:\boldsymbol{C}(A,B)\times\boldsymbol{C}(A,B)\to\boldsymbol{C}(A,B)\) with \(\forall f\in\boldsymbol{C}(A,B),\forall g\in\boldsymbol{C}(A,B):\exists g\circ f:A\to C\), such that \(\forall A,B,C,D\in\text{Ob}(\boldsymbol{C}),\forall f:A\to B,\forall g:B\to C,\forall h:C\to D\):

\(h\circ\left(g\circ f\right)=\left(h\circ g\right)\circ f\);
\(f\circ\text{id}_{A}=f=\text{id}_{B}\circ f\).

So, in words, a category is a family of objects with arrows between these objects. The arrows can be composed, and there exists a distinguished arrow for every object, called the identity, which when composed with another arrow does nothing. The axioms of a category can be expressed in terms of commutative diagrams

Commutative diagrams are everywhere in category theory literature. They sometimes make proofs easier to read and reason about. Now, the flagship example of a category is Set, which is the category where objects are sets and morphisms are functions between sets. Composition is defined in the usual way, of course: Given \(f:A\to B\) and \(g:B\to C\), their composition is \(g\circ f:A\to C\) where for every \(a\in A\), \(g\circ f(a)=g(f(a))\). The identity is simply \(\text{id}_{A}(a)=a\) for every set \(A\) and element \(a\in A\).

Another example of a category is Rel, which is the category of relations, with objects being sets, and morphisms being relations. What are relations? Given two sets \(A\) and \(B\) a relation is a subset \(R\subseteq A\times B\). The idea is that an element \(a\in A\) is related to an element \(b\in B\) if \(\left(a,b\right)\in R\). Composition is a bit more tricky, with \(R:A\to B\) and \(S:B\to C\) being composed as \(R\circ S=\left\{ \left(a,c\right)\in A\times C|\exists b\in B:\left(a,b\right)\in R,\left(b,c\right)\in S\right\}.\) In other words, an object \(a\) is related to an object \(c\) via \(R\circ S\) if there is an intermediate object \(b\) in \(B\) such that \(a\) is related to \(b\) and \(b\) is related to \(c\). It puts us in mind of the transitivity property of equivalence relations. Another interesting one is Hilb: the category with objects corresponding to Hilbert spaces, and arrows which are linear transformations between them. Relations are somewhere in the middle between Set as a "classical" kind of category and Hilb, which is a "quantum" kind of category. I'll leave further discussion of Rel and Hilb for another rainy day, and pursue instead more formal developments of category theory. Before, some other common categories are Vect, of vector spaces and linear transformations, Grp of groups and group homomorphisms and many others. Again, much stuff to talk about some other time, but the key message is that all of the important structures of mathematics and physics, and the mappings, functions or relations between them can be expressed within the language of category theory.

Moving on, a particularly important type of arrow, is an "isomorphism", which is just an arrow \(f:A\to B\) with an inverse \(f^{-1}:B\to A\) such that their composition, no matter the order, gives the identity \[\begin{align*}f\circ f^{-1} &=\text{id}_{A},\\ f^{-1}\circ f &=\text{id}_{B}.\end{align*}\] Two objects are isomorphic if there exists an isomorphism between them. We write \(A\simeq B\) if \(A\) is isomorphic to \(B\). In category theory for every single definition, there is a million different ways of weakening or strengthening definitions, and these are given a million different names. This makes it so space is more economically used, and often relates these concepts to people familiar with different areas of mathematics, but makes reading papers harder for people with less experience and for physicists with more limited knowledge of pure mathematics, like myself. For instance, in physics an invertible function often gives the identity when composed with its inverse on the left and right always, but in mathematics this is not always the case, hence one introduces the notion of left-invertible and right-invertible in the obvious manner, and even calls right invertible arrows "retractions". Uniqueness of inverses can be proved easily, and we do not do it here.

There are a bunch more names for special kinds of categories as well:

A category is skeletal if any two isomorphic objects are equal, i.e. \(A\simeq B\implies A=B\)
A groupoid is a category in which every morphism is an isomorphism.
A group is a groupoid with one object
A category is discrete when all the morphisms are identities
A category is indiscrete when there is a unique morphism \(A\to B\) for each two objects \(A\) and \(B\)

We can also make up new categories from old ones

The opposite category to \(\boldsymbol{C}\), denoted \(\boldsymbol{C}^{\text{op}}\) has the same objects as \(\boldsymbol{C}\) but all the arrows are reversed \(\boldsymbol{C}^{\text{op}}(A,B)=\boldsymbol{C}(B,A)\)
The product category of \(\boldsymbol{C}\) and \(\boldsymbol{D}\) is denoted by \(\boldsymbol{C}\times\boldsymbol{D}\) and its objects are pairs \(\left(A\in\text{Ob}(\boldsymbol{C}),B\in\text{Ob}(\boldsymbol{D})\right)\) and morphisms are pairs \(\left(f,g\right):\left(A,B\right)\to\left(C,D\right)\), with \(f:A\to C\) and \(g:B\to D\).
A category \(\boldsymbol{C}\) is a subcategory of \(\boldsymbol{D}\) when every object of \(\boldsymbol{C}\) is an object of \(\boldsymbol{D}\), the same goes for morphisms and it has the same composition and identities.

A skeleton of a category, is a name given to the subcategory \(\boldsymbol{S}\) of a category \(\boldsymbol{C}\) which contains a single object from every isomorphism class in \(\boldsymbol{C}\).

All categories admit a graphical calculus: Objects are vertical lines, and morphisms are boxes between vertical lines, with one input at the bottom and one output at the top. The cool thing about this graphical calculus is that the axioms of the category all make intuitive sense:

Identities are not drawn, and therefore composition with them leaves a certain morphism invariant, and also associativity is built into the drawings (no brackets are drawn). Succinctly

Flipping this graphical calculus on the side simply gives the usual algebraic constructions. The point is that categories with additional structure can admit "parallel" morphisms, and the graphical language becomes much more useful due to the additional 2D degrees of freedom of a drawing, when compared with a string of algebraically meaningful symbols. I'll cover the basics of this in the next post, when I cover monoidal categories. For now, a few more notions are in order. Since categories are such a general construction, it is useful to relate them. This seems to have been their original purpose, as we can prove things easily in some categories and by showing that they can be mapped into other categories obtain proofs which may be difficult to obtain directly in the setting.

Definition:

Relationships between categories are described by functors. Functors relate both objects and morphisms from different categories, namely, if \(\boldsymbol{C}\) and \(\boldsymbol{D}\) are categories, a functor \(F:\boldsymbol{C}\to\boldsymbol{D}\) is given by

a mapping of objects, which associates to every \(A\in\text{Ob}(\boldsymbol{C})\) an object \(F\left(A\right)\in\text{Ob}(\boldsymbol{D})\)
a mapping of arrows, which associates to every \(f:A\to B\in\boldsymbol{C}(A,B)\) an arrow \(F(f):F(A)\to F(B)\in\boldsymbol{D}(F(A),F(B))\). This must preserve the categorical structure, i.e. we must have the functorial relations
\(F\left(\text{id}_{A}\right)=\text{id}_{F\left(A\right)}\) for all \(A\in\text{Ob}(\boldsymbol{C})\)
\(F(g\circ f)=F\left(g\right)\circ F\left(f\right)\), \(\forall f:A\to B, g:B\to C\)

A redundant name used to describe functors is that they are "covariant". This is introduced in order to oppose the notion of a "contravariant functor", which is a construction in every respect equal to the functor but with \(F(g\circ f)=F\left(f\right)\circ F\left(g\right).\) If a category is a group, a functor is merely a group homomorphism, which may be a good way to remember the functorial relations.

Two categories are equivalent when they have exactly the same structure. This notion of equivalence of categories, is formalized by a special kind of functor. A functor is an equivalence when

It is full: For any two objects \(A\) and \(B\), the functions \(\boldsymbol{C}(A,B)\to\boldsymbol{D}\left(F(A),F(B)\right)\) given by \(f\mapsto F(f)\) are surjective
It is faithful: For any two objects \(A\) and \(B\), the functions \(\boldsymbol{C}(A,B)\to\boldsymbol{D}\left(F(A),F(B)\right)\) given by \(f\mapsto F(f)\) are injective
It is essentially surjective on objects: For every object \(B\in\text{Ob}(\boldsymbol{D}),\) there exists \(A\in\text{Ob}(\boldsymbol{C})\) such that \(B\) is isomorphic to \(F(A)\). This means that the functor acts surjectively on objects up to an isomorphism

These notions can be used to simplify (or make the reading more complicated) the definition of a subcategory as well as the skeleton of a category:

\(\boldsymbol{C}\) is a subcategory of \(\boldsymbol{D}\) if the inclusion \(\boldsymbol{C}\to\boldsymbol{D}\) is a faithful functor
\(\boldsymbol{S}\) is a skeleton of \(\boldsymbol{C}\) if \(\boldsymbol{S}\) is skeletal and the inclusion functor is an equivalence

Finally, lets get to natural transformations: A functor is a map between categories, and a map between functors is a natural transformation. These ideas of "maps between maps between maps between maps" is the kind of thing the category theorist loves, and maybe one day I'll get to learning some notions of higher category as well, which formalizes the structure of these kinds of things.

Definition:

Given two functors \(F:\boldsymbol{C}\to\boldsymbol{D}\) and \(G:\boldsymbol{C}\to\boldsymbol{D}\) a natural transformation \(\zeta:F\implies G\) assigns to every object \(A\) in \(\boldsymbol{C}\) a morphism \(\zeta_{A}:F(A)\to G(A)\) in \(\boldsymbol{D}\), such that, for every morphism \(f:A\to B\) in \(\boldsymbol{C}\), the following diagram commutes

Each morphism \(\zeta_{A}\) is called a component of \(\zeta\), and if every component is an isomorphism, then \(\zeta\) is called a natural isomorphism.

We can now characterize equivalence differently: A functor \(F:\boldsymbol{C}\to\boldsymbol{D}\) is an equivalence if there exists a functor \(G:\boldsymbol{D}\to\boldsymbol{C}\) and natural isomorphisms \(G\circ F\simeq\text{id}_{\boldsymbol{C}}\) and \(\text{id}_{\boldsymbol{D}}\simeq F\circ G\), where \(\text{id}_{\boldsymbol{C}}:\boldsymbol{C}\to\boldsymbol{C}\) and \(\text{id}_{\boldsymbol{D}}:\boldsymbol{D}\to\boldsymbol{D}\) have every component \(\text{id}_{A}:A\to A\) whether \(A\in\boldsymbol{C}\) or \(A\in\boldsymbol{D}\).

This characterization may seem pointless, but note that the first definition of equivalence I gave is written in terms of the internal structure of the categories, while this latter one is given in terms of its external context, i.e. the existence of functors and natural transformations between the categories. This is precisely the kind of thing which I hear that higher category describes and handles well.

Limits

Ok, so far we have looked into what a category is and took a few steps in the "maps between maps between maps between maps" direction of things, by introducing functors and natural transformations. Another important concept in category theory is that of limits. I will not give a general treatment of limits today, but I may some other time when something which needs a more in depth treatment of this subject comes up. For now, I will instead give a series of definitions of certain universal properties which are examples of limits:

Definition:

If \(\boldsymbol{C}\) is a category and \(A,B\in\text{Ob}(\boldsymbol{C})\), the product is an object \(A\times B\) together with arrows \(\pi_{A}:A\times B\to A\) and \(\pi_{B}:A\times B\to B\) such that \(\forall C\in\text{Ob}(\boldsymbol{C})\) and for morphisms \(f:C\to A\) and \(g:C\to B\) there exists a unique morphism \(\left\langle f,g\right\rangle :C\to A\times B\) such that \(\pi_A \circ \langle f,g\rangle = f\) and \(\pi_B \circ \langle f,g\rangle = g\). This can be expressed in the form of the following commutative diagram

Definition:

If \(\boldsymbol{C}\) is a category and \(A,B\in\text{Ob}(\boldsymbol{C})\), a coproduct of \(A\) and \(B\) is an object \(A+B\) together with arrows \(\iota_{A}:A\to A+B\) and \(\iota_{B}:B\to A+B\) such that \(\forall f:A\to C\) and \(\forall g:B\to C\), \(\exists!\left[f,g\right]:A+B\to C\) such that \([f,g] \circ \iota_A = f\) and \([f,g] \circ \iota_B = g\). This can also be expressed in terms of the following commutative diagram:

The co-product is the dual notion of the product. One merely reverses all the arrows in the diagram which defines the product. It is useful to give some examples of the notion of products and coproducts. In Set, products are given by the Cartesian product, and coproducts by the disjoint union. In Rel, products and coproducts are both given by the disjoint union.

Definition:

An object \(I\in\text{Ob}(\boldsymbol{C})\) in a category \(\boldsymbol{C}\) is initial when \(\forall A\in\text{Ob}(\boldsymbol{C})\) there exists a single arrow \(f_{A}:I\to A\).

Definition:

An object \(T\in\text{Ob}(\boldsymbol{C})\) in a category \(\boldsymbol{C}\) is terminal when \(\forall A\in\text{Ob}(\boldsymbol{C})\) there exists a single arrow \(g_{A}:A\to T\).

In Set, any one-element set is a terminal object, and the empty set is the initial object. In Rel, the empty set is both the terminal and initial object. Such an object, which is both initial and terminal is called a zero object, often denoted by \(0\). Furthermore, such an object induces unique maps \(0_{AB}:A\to B\), which are the unique maps factoring through the zero object \(A\to0\to B\).

A name for another special kind of category is a "Cartesian category" which admits a terminal object and products for any pair of objects. Set, for instance, is a Cartesian category.

The following universal property is concerned with the fact that given a pair of functions \(f:A\to B\) and \(g:A\to B\) it may be interesting to ask on which elements \(a\in A\), \(f(a)=g(a)\). The focus on morphisms inherent to category theory pushes us into focusing not on the elements, but rather using a universal property to obtain the same information. This leads to the notion of an equalizer

Definition:

Given \(f,g\in\boldsymbol{C}(A,B)\) in a category \(\boldsymbol{C}\), their equalizer is a morphism \(e:E\to A\) such that \(f\circ e=g\circ e\), such that any morphism \(e':E'\to A\) which satisfies \(f\circ e'=g\circ e'\) allows a unique \(m:E'\to E\) with \(e'=e\circ m\). In terms of a commutative diagram, we have

Much like the coproduct construction, the coequalizer is the equalizer in the opposite category. The final definition we shall provide here is a special case of an equalizer, called a kernel.

Definition:

A kernel of a morphism \(f:A\to B\) in a category \(\boldsymbol{C}\) is an equalizer of \(f\) and the zero morphism \(0_{AB}:A\to B\).

Some more words on the future

So this has been a brief introduction to some ideas of category theory. I am still unsure as to how I will format my posts and how frequent they will be, but my idea is to keep them short enough to be digestible and easy to write. Things may seem half-baked for now, but I shall make use of the blog format and keep adding to what I've written here in order to further develop each of the small topics I've mentioned. Some things I've left open for now are:

Examples in the category Rel
Examples in the category Hilb
The general notion of a limit

In the future, whenever I feel like it, I will cover some of these things. The next post will be on Monoidal categories!