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.
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.
To describe that symmetry, we need a less restrictive version of something like a group. What we end up with is called a groupoid. Groupoids are easiest to describe in terms of category theory. Let’s take a look, and see the difference between a category theoretic definition, and the conventional algebraic definition.
In algebra, we say: A groupoid is a collection of objects G, along with an
operation “×” and a function -1, where:
- × must be defined for some pairs of members of G.
- For all a, b, and c in G, if (a×b)×c is defined, then it must be equal to
a×(b×c). (This is a partial version of the associativity property of
groups.) - For all a in G, a-1 is defined. (The inverse must be total.)
- For all a and b in G, a×b is defined, then a×b×b-1 = a,
and a-1×a×b = b, and only the inverses can have this property. (This is the partial equivalent of the group identity; in a groupoid, you don’t need an identity value which can be combined with every other value in the groupoid; you just have the requirement that there be unique inverses for each value in the groupoid.) - For all a in G, a×a-1 is always defined.
Now, in terms of category theory: a groupoid is a category in which every arrow is iso.
See what I mean? The category theory definitions of the necessary properties of arrows to be a category actually includes most of what makes a groupoid. A groupoid is just a category
where every arrow is reversible. If you can understand the basic concept of a category, then
you’ve pretty much already got groupoids. And it’s very easy to get from groupoids to groups.
Now, what does the category theoretic understanding of groupoids really tell us? What’s really interesting (at least to me) is that if you take a single object O in a groupoid, and collect all of the morphisms that run from O to O, that object and group of morphisms defines a group. So the groupoid can be understood as a collection of closely related groups. For example, in the fifteen puzzle, starting with a given configuration, every sequence of moves that starts and ends in that configuration are a group of moves. The 15-puzzle groupoid is what you get when you entangle all of those groups together.
Not only does each object in a groupoid give a group, but any two objects in a groupoid that have an arrow between them give isomorphic groups. How? Conjugate by the isomorphism between them!
I forget if you covered equivalence of categories, but it’s straightforward now to show that a “connected” groupoid (where all the objects have at least one morphism between them) is equivalent to the group specified by any one of its objects (considered as a category with one object).
Why does this equivalence matter? Because some other puzzles do have a group of moves that can all be composed. But still, this group is really just equivalent to the groupoid of moves you get when you consider states of the puzzle separately, and thus tease apart information that you’d identified by just looking at the group of moves.
Now, in terms of category theory: a groupoid is a category in which every arrow is iso. See what I mean? The category theory definitions of the necessary properties of arrows to be a category actually includes most of what makes a groupoid.
Hm, that is definitely interesting but it seems to me to dovetail nicely with the criticism Blaise Pascal (probably not his real name) issued against Category Theory in your last thread:
And it seems to run up against my main issue with category theory, which is that every time you see an example given of what category theory could be used for, the only clear application seems to be “you see, you can describe this thing using category theory!”. Okay, that’s neat if you like category theory, but if what we’re interested in is groupoids then what do we gain by characterizing the structure by the category theory structures it corresponds to rather than by enumerating the axioms it follows?
Um, I thought group theory defined continuous symmetries, whose that most often have immediate interest. (Conserved quantities.) No doubt you can build more elaborate symmetries.
the only clear application seems to be “you see, you can describe this thing using category theory!”
I’m a newbie to category theory myself but I think I’m beginning to see the edges of what category theory brings at the application level – analogies.
Once you’ve found a way to describe one thing in category theory then you’ve got a formal way to create an analogy between that thing and other apparently unrelated things with the same category theoretical description. Using those analogies can help help you reuse previous proofs or ask interesting questions by pushing the analogies further.
If you are a programming language geek, there was an interesting discussion about the application of category theory to programming recently on Lambda the Ultimate.
I think Blaise’s objection isn’t as widely applicable as he suggests. Yes, learning what a group is that way wouldn’t really help, but there are plenty of other cases where the categorical description really is quite helpful.
For example, I can never keep groupoid and semi-group straight. When I ask one of my friends what one is, he gives me the categorical definition, and I immediately understand it.
For another example, my number theorist roommate was telling me what the p-adics are. After a bit, I was able to realize that he was describing a limit, and I knew what they were.
I hadn’t thought of the 15-puzzle as a groupoid before, so thanks for pointing that out. But I still side with the claim that “group theory defines symmetry,” if I understand what that means.
The 15-puzzle groupoid has automorphisms. For example, you pointed out that the set of moves possible when the empty is in the upper-right corner (call this “set A”) is equivalent to the set of moves possible when the empty is in the upper-left (“set B”). In other words, there is an automorphism of the groupoid which sends set A to set B. “Symmetry” means pretty much the same thing as “automorphism”.
Now, the set of automorphisms can be thought naturally as a group under composition. Automorphisms come in groups. Symmetries come in groups. I’m guessing that’s what is meant by “group theory defines symmetry”.
Of course no one claims that groups are the only structures which have symmetries! Groupoids, Boolean Algebras, and geometric figures have symmetries. But the symmetries of any of these things come in groups.
Here’s some enumeration [source: Online Encyclopedia of Integer Sequences].
A001329 Number of nonisomorphic groupoids with n elements.
n a(n)
0 1
1 1
2 10
3 3330
4 178981952
5 2483527537094825
6 14325590003318891522275680
7 50976900301814584087291487087214170039
COMMENT
The number of isomorphism classes of closed binary operations on a set of order n.
REFERENCES
M. A. Harrison, The number of isomorphism types of finite algebras, Proc. Amer. Math. Soc., 17 (1966), 731-737.
T. Tamura, Some contributions of computation to semigroups and groupoids, pp. 229-261 of J. Leech, editor, Computational Problems in Abstract Algebra. Pergamon, Oxford, 1970.
See also:
A079171 Number of isomorphism classes of closed binary operations (groupoids) on a set of order n, listed by class size.
A001425 Number of commutative groupoids with n elements.
A030271 Number of nonisomorphic groupoids with 1 idempotent and no symmetry.
A079187 Number of isomorphism classes of non-anti-commutative closed binary operations (groupoids) on a set of order n.
A079190 Number of isomorphism classes of anti-commutative closed binary operations (groupoids) on a set of order n.
A090588 Number of labeled idempotent groupoids
A030245 Number of nonisomorphic groupoids with no symmetry.
A030247 Number of nonisomorphic idempotent groupoids.
There are 10 pages of enumeration and other sequences about groupoids on Online Encyclopedia of Integer Sequences (OEIS). You can find them with the OEIS search engine. Many have citations to the literature, or explanations, or formulas.
Coin:
My own take on Category theory is that it’s a great explanatory tool. You can make similar criticisms of set theory: what does set theory really give you that you wouldn’t get if you didn’t use sets at all?
The answer is a common explanatory framework. Category theory is difficult at first, but when you pick up the basics, suddenly a lot of things can be explained simply and clearly in terms of category theory.
If you understand categories, then it takes one simple definition to get groupoids. If you’ve got groupoids, it’s one simple definition to get groups, and understand the connection between the groupoids and the groups. It’s harder to describe that without the language of category theory.
You find similar stuff in all sorts of places. There are a ton of topological properties that actually apply to more than just topological spaces – but expressing those properties in the language of set theory and topology is difficult. Category theory makes algebraic topology a whole lot clearer and easier to apply to things that aren’t quite topological spaces.
A friend of mine, who’s a programming language theorist, once explained category theory to me as “a field of math which produces no new results of its own, but makes older results easier to understand”. It’s not entirely true, but it’s close.
I am trying to categorize category theory. What is it? The comments above mention “a common language”, “explanatory tool”, “a field of math”. I know category theory can be done (formalized) inside ZF set theory with some additional axioms, or in HOL . Some comments suggest though that category theory can serve as a foundation of mathematics, alternative to set theory. If this is the case what would be the axioms of category theory?
Um, I thought group theory defined continuous symmetries, whose that most often have immediate interest. (Conserved quantities.)
Groups can be continuous, but they don’t have to be. You can also have discrete symmetries which define discrete groups. Consider mirror symmetry, where you’re just flipping left and right; there’s the identity operation, where you don’t flip anything, and the flipping operation (which is its own inverse). Those two operations satisfy the group axioms.
The continuous symmetries are particularly interesting to physicists because they’re the kind of symmetries that give you conserved quantities, not because they’re the only symmetries that define groups.
James: you’re exactly right. Category theory is all about analogies. As I say here:
In the very old days, I think that I could have convinced Euclid (if I spoke Greek) and much later, Newton, that in Euclidean space:
“An analogy is a parallelogram in semantic space. To say A is to B as C is to D, where A, B, C, D are statements about the physical universe, social universe, or an abstraction, can be translated. The line segment jointing A to B is parallel to and the same length as the line segment joining C to D.”
This generalizes to vector spaces, and further to metric spaces. One actually sees this done, sort of, in Web 2.0 pages that analyze web pages and make 2-D or 3-D maps of the keywords or sub-domains based on a metric of distance.
In that Eclidean sense of analogies, what is an analogy between analogies? Is it a 3-D parallelopiped? How does that generalize?
==========
As I posted once before (and today would correct “categorize” to “categorify”) on:
November 2, 2006
A Categorical Manifesto
Posted by John Baez
n-Category Cafe
Ulam on Banach; Re: A Categorical Manifesto
Stanisław Marcin Ulam, another mathematician of the Lwów School of Mathematics, in his autobiography, attributes this to Banach:
“Good mathematicians see analogies. Great
mathematicians see analogies between analogies.”
Is this a prescient hint of the campaign to
categorize, re-categorize, and/or n-categorize mathematical and Physics foundations?
Anyone think that the quote can be made axiomatical?
That “Very Great mathematicians see analogies between analogies between analogies between analogies.”
And what the omega-closure of this? Or should it be embedded in a universe including strongly unreachable analogies?
Just wondering, as an admirer of Ulam who was to have coauthored with him, but suffered when he died before we could agree on the abstract.
====
Re: Ulam on Banach; Re: A Categorical Manifesto
“Good mathematicians see analogies. Great mathematicians see analogies between analogies.”
Is this a prescient hint of the campaign to categorize, re-categorize, and/or n-categorize mathematical and Physics foundations?
There’s no doubt in my mind that that’s so. My advisor was fond of quoting that line, usually right after noting that “a functor is an analogy”.
Posted by: John Armstrong on November 11, 2006 4:35 AM
=====
Re: Ulam on Banach; Re: A Categorical Manifesto
Thank you for that supportive example. Could it be that Ulam or Banach was influenced by Hilbert’s syzygy theorem? This theorem, as summarized on Wikipedia,
which also gives a more modern statement, but not so modern as category Theory: “is a result of commutative algebra, first proved by David Hilbert (1890) in connection with the syzygy (relation) problem of invariant theory. Roughly speaking, starting with
relations between polynomial invariants, then relations between the relations, and so on, it explains how far one has to go to reach a clarified situation. It is now considered to be an early result of homological algebra, and through the depth concept, to be a measure of the non-singularity of affine space.”
Posted by: Jonathan Vos Post on November 11, 2006 5:57
=========
[A friend of mine, who’s a programming language theorist, once explained category theory to me as “a field of math which produces no new results of its own, but makes older results easier to understand”.]
Do you know of any examples where learners have *first* learned “older results” that others learned with set theory? Did they learn those results faster or in less space than those who learned those results from set theory? Or does category theory have a more compact notation? An affirmative for one of these would seem required to rule to know that people learn results more easier through category, since older results come out easier to understand *even if* one reviews them a second time through old methods.
On another note, how much do the results matter? Does the process, axioms, operators, etc. matter more?
Actually, to address the concerns of some that category theory seems like only an end to itself, it turns out that notions such as groupoids (and other category-theoretic objects that seem totally abstract) are vital inputs to some of the most interesting pure mathematics today.
In the abstract, category theory is a necessary tool for the fields of representation theory and algebraic geometry (and many more areas too), both of which are huge areas of research. Roughly, the reason category theory is so important in these areas is that the language of categories allows us to compare seemingly disparate collections of objects in different settings. Many of the biggest results in representation theory at the moment are heavily category-theoretic in flavor as well.
As for groupoids, they are actually one of the main inputs in creating mathematical objects called stacks, and it isn’t overstating the issue to say that the introduction of stacks some 40 years ago has revolutionized large areas of algebraic geometry. (Very) roughly speaking, stacks are geometric objects built from collections of groupoids; the allow constructions of quotient spaces that “remember” the quotient group. As just one example of the usefulness of stacks, they are a main component of the geometric Langlands program, which is a huge area of current research. In general, stacks have found great use in creating so-called “moduli spaces:” these are spaces that parametrize various objects. There are moduli stacks of vector bundles, moduli stacks of curves, etc.
Anyhow, the point is that, far from being some odd, esoteric branch of mathematics, category theory is actually a necessary component of what (in my admittedly biased opinion) is some of the most exciting– and far from esoteric!– mathematical research going on today.
For those who are interested in stacks, there is an introductory book that can be downloaded free here:
http://www.math.unizh.ch/index.php?pr_vo_det&key1=1287&key2=580&no_cache=1
It’s accessible to a reader with some mathematical background.
Also, if you are interested in learning about the langlands program, there is a good survey article here:
http://arxiv.org/abs/hep-th/0512172
It requires some mathematical knowledge to read, but even if you don’t know a whole lot about math you can skim it to get the gist.
FWIW, catching up on old threads:
@ pillsy:
Yes – I was sloppy. Though it is still the case that the continuous subset defines the immediate interest, as you also note.