# Examples of Categories

post by countedblessings · 2019-10-10T01:25:32.374Z · LW · GW · 2 commentsBefore 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

__Rule of composition__: function composition, e.g.,

__Associativity__:

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 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 in a category, then you do not also have 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 but not , you could think of and as being in an order. For example, you could represent natural numbers, e.g., , etc., as objects and have the morphism be "less than or equal to," i.e., the sign. Then means "." 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!)

Posets are *partial* orders in the sense that there can be *at most* one morphism between and . 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 would mean that that the basketball player is less than or equal to in skill than basketball player . However, suppose, that is a soccer player. Then morphisms like or 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 and , 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 and another poset like . 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 and are *equivalent.* That is to say, if you start at , you can go right then down to get to , or down then right to get to , 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 to 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.

The example of associativity seems a little strange, I'm note sure what's going on there. What are the three functions that are being composed?

Two of my favorite categories show that they really are everywhere: the free category on any graph and the presheaves of gamma.

The first: take any directed graph, unfocus your eyes and instead of arrows consider paths. That is a category!

The second: take any finite graph. Take sets and functions that realize this graph. This is a category, moreover you can make it dagger-compact, so you can do quantum mechanics with it. Take as the finite graph gamma, which is just two vertex with two arrows between them. Sets and functions that realize this graph are... any graph! So, CT allows you to do quantum mechanics with graphs.

Amazing!