Examples of Categories

post by countedblessings · 2019-10-10T01:25:32.374Z · LW · GW · 2 comments

Contents

2 comments

Before we go through any more conceptual talk, let's explore some examples of categories to get a better feel of what they are.

Categories do two things:

1) They function as mathematical structures that capture our intuition about how models of cause-and-effect (composition) work in general.

2) They generalize other mathematical structures that capture our intuition about how specific models work.

Obviously, 1 and 2 are related. We model particular pieces of reality with particular mathematical structures (e.g., we model shapes with geometry), so generalizing how we model the world and generalizing fields of mathematics are highly related tasks.

Because I'm assuming my audience isn't familiar with any mathematical structures, we can't just start tossing out examples. Essentially the art of "categorifying" a mathematical structure is as simple as identifying what are the objects and what are the associatively composable morphisms. See here for a list of examples (scroll down to the table), which ought to give you an idea that many different kinds of mathematics really are just examples of categories on some level.

To give just one example of a mathematical structure generalized by category theory, you might be relatively familiar with the category known as Set, the category whose objects are sets and whose morphisms are functions—functions being very nice maps between sets. Functions compose, as we've already seen, and you can check that this composition is associative, so, voila, we've "categorified" a mathematical structure.

Set as category:

Objects: sets

Morphisms: functions

Identity morphism: identity function $f\left(x\right)=x$

Rule of composition: function composition, e.g., $2x^2$

Associativity: $2\left(x^2\right)=(2\times 1)x^2$

Since Set is pretty important, we'll discuss it in a separate post to make sure we're all on the same page about sets and functions. But hopefully this gives you an idea of what it looks like to take a "math thing" and make it into a category.

***

Even if you're not a math expert, you probably know that $2$ is bigger than 1. That's all the level of expertise required to understand a very important type of a category called a poset, which is category-speak for "partially ordered set." A partially ordered set is a set with an order than is at least partial.

A poset is any category for which there is at most one morphism between any two objects. I.e., if you have $A\to B$ in a category, then you do not also have $B\to A$ in the same category, unless B is merely a relabeling of A. (In which case the morphism is the identity morphism, as a poset also rules that there can only be at most one morphism between any object and itself, and since every object must have an identity morphism, there isn't any other possibility.)

A poset is partially ordered in the sense that, since $A\to B$ but not $B\to A$, you could think of $A$ and $B$ as being in an order. For example, you could represent natural numbers, e.g., $1,2,3$, etc., as objects and have the morphism be "less than or equal to," i.e., the $\le$ sign. Then $A\to B$ means "$A\le B$." Hence the category has an order—the objects are ordered by how big they are.

(Why less than or equal to and not simply less than? Because we need the identity morphism, and a number can't be less than itself. But it can be less than or equal to itself—by being equal to itself!)

A poset pictured. Composition would require than, since 1 is less than or equal to 2 and 2 is less than or equal to 3, it must be that 1 is less than or equal to 3 as well.

Posets are partial orders in the sense that there can be at most one morphism between $A$ and $B$. However, there does not need to be a morphism between them at all! For example, say your objects are sports players, and your morphism refers to "less than or equal to in skill." Then $A\to B$ would mean that that the basketball player $A$ is less than or equal to in skill than basketball player $B$. However, suppose, that $C$ is a soccer player. Then morphisms like $A\to C$ or $B\to C$ wouldn't really make sense. Hence, the orders in the category are only partial—they do not go through the entire category.

When you do have at least and at most one morphism between $A$ and $B$, that's called a total order. The natural numbers are in fact totally ordered by size. One is less than or equal to two, two is less than or equal to three, etc. (Examples of total orders are probably easier to think of than partial orders, but, as we'll see later, partial orders are sufficient to do the things we really care about having orders for, without needing to go so far as to necessitate that the order be total. I.e., partial orders let us assume less to get the same basic outcome for what we'll be doing later.)

Posets are really important for a couple of reasons. The main one is that posets are the simplest interesting kind of category. Posets are interesting because they can have morphisms between different objects, and morphisms are where all the interesting stuff in a category lie, as we'll see in a couple of posts. However, because there is at most one morphism between any two objects in a poset, posets stay fairly tame and simple. If you're ever confused by a concept in category theory, it's pretty much always a good idea to apply it to a poset so that you can see the idea in its simplest interesting form.

We'll also see that posets are very useful for studying what it means to do things in the best possible way—which is what adjunction, arguably the key concept of category theory, is all about.

***

One of the nice things about categories is how easily visualized their underlying structure is. For example, take a poset like $1\to 2\to 3$ and another poset like $a\to b\to c$. These are clearly very similar posets. (In fact, they're isomorphic.)

Despite the superficial differences, we clearly have "basically the same thing" going on with these two categories. So let's get abstract (which is what category theory is all about). Look at this category:

We've gotten rid of the labels on the objects and just replaced them with generic nodes. Using this framework, we can forget concerns about what specific category we're working with and just look at the general types of categories that can exist.

The most basic kind of category is the empty category, a category with no objects and therefore no morphisms. Obviously, we can't exactly depict this category visually—there's nothing to depict.

The "next" kind of category is a single object with just the identity morphism. Leaving the identity morphism implicit, it looks like this:

Growing more complex, we can add in a second object, but no morphisms between objects, just two objects and their identity morphisms.

A category with just identity morphisms is called discrete—the objects aren't connected to each other, hence the term. (Note that all discrete categories are posets—there is clearly at most one morphism between any two objects.)

Turning the above diagram into a poset (in this case a total order) is as easy as adding an arrow.

Here's something called a "commutative square. I'll add in labels to make it easier to follow.

The commutative square is a very important and famous shape in category theory. It commutes in the sense that the paths $A\stackrel{e}{\to }X\stackrel{g}{\to }Y$ and $A\stackrel{f}{\to }B\stackrel{h}{\to }Y$ are equivalent. That is to say, if you start at $A$, you can go right then down to get to $Y$, or down then right to get to $Y$, and it does not matter which path you choose. This is exactly analogous to how the knight moves in chess: typically (always? or does it not hold at the edge of the board?) there are two paths the knight can follow to get to a particular square from its current position, and it does not matter which path you choose.

In fact, it matters so little that you can just jump straight to the square, you don't have to trace out the "L" that the knight does. Similarly, you can just jump straight from $A$ to $Y$ without actually going down one of the two paths: that's composition.

A lot of important claims in category theory can be boiled down to saying that a particular diagram, often a square, commutes. For example, the basic definition of a natural transformation has at its center a commutative square—and properly defining natural transformations was the original motivation for developing category theory! (We'll talk about natural transformations quite a bit later.)

From here we can branch out in lots of different ways in terms of adding morphisms and objects, but you should get the general idea. Whenever you can think of a model that can be boiled down to nodes and arrows, it's probably a category. You should know that categories like the two categories depicted here are totally valid. You can have an infinite number of morphisms between two objects going back and forth. In the end, as long as the morphisms compose (associatively), you can do pretty much anything you want. We'll get a clearer view of exactly how to talk about this once we've discussed sets and functions in the next post.

2 comments

Comments sorted by top scores.