In my last topology post, I started talking about the fundamental group of a topological space. What makes the fundamental group interesting is that it tells you interesting things about the structure
of the space in terms of paths that circle around and end where they started. For example, if you’re looking at a basic torus, you can go in loops staying in a euclidean-looking region; you can loop around the donut hole, or you can loop around the donut-body.
Of course, in the comments, an astute reader (John Armstrong) leapt ahead of me, and mentioned the fundamental group*oid* of a topological space, and its connection with category theory. That’s
supposed to be the topic of this post.
To start, what’s a groupoid? Basically, take the basic concept of a group, and expand it to cases
where the group operation *isn’t* total. To be formal, a groupoid consists of:
1. A set of values, *G*.
2. A *partial* operation × : *G* × *G* → *G*, such that:
* for all x, y, z ∈ *G*, if (x×y)×z is defined, and x×(y×z) is defined, then they’re equal.
3. A *total* inverse operation ()-1 : *G* → *G*, such that:
* for all *x*, *y* ∈ *G*, if *x*×*y* is defined, then
*x*-1×*x*×*y* = *y*.
* for all *x*, *y* ∈ *G*, if *x*×*y* is defined, then *x*×*y*×*y*-1 = *x*.
* for all x ∈ *G*, x×x-1 and x-1×x are defined.
The fundamental groupoid of a topological space is similar in concept to the fundamental group, but instead of being based on the set of *loops* from a point to itself, it’s based on the set of *all paths*. The groupoid operation is the same as the group operation: path concatenation. So given two paths, *x* and *y*, the *x×y* is defined if the end-point of *x* is the start-point of *y*. And for a path *x* from a point *a* to a point *b*, *x-1* is the reverse path from *b* to *a*. So the fundamental groupoid is formed
from the equivalence classes of paths in the topological space formed by homotopies.
Where is gets kind of neat is when you look at a groupoid in category theory. In category theoretic terms, a groupoid is just a category where every morphism is *iso*. (As a reminder, *that* means that every morphism is reversable.) Composition of the morphism is the group operation. Much simpler definition, eh?
Now, let’s play some tricks. Suppose we have a topological space, **T**, and its fundamental groupoid, *G*. We’ll think about *G* in its categorical form, because that’s easier to talk about. So the category form of the groupoid has the same objects as **T**, with morphisms between objects *x* and *y*if there is a *continuous* path from *x* to *y*.
We can say that the groupoid *G* is connected if for all *x,y ∈ G*, there is a morphism *m : x → y*. If the groupoid is connected, then the topological space is *path*-connected. (And that’s a much easier definition of path-connected to get than the non-categorical one, which is based on another of those “isomorphism from [0,1]” beasts!)
So, suppose we have a connected groupoid, *O*. If we keep looking at it in terms of categories, we see something interesting about groupoids pretty easily. We can describe
a connected groupoid using a group. The way we do that is: take the set of
objects of *O*, and for all pairs of points x and y ∈ *O*, the set of *morphisms* from x to y is an object of the group. The group operation is just composition of the morphisms. So for any connected groupoid, there’s a really simple representation of the groupoid as a category-based group.
What if the groupoid *O* is *not* connected? Then it can still be represented in terms of groups, but you need more than one. You can describe the groupoid by a set of pairs (Gi,Oi), where Oi is a subset of the objects of *O*, and
Gi is the category-based group describing Oi. The strange thing
about this is that there *isn’t* a canonical group-based description of a non-connected groupoid for a topological space. There can be many different ways of describing a groupoid in
terms of groups over subsets of its elements, and there is *no* way to choose one
of those as being canonical – they’re different, but equivalent.
If you think about it, that’s pretty strange. Most of the time in math, we can find ways of
creating canonical definitions: for some mathematical construct *X*, we can generally find
some way of saying “This is what X is, and any other way of defining X can be reduced to another way of restating this.” And yet, for something deeply fundamental about the shapes of spaces, *we can’t do that*. That’s strange, and fascinating.
An interesting side note about these two definitions of a groupoid is that they highlight one of the culture differences between mathematicians and computer scientists. Computer scientists seem universally comfortable with “partial functions”, while to a mathematician to call them “functions” at all is an abomination before.. well before something.
I’ll admit candidly that I always hated the idea of a “groupoid” when I first saw it. These partial operations seemed so awkward and stunted that it couldn’t possibly be more than a curiosity. Then I saw the categorical version and it suddenly made sense.
It works the other way too: do categories give you the shivers? Just think of them as being sort of like monoids, but the composition is only partially defined.
It’s really interesting, but… could you walk more slowly? I’m too dusted, or maybe it’s the work distracting me. Or maybe I’m dull. I seem to get the idea, but fail to grasp details. Is your entry supposed to be read and understood by the first read? :$
My confussion starts with: “Where is gets kind of neat is when you look at a groupoid in category theory. In category theoretic terms, a groupoid is just a category where every morphism is iso. (As a reminder, that means that every morphism is reversable.) Composition of the morphism is the group operation. Much simpler definition, eh?”
A couple random remarks:
*The difficulty Mark alludes to in the last paragraph is a fundamental one, leading to some pretty category theory. The technical reason for it is that groups form a “pointed category” while topological spaces do not. What this means, in essence, is that the category of groups has a distinguished zero object (the trivial group) which maps into every nontrivial group in exactly one way. The category Top of topological spaces also has a zero object of sorts (a single point) but there are many (usually uncoutably many) ways that we can map a point into our topological space. To fix this problem, we sometimes look at the category pTop of “pointed” topological spaces, that is, topological spaces with a single point distinguished as the “base point.” In the other direction, the non-pointed version of a group is … a groupoid! I could ramble on about this for a good long while, but that’s probably enough.
*There’s an easier way to get the fundamental group of a path-connected space out of the fundamental groupoid: simply forget about everything but one object, and the morphisms from that object to itself. The resulting thing is a category with a single object in which all morphisms are iso… namely, a group! (For those not totally fluent in category-speak, recall that the objects of the group are the morphisms from the object to itself, and the group identity is the identity morphism.)
Hm… The definition of groupoid that we use in geometry is not that (or equivalent to that). In fact, the first definition you gave is *not* equivalent to the second (a category where every morphism is iso).
More specifically, you did not define a groupoid as a total set G (“set of arrows”) plus a base set X (“set of vertices”), together with two projections (“head” and “tail”) from G to X (which, among other things, tells us when we can compose two elements of G) plus axioms. You skipped the base set X entirely. As a consequence, G in general is not the set of morphisms of a category because there is no set of objects.
Am I missing something? Or do you just use a different concept of category in CS?
PS: Just for the purists, if you require G to be a set, you should talk about small categories. Which does not matter much.
There are two very different meanings of the word “groupoid” unfortunately.
A groupoid G is a set together with a binary operation G x G –> G. The groupoid (or “magma”) is closed under the operation.
There is also a separate, category-theoretic definition of “groupoid.”
See:
Weisstein, Eric W. “Groupoid.” From MathWorld–A Wolfram Web Resource.
Follow links to the enumerations in the Online Encyclopedia of Integer Sequences (OEIS).
Or start at the OEIS and insert “groupoid” into the search engine. There are several sequences, most with additional examples and references. I seem to recall having contributed at least one of these.
Too few words for too many concepts. Related to the “Law of Small Numbers.”