Category Archives: Category Theory

Fun with Functors

16 Replies

So far, we’ve looked at the minimal basics of categories: what they are, and how to categorize the kinds of arrows that exist in categories in terms of how they compose with other arrows. Just that much is already enlightening about the nature of category theory: the focus is always on composition.

But to get to really interesting stuff, we need to build up a bit more, so that we can look at more interesting constructs. So now, we’re going to look at functors. Functors are one of the most fundamental constructions in category theory: they give us the ability to create multi-level constructions.

What’s a functor? Well, it’s basically a structure-preserving mapping between categories. So what does that actually mean? Let’s be a bit formal:

A functor F from a category C to a category D is a mapping from C to D that:

  • Maps each member m in Obj(C) to an object F(m) in Obj(D).
  • Maps each arrow a : x rightarrow y in Mor(C) to an arrow F(a) : F(x) rightarrow F(y), where:
    • forall o in Obj(C): F(1_o) = 1_{F(o)}. (Identity is preserved by the functor mapping of morphisms.)
    • forall m,n in Mor(C): F(n circ o) = F(n) circ F(o). (Commutativity is preserved by the Functor mapping of morphisms.)

Note: The original version of this post contained a major typo. In the second condition on functors, the “n” and the “o” were reversed. With them in this direction, the definition is actually the definition of something called a covariant functor. Alas, I can’t even pretend that I mixed up covariant and contravariant functors; the error wasn’t nearly so intelligent. I just accidentally reversed the symbols, and the result happened to make sense in the wrong way.

That’s the standard textbook gunk for defining a functor. But if you look back at the original definition of a category, you should notice that this looks familiar. In fact, it’s almost identical to the definition of the necessary properties of arrows!

We can make functors much easier to understand by talking about them in the language of categories themselves. Functors are really nothing but morphisms – they’re morphisms in a category of categories.

There’s a kind of category, called a small category. (I happen to dislike the term “small” category, but I don’t get a say!) A small category is a category whose collections of objects and arrows are sets, not proper classes.

(As a quick reminder: in set theory, a class is a collection of sets that can be defined by a non-paradoxical property that all of its members share. Some classes are sets of sets; some classes are not sets; they lack some of the required properties of sets – but still, the class is a collection with a well-defined, non-paradoxical, unambiguous property. If a class isn’t a set of sets, but just a collection that isn’t a set, then it’s called a proper class.)

Any category whose collections of objects and arrows are sets, not proper classes, are called small categories. Small categories are, basically, categories that are well-behaved – meaning that their collections of objects and arrows don’t have any of the obnoxious properties that would prevent them from being sets.

The small categories are, quite beautifully, the objects of a category called Cat. (For some reason, category theorists like three-letter labels.) The arrows of Cat are all functors – functors really just morphisms between categories. Once you wrap you head around that, then the meaning of a functor, and the meaning of a structure-preserving transformation become extremely easy to understand.

Functors come up over and over again, all over mathematics. They’re an amazingly useful notion. I was looking for a list of examples of things that you can describe using functors, and found a really wonderful list on wikipedia.. I highly recommend following that link and taking a look at the list. I’ll just mention one particularly interesting example: groups and group actions.

If you’ve been reading GM/BM for a very long time, you’ll remember my posts on group theory. In a very important sense, the entire point of group theory is to study symmetry. But working from a set theoretic base, it takes a lot of work to get to the point where you can actually define symmetry. It took many posts to build up the structure – not to present set theory, but just to present the set theoretic constructs that you need to define what symmetry means, and how a symmetric transformation was nothing but a group action. Category theory makes that so much easier that it’s downright dazzling. Ready?

Every group can be represented as a category with a single object. A functor from the category of a group to the category of Sets is a group action on the set that is the target of the functor. Poof! Symmetry.

Since symmetry means structure-preserving transformation; and a functor is a structure preserving transformation – well, they’re almost the same thing. The functor is an even more general abstraction of that concept: group symmetry is just one particular case of a functor transformation. Once you get functors, understanding symmetry is easy. And so are lots of other things.

And of course, you can always carry these things further. There is a category of functors themselves; and notions which can be most easily understood in terms of functors operating on the category of functors!

This last bit should make it clear why category theory is affectionately known as abstract nonsense. Category theory operates at a level of abstraction where almost anything can be wrapped up in it; and once you’ve wrapped something up in a category, almost anything you can do with it can itself be wrapped up as a category – levels upon levels, categories of categories, categories of functors on categories of functors on categories, ad infinitum. And yet, it makes sense. It captures a useful, comprehensible notion. All that abstraction, to the point where it seems like nothing could possibly come out of it. And then out pops a piece of beautiful crystal. It’s really remarkable.

Category Diagrams

2 Replies

One of the most unusual things about category theory that I really love is category diagrams. In category theory, many things that would be expressed as equations or complex formulae in most mathematical formalisms can be presented as diagrams in category theory. If you are, like me, a very visual thinker, than category diagrams can present information in a remarkably clear form – and the categorical form of many statements of proofs can be much clearer than the alternatives because it can be presented in diagram form.

A category diagram is a directed graph, where the nodes are objects from a category, and the edges are morphisms. Category theorists say that a graph commutes if, for any two paths through arrows in the diagram from node A to node B, the composition of all edges from the first path is equal to the composition of all edges from the second path. (But it’s important to note that you do need to be careful here: merely because you can draw a diagram doesn’t mean that it necessarily commutes, just like being able to write an equation doesn’t mean that the equation is true! You do need to show that your diagram is correct and commutes.)

As usual, an example will make that clearer.

cat-assoc.jpg

This diagram is a way of expressing the associativy property of morphisms: f circ (g circ h) = (f circ g) circ h. The way that the diagram illustrates this is: g circ h is the morphism from A to C. When we compose that with f, we wind up at D. Alternatively, f circ g is the arrow from B to D; if we compose that with h, we wind up at D. The two paths: f circ (A rightarrow C) and (B rightarrow D) circ H are both paths from A to D, therefore if the diagram commutes, they must be equal. And the arrows on the diagram are all valid arrows, arranged in connections that do fit the rules of composition correctly, so the diagram does commute.

Let’s look at one more diagram, which we’ll use to define an interesting concept, the principal morphism between two objects. The principle morphism is a single arrow from A to B such that any composition of morphisms that goes from A to B will end up being equivalent to it.

In diagram form, a morphism m is principle if forall x : A rightarrow A, forall y: A rightarrow B, the following diagram commutes:

cat-principal.jpg

In words, this says that f is a principal morphism if for every endomorphic arrow x, and for every arrow y from A to B, f is is the result of composing x and y. There’s also something interesting about this diagram that you should notice: A appears twice in the diagram! It’s the same object; we just draw it in two places to make the commutation pattern easier to see. A single object can appear in a diagram as many times as you want to to make the pattern of commutation easy to see. When you’re looking at a diagram, you need to be a bit careful to read the labels to make sure you know what it means.

One more definition by diagram: (x, y) is a a retraction pair, and A is a retract of B (written A < B) if the following diagram commutes:

cat-retract.jpg

That is, x : A rightarrow B, y: B rightarrow A are a retraction pair if y circ x = 1_A.

Category Intuition by Example

11 Replies

The good thing about category theory is that it abstracts everything down to a couple of very simple, bare-bones concepts, and lets us play with those concepts in really fascinating ways. But the bad thing about category theory is that it abstracts everything down so much that it can be difficult to have any intuitive sense about what things actually mean.

We said that a category is, basically, a collection of objects connected by arrows, and a composition operation over the arrows. But what the heck is an object, and what is an arrow?

In some sense, the point of category theory is that it doesn’t matter. There’s a set of fundamental concepts that underly all composable mapping-like things, and category theory focuses in on those fundamental concepts, and what they mean.

But still, to understand category theory, you need to be able to get some kind of intuitive handle on what’s going on. And so, we’ll take a look at a few examples.

The Category Set

One of the easiest examples is the category Set. The objects of the category are, obviously, sets; the morphisms are functions between sets; and composition is (obviously) function composition.

That much is easy. Now, what about the special arrows? What do all of the epi, iso, endo, and auto arrows in the category of sets?

An monomorphism over the category of sets is an injective function – that is, a function which maps each value in the domain to a distinct value in the range. So you can always reverse the function: given a value in the range of the function, you can always say, specifically, exactly what value in the domain maps to it. In a monomorphism in the category set, there may be values in the target of the morphism that aren’t mapped to by any element of the range; but if a value of the range is mapped to, you know which value in the domain mapped to it.

The key property of the monomorphism is that it’s left-cancellative – that is, if f is a monomorphism, then we know that f circ g == f circ h is only true if g = h. We can cancel the left side of the composion. Why? Because we know that f maps each value in its domain to a unique value in its range. So f circ g and f circ h can only be the same if they map all of the same values in their domain to the same values in their range – that is, if they’re the same function.

An epimorphism is an onto function – that is, a mapping f from a set X to a set Y in which for every value y in Y, there’s some value in x in X such that f(x)=y. It’s a dual of the notion of a monomorphism; for each value in the range, there is at least one value in the domain that maps to it. But it’s not necessary that the domain values be unique – there can be multiple values in the domain that map onto a particular value in the range, but for every element of the domain, there’s always at least one value that maps to it. It’s right-cancellative in the same way that the monomorphism is left-cancellative.

What about iso-morphism? If you combine the ideas of mono-morphism and epi-morphism, what you end up with is a function where every member of the domain is mapped onto a unique value in the range, and every value in the range is mapped onto by at least one value: it’s a one-to-one function.

The Category Poset

Poset is the category of partially ordered sets. A partially ordered set is a set with a binary relation, le, which satisfies the following properties:

  1. Reflexivity: forall a: a le a
  2. Antisymmetry: if a le b land b le a then a = b.
  3. Transitivity: if a le b land b le c then a le c

In the category of partially ordered sets, the arrows are monotonic functions – that is, functions that preserve the partial ordering. So if x le y, then if f is monotonic, f(x) le f(y).

The arrow composition operation, circ, is still just function composition. In terms of meaning, it’s pretty much the same as it was for simple sets: a monomorphism is still a surjective function; etc. But in Poset it needs to be a surjective function that preserves the ordering relation.

We know that monotonic functions fit the associative and identity properties of category arrows – they’re still just functions, and monotonicity has no effect on those. But for posets, the composition is a bit tricky – we need to ensure that composition maintains the partial order. Fortunately, that’s easy.

  • Suppose we have arrows f : A rightarrow B, g : B rightarrow C. We know that f and g are monotonic functions.
  • So for any pair of x and y in the domain of f, we know that if x le y, then f(x) le f(y).
  • Likewise, for any pair s,t in the domain of g, we know that if s le t, then g(s) le g(t).
  • So we just put those together: if x le y, then f(x) le f(y). f(x) and f(y) are in the domain of g, so if f(x) le f(y) then we know g(f(x)) le g(f(y))

The category Grp

Our last example is the category of groups, which is called Grp. In this category, the objects are (obviously) groups. What are arrows? Group homomorphisms – that is, essentially, functions between sets that preserve the group structure.

What’s a homomorphism in this category? That’s a bit confusing, because we get stuck with some overloaded terminology. But it’s basically just a symmetry-preserving surjection – that is, it’s a reversable mapping from a group into a second group, where the group symmetry of the first group is mapped onto the group symmetry of the second by the arrow. You should be able to follow the meanings of the other kinds of morphisms by using similar reasoning.

These are all, of course, very simple examples. They’re all concrete categories, where the objects are (speaking very loosely) sets. There are categories – many very interesting ones – where the objects aren’t sets or even particularly set-like – but we’ll get to those later. For now, the ideas of objects as sets gives you an intuitive handle to grab onto.

Leading up to Topoi: Getting Back to Categories

26 Replies

As I mentioned a few posts ago, I recently changed jobs. I left Google, and I’m now working for foursquare. Now that I’m done with the whole job-hunting thing, and things are becoming relatively saner and settling down, I’m trying to get back to blogging.

One thing that I’ve been wanting to spend some time learning about is Topoi theory. Topoi theory is an approach to building logic and mathematics using category theory as a fundamental basis instead of set theory. I’ve been reading the textbook Topoi: The Categorial Analysis of Logic (Dover Books on Mathematics), and I’ll be blogging my way through it. But before I get started in that, I thought it would be a good idea to revise and rerun my old posts on category theory.

To get started, what is category theory?

Back in grad school, I spent some time working with a thoroughly insane guy named John Case who was the new department chair. When he came to the university, he brought a couple of people with him, to take temporary positions. One of them was a category theorist whose name I have unfortunately forgotten. That was the first I’d ever heard of cat theory. So I asked John what the heck this category theory stuff was. His response was “abstract nonsense”. I was astonished; a guy as wacky and out of touch with reality as John called something abstract nonsense? It turned out to be a classic quotation, attributed to one of the founders of category theory, Norman Steenrod. It’s silly and sarcastic, but it’s also not an entirely bad description. Category theory takes abstraction to an extreme level.

Category theory is one of those fields of mathematics that fascinates me: where you take some fundamental concept, and abstract it down to its bare essentials in order to understand just what it really is, what it really means. Just like group theory takes the idea of an algebraic operation, strip it down to the bare minimum, and discovering the meaning of symmetry; category theory looks at what happens if you take the concept of a function as a mapping from one thing to another, and strip it down to the bare minimum, and see what you can discover?

The fundamental thing in category theory is an arrow, also called a morphism. A morphism is an abstraction of the concept of homomorphism, which I talked about a bit when I was writing about group theory. Category theory takes the concept function mapping from one set of values to another, and strips it down to itsbarest essentials: the basic concept of something that maps from one thing to some other thing.

The obvious starting point for our exploration of category theory is: what the heck is a category?

To be formal, a category C is a tuple: (O, M, circ), where:

  1. O (or Obj(C)) is a set of objects. Objects can be anything, so long as they’re distinct, and we can tell them apart. All that we’re going to do is talk about mappings between them – so as long as we can identify them, it doesn’t matter what they really are. We’ll look at categories of sets, of numbers, of topological spaces, and even categories of categories.

  2. M (or Mor(C)) is a set of morphisms, also called arrows. Each morphism is a mapping from an object in O called its source, to an object in O called its target. Given two objects a and b in O, we’ll write Mor(a,b) for the set of morphisms from a to b. To talk about a specific morphism f from a to b, we’ll write it as f : a rightarrow b.

  3. circ is the composition operator: dot is a binary operation that is the abstraction of function composition; circ; given an arrow f in Mor(a,b), and an arrow g in Mor(b,c), f circ g in Mor(a,c). It’s got the basic properties of function composition:

    1. Associativity: forall f : a rightarrow b, g : b rightarrow c, h : c =rightarrow d) h circ (g circ f) = (h circ g) circ f.
    2. Identity: forall a,b in O(C): exists 1_a, 1_b in Mor(C): forall f : a rightarrow b: 1_b circ f = f = f circ 1_a.

One neat little trick to simplify things is that we can actually throw away Obj(C), and replace it with the set of identity morphisms: since there is exactly one identity morphism per object, there’s no real need to distinguish between the identity morphism and the object. It’s a nice trick because it means that we have nothing but morphisms all the way down; but it’s really just a trick. We can talk about Obj(C); or Id(C); but we still need to be able to talk about the objects in some way, whether they’re just a subset of the morphisms, or something distinct.

Now, we get to something about category theory that I really don’t like. Category theory is front-loaded with rather a lot of definitions about different kinds of morphisms and different kinds of categories. The problem with that is that these definitions are very important, but we don’t have enough of the theory under our belts to be able to get much of a sense for why we should care about them, or what their intuitive meaning is. But that’s the way it goes sometimes; you have to start somewhere. It will make sense eventually, and you’ll see why these definitions matter.

There are a lot of special types of morphisms, defined by properties. Here’s the basic list:

  • A monomorphism (aka a monic arrow ) is an arrow f : a rightarrow b such that forall g_1, g_2: x rightarrow a: f circ g_1 = f circ g_2 Leftrightarrow g_1 = g_2. That is, f is monic if and only if, when composed with other arrows, it always produces different results for different arrows.
  • An epic (or epimorphism) is an arrow f : a rightarrow b such that forall g_1, g_2: b rightarrow x): g_1 circ f = g_2 circ f Leftrightarrow g_1 = g_2. This is almost the same as a monic, but it’s from the other side of the composition; instead of f circ g_i in the definition, it’s g_i circ f; so an arrow is epic if when another arrow is composed with f, it always produces different results for different arrows.
  • An isomorphism is an arrow f : a rightarrow b such that exists g: b rightarrow a: f circ g = 1_b land g circ f = 1_a – an isomorphism is, basically, a reversible arrow: there’s a morphism that always reverses the action of an iso arrow.
  • An endomorphism is an arrow f : a rightarrow b where a = b. It’s sort of like a weak identity arrow.
  • An automorphism is an arrow that is both an endmorphism and an isomorphism.

One last definition, just because it gives me a chance to point out something useful about category theory. A functor is a morphism in the category of all categories. What that means is that it’s a structure-preserving mapping between categories. It’s neat in a theoretical way, because it demonstrates that we’re already at a point where we’re seeing how category theory can make it easier to talk about something complicated: we’re using it to describe itself! But the concept of functor also has a lot of applications; in particular, the module system of my favorite programming language makes extensive use of functors.

In Ocaml, a module is something called a structure, which is a set of definitions with constrained types. One of the things you often want to be able to do is to write a piece of code in a way that allows you to make it parametric on some other structure. The way you do that is to write a functor: a “function” from a structure to a structure. For example, to implement a generic binary tree, you need a type of values that you’ll put in the tree; and an operation to compare values. The way you do that is to write a functor which takes a structure defining a type and a comparison operator, and mapping it to a structure which is an implementation of a binary tree for that type and comparison.

The Ocaml functor is a category theoretic functor: category theory provides an easy way to talk about the concept of the compile-time “function” from structure to structure.

Topoi Prerequisites: an Intro to Pre-Sheafs

4 Replies

I’m in the process of changing jobs. As a result of that, I’ve actually got some time between leaving the old, and starting the new. So I’ve been trying to look into Topoi. Topoi are, basically, an alternative formulation of mathematical logic. In most common presentations of logic, set theory is used as the underlying mathematical basis – set theory and a mathematical logic built alongside it provide a complete foundational structure for mathematics.

Topoi is a different approach. Instead of starting with set theory and a logic with set theoretic semantics, Topoi starts with categories. (I’ve done a bunch of writing about categories before: see the archives for my category theory posts.)

Reading about Topoi is rough going. The references I’ve found so far are seriously rough going. So instead of diving right in, I’m going to take a couple of steps back, to some of the foundational material that I think helps make it easier to see where the category theory is coming from. (As a general statement, I find that category theory is fascinating, but it’s so abstract that you really need to do some work to ground it in a way that makes sense. Even then, it’s not easy to grasp, but it’s worth the effort!)

A lot of category theoretic concepts originated in algebraic topology. Topoi follows that – one of its foundational concepts is related to the topological idea of a sheaf. So we’re going to start by looking at what a sheaf is.

Continue reading →

Meta out the wazoo: Monads and Monoids

Leave a reply

Since I mentioned the idea of monoids as a formal models of computations, John Armstrong made the natural leap ahead, to the connection between monoids and monads – which are a common feature in programming language semantics, and a prominent language feature in Haskell, one of my favorite programming languages.

Continue reading →

Full Circle: the Categorical Monoid

Leave a reply

By now, we’ve seen the simple algebraic monoid, which is essentially an
abstract construction of a category. We’ve also seen the more complicated, but interesting monoidal category – which is, sort of, a meta-category – a category built using categories. The monoidal category is a fairly complicated object – but it’s useful.

What does a algebraic monoid look like in category theory? The categorical monoid is a complex object – a monoid built from monoids. If we render the algebraic monoid in terms of a basic category, what do we get? A monoid is, basically, a category with one object. That’s it: every algebraic monoid is a single object category.

But we can do something more interesting than that. We know what a monoidal category looks like. What if we take a monoidal category, and express the fundamental concept of a monoid in it?

Continue reading →

This is getting fun! On to Monoidal Categories.

Leave a reply

In the last post on groups and related stuff, I talked about the algebraic construction of monoids. A monoid is, basically, the algebraic construction of a category – it’s based on the same ideas, and has the same properties; just the presentation of it is different.

But you can also see a monoid in categorical terms. It’s what we computer scientists would call a bootstrapped definition: we’re relying on the fact that we have all of the constructs of category theory, and then using category theory to rebuild its own basic concepts.

Continue reading →

Clarifying Groupoids and Groups

Leave a reply

This post started out as a response to a question in the comments of my last post on groupoids. Answering those questions, and thinking more about the answers while sitting on the train during my commute, I realized that I left out some important things that were clear to me from thinking about this stuff as I did the research to write the article, but which I never made clear in my explanations. I’ll try to remedy that with this post.

Continue reading →

More Groupoids and Groups

Leave a reply

In my introduction to groupoids, I mentioned that if you have a groupoid, you can find
groups within it. Given a groupoid in categorical form, if you take any object in the
groupoid, and collect up the paths through morphisms from that object back to itself, then
that collection will form a group. Today, I’m going to explore a bit more of the relationship
between groupoids and groups.

Before I get into it, I’d like to do two things. First, a mea culpa: this stuff is out on the edge of what I really understand. My category-theory-foo isn’t great, and I’m definitely
on thin ice here. I think that I’ve worked things out enough to get this right, but I’m
not sure. So category-savvy commenters, please let me know if you see any major problems, and I’ll do my best to fix them quickly; other folks, be warned that I might have blown some of the details.

Second, I’d like to point you at Wikipedia’s page on groupoids as a
reference. That article is quite good. I often look at the articles in Wikipedia and
MathWorld when I’m writing posts, and while wikipedia’s articles are rarely bad, they’re also
often not particularly good. That is, they cover the material, but often in a
somewhat disorganized, hard-to-follow fashion. In the case of groupoids, I think Wikipedia’s
article is the best general explanation of groupoids that I’ve seen – better than most
textbooks, and better than any other web-source that I’ve found. So if you’re interested in
finding out more than I’m going to write about here, that’s a good starting point.

Continue reading →