Archive for the 'Category Theory' category

Category Intuition by Example

Oct 09 2011 Published by under Category Theory

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.

11 responses so far

Leading up to Topoi: Getting Back to Categories

Sep 30 2011 Published by under Category Theory

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.

26 responses so far

Topoi Prerequisites: an Intro to Pre-Sheafs

Jul 03 2011 Published by under Category Theory, topology

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 »

4 responses so far

Meta out the wazoo: Monads and Monoids

Mar 11 2008 Published by under Abstract Algebra, Category Theory, Haskell, Programming

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 »

No responses yet

Full Circle: the Categorical Monoid

Feb 28 2008 Published by under Abstract Algebra, Category Theory

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 »

No responses yet

This is getting fun! On to Monoidal Categories.

Feb 18 2008 Published by under Abstract Algebra, Category Theory

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 »

No responses yet

Clarifying Groupoids and Groups

Feb 07 2008 Published by under Category Theory, Group Theory

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 »

No responses yet

More Groupoids and Groups

Feb 05 2008 Published by under Category Theory, Group Theory

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 »

No responses yet

Capturing More Symmetry using Categories: Groupoids

Jan 24 2008 Published by under Category Theory, Group Theory

Today's entry is short, but sweet. I wanted to write something longer, but I'm very busy at work, so this is what you get. I think it's worth posting despite its brevity.

When we look at groups, one of the problems that we can notice is that there are things
that seem to be symmetric, but which don't work as groups. What that means is that despite the
claim that group theory defines symmetry, that's not really entirely true. My favorite example of this is the fifteen puzzle.

fifteen.png

The fifteen puzzle is a four-by-four grid filled with 15 tiles, numbered from 1 to 15, and one empty space. You can make a move in the puzzle by sliding a tile adjacent to the empty
space into the empty. In the puzzle, you scramble up the tiles, and then try to move them back so that they're in numerical order. The puzzle, in its initial configuration, is shown to the right.

If you look at the 15 puzzle in terms of configurations - that is, assignments of the pieces to different positions in the grid - so that each member of the group describes a single tile-move in a configuration, you can see some very clear symmetries. For example, the moves that are possible when the empty is in any corner are equivalent to the moves that are possible when the empty is in any other corner. The possible moves when the space is in any given position are the same except for the labeling of the tiles around them. There's definitely a kind of symmetry there. There are also loops - sequences of moves which end in exactly the same state as the one in which they began. Those are clearly symmetries.

But it's not a group. In a group, the group operation most be total - given any pair of values x and y in the group, it must be possible to combine x and y via x+y. But with the 15 puzzle, there moves that can't be combined with other moves. If x = "move the '3' tile from square 2 to square 6", and y = "move the '7' tile from square 10 to square 11", then there's no meaningful value for "x+y"; the two moves can't be combined.

Continue Reading »

No responses yet

Before Groups from Categories: a Category Refresher

Jan 20 2008 Published by under Category Theory, Group Theory

So far, I've spent some time talking about groups and what they mean. I've also given a
brief look at the structures that can be built by adding properties and operations to groups -
specifically rings and fields.

Now, I'm going to start over, looking at things using category theory. Today, I'll start
with a very quick refresher on category theory, and then I'll give you a category theoretic
presentation of group theory. I did a whole series of articles about category theory right after I moved GM/BM to ScienceBlogs; if you want to read more about category theory than this brief introduction, you can look at the category theory archives.

Like set theory, category theory is another one of those attempts to form a fundamental
abstraction with which you can build essentially any mathematical abstraction. But where sets
treat the idea of grouping things together as the fundamental abstraction, category
theory makes the idea of mappings between things as the fundamental abstraction.

Continue Reading »

No responses yet

« Newer posts Older posts »