Category

Informally, a category is just a collection of things, along with a particular relationship between these things. For example, imagine the collection of all possible states our world could be in (Einstein being the American president, dogs not existing, and any other wacky thing you can come up with). In any particular world \(W_1\), there are other worlds \(W_2\) that we can "get to" if some sequence of events were to occur, transforming \(W_1\) into \(W_2\). At the very least, every state can "get to" itself by "doing nothing." For example, I can get from a world where I have an apple to a world where I don't by eating the apple, or giving it away, or throwing it in a lake, etc.

Formally, a category \(C\) is a collection of objects (often written \(\texttt{ob}(C)\)) and a collection of arrows (often called "morphisms," each starting at an object and ending at an object). To be a valid category, there are some requirements these collections need to satisfy. It's very helpful to draw these on paper. For any object \(X\) in \(C\), there must be a morphism from \(X\) to \(X\) (drawn as a little loop at \(X\)) that "does nothing" (typically written \(id_X\) or \(1_X\) but sometimes unfortunately written as just \(X\) when what is meant is "clear from context"). This is called an "identity arrow," "identity on \(X\)," or "identity of \(X\)." Also, for any objects \(X\), \(Y\), and \(Z\) in \(C\), for any two morphisms \(f:X\to Y\) and \(g:Y\to Z\), there must be a morphism \(g\circ f:X\to Z\) (pronounced "\(g\) after \(f\)") that is exactly the same as following \(f\) from \(X\) to \(Y\) and from there following \(g\) to finally get to \(Z\). This is called the composition of \(f\) and \(g\), and the composition operator \(\circ\) must be associative. These requirements are drawn formally with the following diagrams. These diagrams are called "commutative diagrams" or "commuting diagrams," meaning that any two paths from one object to another must be equal (one says the diagram "commutes"). Therefore, each diagram is visually representing a bunch of equations, such as \(f\circ id_X=f\).

These requirements aren't too difficult to satisfy; categories show up all over the place. Any transitive, reflexive relation (these are called "preorders") gives rise to a category, including \(\leq\) on the integers. So for any integer, say \(7\), it's less than or equal to itself (\(7\leq 7\)). And for any three integers \(a\), \(b\), and \(c\), if \(a\leq b\) and \(b\leq c\), then \(a\leq c\). And of course, \(\leq\) is associative.

You'll also find a category in any "monoid," that is, an associative binary operation (like \(+\)) on a set (like the integers) which has a unit for the operation (like \(0\)). You can form a category with a single object \(M\) where the arrows all loop from \(M\) back to \(M\), representing the elements of the set (such as the integers). So for example, \(1:M\to M\), \(2:M\to M\), etc. \(M\) is called a "monoid object." This is a proper category because any two of these arrows can be composed using the binary operation, which we've required to be associative. For example, \(3+4:M\to M\). And there's an arrow for the unit (such as \(0\), for \(+\)) that behaves as the identity arrow of \(M\).

*Psst-- Draw those examples out on a sheet of paper! Show some example diagrams! It really helps ideas crystallize. Here's one:*

It's been said in some category theory learning material that I can't find now that a category is something like a bridge between the definition of a preorder and the definition of a monoid, capturing each in a way that extends the other. This is an informal idea but I found it helpful. A preorder is a category with multiple objects but only one arrow (at most) between each object, and a monoid is a category with multiple arrows but only one object. Bartosz Milewski (a popular category theory educator) suggested that a category can also be seen as a "proof-relevant" preorder, meaning objects can be related to each other and themselves in multiple ways that are seen as distinct, as opposed to typical relations which either relate two given objects or don't.

In programming, we typically use a slightly different-looking category. Namely, we typically use categories where the objects are types (or some similar collection, like sets) and the arrows are functions (or function-like in some way). That's why I've been naming objects uppercase and naming morphisms starting from "f." This particular kind of category has certain properties right out the gate. The "relationships" between objects aren't propositions (like \(4\leq 5\)) but transformations (like \(f(x)=x+1\)). We often have values within objects (since the objects are collections), which wouldn't make sense with an object like \(7\). That means there are multiple distinct values, like \(7\) or \(8\), that are different from each other but represented by the same object in the category (say, int). Category theory can't talk about these values directly (it can hardly say things about even the objects, as it generally uses morphisms for all reasoning) though if you have something like a singleton set \(S\) then the set of all functions from \(S\) to any set \(X\) is equivalent to the set \(X\) itself, and gives a way of talking about the elements of \(X\) in category theory. Categories where the objects are collections are EXTREMELY powerful, and it's the main reason we say a category has a "collection" of objects instead of a "set;" we'd like to be able to construct categories where the objects are all the sets, and there's no set-of-all-sets so this category's objects don't form a set. "Small" categories are ones where the objects form a set, and "large" categories are the rest, and include many interesting and powerful categories.

I think these categories-of-collections are also very useful and underappreciated for analytic philosophers, which is why the first example category I gave was an analysis of possible worlds. That category is an example where objects have an enormous amount of information (the entire state of the world), and arrows are transformations (sequences of events).

Small categories form a famous and powerful category called Cat.

© 2024 Ryan Brewer.