Category theory: abstracting mathematical construction (essay)

Definition. A category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathcal{C}} consists of the following data:

1. A class Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{ob}(\mathcal{C})} , called the "objects" of the category
2. For any two objects Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X,Y \in \text{ob}(\mathcal{C})} , a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{mor}_{\mathcal{C}}(X,Y)} , called the "morphisms from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X } to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle Y } ." We take Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f : X \rightarrow Y} to be a statement which means the exact same thing as the statement $f\in {\text{mor}}_{\mathcal {C}}(X,Y)$.
3. For any two morphisms Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f : X \rightarrow Y} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g : Y \rightarrow Z} , a function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \circ : \text{mor}_{\mathcal{C}}(Y,Z) \times \text{mor}_{\mathcal{C}}(X,Y) \rightarrow \text{mor}_{\mathcal{C}}(X,Z), } which we call "composition." That is, we can compose Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g } to get an element Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g \circ f : X \rightarrow Z } ,

subject to the following conditions:

1. For any object Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \in \text{ob}(\mathcal{C}) } , there exists an "identity" morphism Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1_X : X \rightarrow X } , satisfying $1_{X}\circ f=f$ for any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f : Y \rightarrow X } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g \circ 1_X = g } for any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g : X \rightarrow Z } .
2. Composition is associative: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (f \circ g) \circ h = f \circ (g \circ h) } .

♦

One example of a category---the example, in fact---is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Set} } , the category of sets. The objects of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Set} } are sets, the morphisms of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Set} } are functions, and composition of morphisms of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Set} } is composition of functions: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (g \circ f)(x) : = g(f(x)). } The identity morphism of a set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} is the function Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \rightarrow X } which does nothing.

Another example of a category is "the discrete category with 2 elements," which I shall call Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{I} } . The objects Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{ob}(\mathbb{I}) } are a set consisting of 2 elements (for concreteness we could take Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{ob}(\mathbb{I}) := \{ a,b \} } where Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a = \emptyset } and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b = \{ \emptyset \} } ). The morphisms of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{I} } are the identity elements, and nothing else. More formally, we haveFailed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{mor}_{\mathbb{I}}(a,a) = \{ * \} } , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{mor}_{\mathbb{I}}(a,b) = \emptyset } , and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{mor}_{\mathbb{I}}(b,b) = \{ * \} } .

Another example of a category is the category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Grp} } of groups. Here, the objects are groups, and the morphisms are group homomorphisms.

Another example of a category is the (naive) category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Top} } of topological spaces. Here, the objects are topological spaces, and the morphisms are continuous maps.

We could go on like this ad infinitum. There are a huge variety of mathematical objects that form categories. Rings, graphs, vector spaces, representations, algebraic varieties, the points of the sphere, the open subsets of the plane, the natural numbers, compact Hausdorff totally disconnected spaces, etc etc. There is even a category of categories themselves. In fact, every mathematical object forms a category, though perhaps not in an interesting manner. Part of modern mathematical folklore is that you should always "categorify" whatever mathematical objects it is that you are working with, i.e. you should find a way to define everything in a category-theoretic way.

Note that the definition I gave of categories is set theoretic. Shea has reminded me that category theory can be taken as foundational (see here for Lawvere's attempt at that). I have barely studied Lawvere's ideas, but I am skeptical that it is useful as a foundation. One big reason why is that when it comes to actually proving things, set theory is much easier than category theory. It has been my experience that even the most routine, "obvious" things can become very difficult to prove when phrased categorically. I don't think this is just my own ineptitude; I think there is a deep reason why category theory is difficult, which I will explain later. It's not just me, either: When working mathematicians want to understand something category theoretic, they often do things that allow them to think about it in a set theoretic manner, e.g. they embed their category into the category of sets (see "Yoneda embedding").

Functors

I mentioned earlier that there is a category Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Cat}} of categories. Clearly the objects of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Cat}} are ... categories, but what are the morphisms of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \text{Cat}} ? They are called functors, and they are defined as follows.

Definition. A functor Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F : \mathcal{C} \rightarrow \mathcal{D}} is a function which sends any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle X \in \text{ob}(\mathcal{C})} to an object Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(X) \in \text{ob}(\mathcal{D})} , along with a function which sends any Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi \in \text{mor}_{\mathcal{C}}( X ,Y)} to an object Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(\varphi) \in \text{mor}_{\mathcal{D}}(F(X),F(Y))} . This assignment respects composition (meaning Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(\varphi \circ \psi) = F(\varphi) \circ F(\psi)} for any morphisms Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \varphi, \psi} ), and which respects identity (meaning Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(\text{Id}_{X} ) = \text{Id}_{F(X)} } for any object $X$). ♦

If you want examples of functors, you can find many of them in a category theory textbook. I won't give the standard examples here. I will only give one example, which demonstrates the essence and purpose of functors.

Let's suppose that we are mathematicians who wish to do some set-theoretic "construction." For example, one construction we could do is we could take any set $A$, and we could replace it with a set $A\sqcup A$, where $A\sqcup A$ is a set which has exactly two copies of every element of $A$. For example, if $A=\{a,b\}$ then we might have $A\sqcup A=\{(a,1),(b,1),(a,2),(b,2)\}$.

Now, let's suppose that we change $A$ in a "trivial" way. For example, instead of considering $A=\{a,b\}$, what if we considered $A'=\{a',b'\}$. Since $A$ and $A'$ are basically the same, nothing important would change. Instead of getting

$$A\sqcup A=\{(a,1),(b,1),(a,2),(b,2)\},$$

we would get

$$A'\sqcup A'=\{(a',1),(b',1),(a',2),(b',2)\},$$

which, again, is basically the same thing.

Now, why am I entitled to say that $A$ and $A'$ are "basically the same," and that replacing $A$ with $A'$ was trivial? Because all I did was I took the contents of $A$, and I added a symbol ' to both of them! That's not interesting. More formally, I think that $A$ and $A'$ are "the same" because I have in mind a function $\varphi :A\rightarrow A'$, which sends $a\mapsto a'$ and $b\mapsto b'$, and this function is an isomorphism; it has an inverse function $A'\rightarrow A$ which sends $a'\mapsto a$ and $b'\mapsto b$ . Likewise, I think that $A\sqcup A$ and $A'\sqcup A'$ are "basically the same" because there is an isomorphism $A\sqcup A\rightarrow A'\sqcup A'$ sending $(a,1)\mapsto (a',1)$, $(b,2)\mapsto (b',2)$, etc.

It is clear that $A$ and $A'$ didn't play any special role in our construction; we could have done the exact same thing for any set $S$. Thus, for an arbitrary set $S$, let's call $F(S):=S\sqcup S$. Furthermore, let's call the latter isomorphism of the above paragraph $F(\varphi ):F(A)\rightarrow F(A')$. It's also clear (exercise!) that $\psi :S\rightarrow T$ is any isomorphism of sets, then we get an isomorphism $F(S)\rightarrow F(T)$, which we shall call $F(\psi )$. Thus our construction defines a functor $F:{\text{Iso}}({\text{Set}})\rightarrow {\text{Iso}}({\text{Set}})$, where ${\text{Iso}}({\text{Set}})$ is that category whose objects are sets and whose morphisms are isomorphisms of sets.

Let's take a step back and observe what happened. We have a set-theoretic construction $S\mapsto S\sqcup S$. This set-theoretic construction is robust against arbitrary choices, in the sense that if we were to relabel all the elements of $S$ (that is, if we changed $S$ to an isomorphic set $S'$), then there is an obvious way to relabel all the elements of $S\sqcup S$. This robustness means precisely that our construction defines a functor.

This, in my view, is the essence of functors. Functors represent mathematical constructions, such that when you make an unimportant change to the input of the construction, it induces an unimportant change on the output of the construction.

As any mathematician (or computer programmer) knows, whenever you are constructing something (or programming something), there are tons of details which are "arbitrary," in the sense that they that could have been other than the way they are. We even faced this issue in the previous section, when I defined the category $\mathbb {I}$. To define the objects of $\mathbb {I}$, I needed a set with two elements, and I chose ${\text{ob}}(\mathbb {I} ):=\{\emptyset ,\{\emptyset \}\}$, but I could just as well have chosen ${\text{ob}}(\mathbb {I} ):=\{\{\emptyset \},\{\{\emptyset \}\}\}$, or ${\text{ob}}(\mathbb {I} ):=\{1,2\}$, or ${\text{ob}}(\mathbb {I} ):=\{*,\star \}$, or anything else, and it wouldn't have made a big difference. (Likewise, when programming a computer, it doesn't matter if we begin our for-loops at 0 and end at n-1, or begin them at 1 and end them at n.)

Functors are a way of talking about constructions, without making any arbitrary choices. Functors gain their "independence" from arbitrary choices because to build one, you have to say how it would handle any possible arbitrary choices. (Here we also see why category theory is difficult: to define a functor, you have to say how you would handle any possible choice, which is much more difficult than just saying how you would do the construction in some specific case).

Universal properties

There is another way in which categories handle arbitrary choices...

The history of category theory

Eillenberg-Steenrod axioms [TODO]