Tag Archives: category theory

Categorical Computation Characterized By Closed Cartesian Categories

3 Replies

One of my favorite categorical structures is a thing called a closed cartesian category, or CCC for short. Since I’m a computer scientist/software engineer, it’s a natural: CCCs are, basically, the categorical structure of lambda calculus – and thus, effectively, a categorical model of computation. However, before we can talk about the CCCs, we need – what else? – more definitions.

Cartesian Categories

A cartesian category C (note not cartesian closed category) is a category:

  1. With a terminal object t, and
  2. forall a, b in Obj(C), the objects and arrows of the categorical product a times b in C.

So, a cartesian category is a category closed with respect to product. Many of the common categories are cartesian: the category of sets, and the category of enumerable sets, And of course, the meaning of the categorical product in set? Cartesian product of sets.

Categorical Exponentials

To get from cartesian categories to cartesian closed categories, we also need to define categorical exponentials. Like categorical product, the value of a categorical exponential is not required to included in a category. The exponential is a complicated definition, and it’s a bit hard to really get your head around, but it’s well worth the effort. If categorical products are the categorical generalization of set products, then the categorical exponential is the categorical version of a function space. It gives us the ability to talk about structures that are the generalized version of “all functions from A to B”.

Given two objects x and y from a category C, their categorical exponential xy, if it exists in the category, is defined by a set of values:

  • An object x^y,
  • An arrow mbox{eval}_{y,x}: x^y times y rightarrow x, called an evaluation map.
  • forall z in Obj(C), an operation Lambda_C: (z times y rightarrow x) rightarrow (z rightarrow x^y). (That is, an operation mapping from arrows to arrows.)

These values must have the following properties:

  1. forall f : z times y rightarrow x, g : z rightarrow x^y:
    • mbox{val}_{y,x} circ (Lambda_C(f)times 1_y)
    • forall f : z times y rightarrow x, g : z rightarrow x^y: Lambda_C(mbox{eval}_{y,x} circ (z times 1_y) = z

To make that a bit easier to understand, let’s turn it into a diagram.

exponent.jpg

As I alluded to earlier, you can also think of it as a generalization of a function space.x^y is the set of all functions from y to x. The evaluation map is simple description in categorical terms of an operation that applies a function from a to b (an arrow) to a value from a, resulting in an a value from b.

So what does the categorical exponential mean? I think it’s easiest to explain in terms of sets and functions first, and then just step it back to the more general case of objects and arrows.

If X and Y are sets, then X^Y is the set of functions from Y to X.

Now, look at the diagram:

  1. The top part says, basically, that g is a function from Z to to X^Y: so g takes a member of Z, and uses it to select a function from Y to X.
  2. The vertical arrow says:
    1. given the pair (z,y), f(z,y) maps (z,y) to a value in X.
    2. given a pair (z,y), we’re going through a function. It’s almost like currying:
      1. The vertical arrow going down is basically taking g(z,y), and currying it to g(z)(y).
      2. Per the top part of the diagram, g(z) selects a function from y to x. (That is, a member of X^Y.)
      3. So, at the end of the vertical arrow, we have a pair (g(z), y).
    3. The “eval” arrow maps from the pair of a function and a value to the result of applying the function to the value.

    Cartesian Closed Categories

    Now – the abstraction step is actually kind of easy: all we’re doing is saying that there is a structure of mappings from object to object here. This particular structure has the essential properties of what it means to apply a function to a value. The internal values and precise meanings of the arrows connecting the values can end up being different things, but no matter what, it will come down to something very much like function application.

    With exponentials and products, we can finally say what the cartesian closed categories (CCCs). A Cartesian closed category is a category that is closed with respect to both products and exponentials.

    Why do we care? Well, the CCCs are in a pretty deep sense equivalent to the simply typed lambda calculus. That means that the CCCs are deeply tied to the fundamental nature of computation. The structure of the CCCs – with its closure WRT product and exponential – is an expression of the basic capability of an effective computing system. So next, we’ll take a look at a couple of examples of what we can do with the CCCs as a categorical model of computation.

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.

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 →