Examples of Categories

10Eigil Rischel

4MrMind

New Comment

2 comments, sorted by Click to highlight new comments since: Today at 2:41 PM

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!

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 structuresthat capture ourintuitionabout how models ofcause-and-effect(composition) workin general.2) They generalize

othermathematical structures that capture our intuition about howspecificmodels 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 aresetsand whose morphisms arefunctions—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: setsMorphisms: functionsIdentity morphism: identity function f(x)=xRule of composition: function composition, e.g., 2x2Associativity: 2(x2)=(2×1)x2Since

Setis 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 asetwith anorderthan isat leastpartial.A poset is

anycategory for which there isat most onemorphism between any two objects. I.e., if you have A→B in a category, then you do not also have B→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

orderedin the sense that, since A→B but not B→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 ≤ sign. Then A→B means "A≤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 equalto 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

partialorders in the sense that there can beat mostone 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→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→C or B→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

isless than or equal to two, twoisless 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 areinterestingbecause theycanhave 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→2→3 and another poset like a→b→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

betweenobjects, 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 clearlyat mostone 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 Ae→Xg→Y and Af→Bh→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 itdoes 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 aretwopaths the knight can follow to get to a particular square from its current position, and itdoes 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.