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.
As I’ve explained before, the basic idea of a group is a mathematical structure with an
operation that defines a kind of immunity to transformation. Every transformation through the
group operator preserves some kind of structure. In a groupoid, you don’t have such a strong
symmetry. In a groupoid, you have an operation that includes a symmetric
transformation, but not all applications of it are symmetric: the groupoid operator preserves
structure under some conditions: that is, there are sequences of groupoid
operations that result in symmetric, structure-preserving transformation, and it’s easy to
define just what those sequences of transformations are.
In categorical terms, that idea of the partially symmetric operation of a
groupoid is reflected by the fact that there are many arrows that go from an object (a
structure) to a different object – transforming it into something different –
something distinguishable from the original structure. But there are sequences of operations
that end back at the original object, and those sequences of operations describe symmetric
transformations.
This leads to the intuition behind the simplest relation between groupoids and groups. If
you have a groupoid with a single object in it, that that groupoid is a group. In a
single-object groupoid, every application of the operation must end back at the
object where it began – so every transformation in a single-object groupoid must be symmetric
– so the single-object groupoid is a group.
That much already shows us some of why the categorical formulation is nice: we’ve gone from something where the relationships and structures are symbolic, to something where we can see what’s going on using a simple diagram: it’s easier to see “all paths from G end at G”
when you draw the structures, than it is to see the corresponding statement in terms of pure algebra.
But there’s more to it. Some of the more subtle things are captured very nicely. For
example, there’s a notion of equivalence in groupoids that is different from isomorphism, which tells us more about the relationship between groupoids and groups. It comes from the categorical idea of a natural transformation. I wrote about
natural transformations here. For a quick reminder, if you start with
a category, you can define structure-preserving transformations between objects using
morphisms; you can define structure-preserving transformations between morphisms using functors; and you can define structure-preserving transformations between functors using
natural transformations.
Let’s look at that notion of loose equivalence. Suppose we have a groupoid, O, which is
connected – that is, where in the category for G, given any two objects a and b in O, there
is an arrow from a to b. We can form a group G out of the groupoid, by collapsing
the connected groupoid to a single object. Loosely speaking, you can pick an arbitrary object from the groupoid as a representative, and collapse the arrows – each set of arrows
from the representative to a particular other object becomes an arrow in the collapsed groupoid; those arrows become the objects of the group, and arrow composition is the group operator. The end result is a group formed from the collapsed arrows of any connected groupoid.
What if the groupoid isn’t connected? You take the connected components of the groupoid, and each of them can be collapsed into a group – so you can collapse any groupoid into a collection of disjoint groups.
Here’s where it gets interesting. The collapse of a groupoid isn’t unique. It’s determined by the selection of the representative objects. The collapsed groupoids are all
equivalent. In fact, you can define an isomorphism between them – they’re all ultimately the
same structure; so you can define the isomorphic mappings between objects in the different
collapsed versions.
But suppose you don’t define the mappings between objects. Suppose all you look at are
the arrows that form the groups. So you’ve discarded the objects from the original groupoid,
and all you have left are single objects corresponding to the different connected components, each of which is a group. What you’ve done, then, is to create a mapping from a groupoid to a collection of groups. It is not an isomorphism – but it is a mapping from the groupoid to a collection of groups that is, in some sense, equivalent to the original groupoid. (Note that I said “collection”, not set. In fact, it’s a multiset; multiple components can collapse down to the same group, but you need to keep an instance of that group for each of the components.) The structure of that collection of groups is determined by the original groupoid.
But it’s not an isomorphism. That transformation has discarded some information about the original structure. There are multiple groupoids that can all be collapsed into the same
collection of groups. Because you didn’t keep the mappings that allow you to identify the arrows to the original groupoid objects, you can’t go back. It’s a one-way transformation.
Category theory allows you to define that loss of information in a very convenient way. Any high-level transformation like that – where you’re basically transforming a category into a different category (in this case, from a groupoid category to a category containing a collection of groups) can be described by categorical transformations. The structure-preserving relations between arrows in the original category – the functors of the original category – in a categorical sense define the structural information contained in the category. When you map from category to category, there
is a mapping between the functors that define the informational relationships between
the two categories. If you can map from one category C to another category D without losing any structural information, that is reflected in category theory by the existence of
a natural transformation from C to D. In the case of the groupoid-to-groups collapse, there is no natural transformation. The non-existence of a natural transformation
means that there is going to be a significant loss of structural information.
What does that mean?
It means that groupoids are richer structures that groups. There is interesting
information about symmetry which we can capture in terms of the algebraic structure of
a groupoid which we cannot capture in terms of the groups that make up the components of a groupoid. Without understanding the groupoids, we are missing something about
the meaning of symmetry!
This is pretty much on-target. Every groupoid can be broken into connected components (like a graph), and each connected component is equivalent (in the groupoid sense) to a group (considered as a one-object groupoid). In fact, this group is the group of automorphisms of any object in that component. The question I’m leaving open here is why all the objects in a connected component have isomorphic groups of automorphisms.
It’s instructive to look at the difference between the 15-puzzle and the Rubik’s cube here. The 15-puzzle naturally makes us think of a groupoid because we can see an “object” in our choice of vacant space, while the Rubik’s cube is “shaped the same” after each twist. There is an equivalent group for the 15-puzzle, but the “natural” generators (individual tile-slides) are not in that group since they go from one object to another. On the other hand, the “natural” generators of Rubik’s group (1/4 face-twists) are in the group.
Also, each of these puzzles could be expanded to a big groupoid with one object for each state, and one morphism for each maneuver (either a basic move or a sequence of basic moves), like a giant graph of the game. Then the fact that we have a groupoid means that everything we do we can undo. Of course, these huge groupoids are also equivalent to the group(oid)s we naturally think of.
It still seems to me that groups are sufficient to capture the structure of the symmetries of any object (but, of course, not all of the structure of the object). I was confused about this in the last post, and I hope someone can set me straight here.
I understand that you need a groupoid to capture the structure of the 15-puzzle. Is the claim that every “move” in the 15-puzzle is a “symmetry” of the 15-puzzle? That seems like a strange use of the word symmetry, but maybe that’s the disconnect. I would have thought that a symmetry of the 15-puzzle is an automorphism of the 15-puzzle (i.e. an automorphism of the groupoid which naturally describes the 15-puzzle, where each groupoid element corresponds to a 15-puzzle move). And the automorphisms of a structure form a group.
Help?
ej:
I thought that the categorical structure made it clear; I guess I didn’t do a good enough job explaining it.
In the groupoid, we’re not saying that every application of the group operator is symmetric. But what we are saying is that every symmetry of the groupoid is formed from applications of the groupoid operato
If you take something like a 15 puzzle, given any initial configuration, you can describe a group around that configuration which defines a symmetry of the puzzle. Further, for any two configurations with the empty square in the same position, you can define an isomorphism between the groups for those two configurations.
So there are 16 basic symmetries of the puzzle, each of which can apply to a huge number of configurations.
That set of 16 groups are the result of collapsing the groupoid for the 15 puzzle.
The thing is, there’s more to the actual symmetries of the puzzle than you can see from those groups. The fact that the groupoid-to-groups transformation loses information means that we’ve *lost* information about the symmetric structure of the puzzle in that transformation.
So every symmetry of the 15 puzzle *is formed by* moves. But not all moves are symmetric.
The reason that we care about the groupoid is that the symmetries are both formed by, and related by applications of the groupoid operator. Given a puzzle in one configuration, there’s a bunch of symmetric sequences of moves. Given that same puzzle, there’s a different bunch of symmetric sequences of moves. And for many pairs of configurations, there’s a non-symmetric series of moves that transforms the puzzle from one of those configurations to another. So the configurations – the basis of the symmetries – are related by the same elements that define their symmetries.
I have much the same problems with this discussion. As I understand it, the physically important symmetries, which I believe are based on diffeomorphisms, are described by groups. It sounds to me the basic claim is that the remainder, describing discrete symmetries, is described by groupoids?
……00……02……04……06……08
……09……11……13……15……17
……18……20……22……24……26
……27……29……31……33……35
……36……38……40……42……44
……45……47……49……51……53
……54……56……58……60……62
……63……65……67……69……71
……72……74……76……78……80
……81……83……85……87……89
……90……92……94……96……98
+___________________________
A.) 495….517….539….561….583
……01……03……05……07……09
……10……12……14……16……18
……19……21……23……25……27
……28……30……32……34……36
……37……39……41……43……45
……46……48……50……52……54
……55……57……59……61……63
……64……66……68……70……72
……73……75……77……79……81
……82……84……86……88……90
……91……93……95……97……99
+___________________________
B.) 506….528….550….572….594
Therefore;
….A…495….517….539….561….583
+…….594….572….550….528….506…B
__________________________________
=…..1089….1089…1089…1089…1089 equals 5445
Or, (01+10) = 11 x 495
String Theory’s principles
Lier.
I think you mean liar, unless you’re punning on something that I can’t find with an elementary googling.
However, that is indeed the most egregrious lie told by ray so far in his short history of spanning this blog with basic numerology. Zero (a previous numerologist who spammed a few threads, for those just tuning in) was at least more interesting in his craziness – ray is just obsessed with the properties of 9 and 11 in the base-10 numbering system.
Oops. Sure Xanthir, that is what a bear or two buys you.
I think you mean spamming…
How many bears did you have?
Only tree bears, I swear!
You recondite elitist want to be’s, are just pissed off because of the realization that your favored bourgeoisie mystique will have to give evolutionary leeway and thereby credence to the “directional flow” and the posteriori ‘symmetry’ impetus represented in “Reduction” mathematics (antithetical duality).
For most of you this represents a level of logic and perceptive visual complexity that will leave your scholarship at the doorstep of tomorrows reality. Liken by the antiquated mythic system of Christian beliefs, and as it should be, who’s time has come and went in the creation of tomorrows basis.
“As a child I played with child like things” etc…etc…
If you can’t see the impetus of String Theories predominate numbers 01 and it’s inverse 10, 11, and/or 5 have in my examples. Then your interest would be best be served in perfecting your tenure, as tomorrow has just passed you by.
Ridicule and derision, the tools of the forgotten.
Ray:
Give it a rest.
To put it mildly, you’re a clueless idiot who’s doing nothing but demonstrating his awn pathetic ignorance and arrogance.
You don’t understand string theory. You don’t even understand simple arithmetic as far as I can tell. All of your supposed deep truths are nothing but numerical games that reveal nothing.
See, number games like what you’re playing at are properties of the number base. That’s all. It just happens that we commonly use base 10, and so numbers like 5, 9, and 11 appear to have amazing properties. Similarly, if we used base 12, the “amazing properties” would show up for 6, 11, and 13. If we used base 3, 2 and 4 would have amazing properties, but there’d be nothing with the supposed “properties” of 5.
It’s all just games with notation.
Like the old 0.99999….=1 thing. There’s nothing deep there. It’s just notation. Switch to base 12, and you’ll find a slightly different version of that, involving 1/11th and 0.BBBBBBB repeating (assuming you use “A” for the numeral 11).
It’s not deep. It’s not meaningful. It’s got nothing to do with deep truths, or with physics of any kind. It’s got nothing to do with deep symmetry. It’s got nothing to do with string theory. It’s just a dull notational artifact.
Thanks, Mark. Notational artifact or number pareidolia?
Anyway, it is the one of the most annoying displays of mental or social (ignorance) problems, and when it is compounded by science falsehoods…
10 being an arbitrary base due to rule-of-thumb with two human thumbs worth of fingers.
By the way, Professor Gregory Benford, whom I’ve known for very nearly 30 years, told me “rules of thumb are well and good, but remeber that other intelligent beings may have different numbers of thumbs.”
Which reminds me of the following…
The passion rule of thumb: Gregory Benford, professor of physics and astronomy, a long-time advisor to NASA, and Hugo- and Nebula-winning novelist, says “passion is inversely proportional to the amount of real information available.”
Coincidently, I can say more linking “rule of thumb” and Benford.
“If crew were already harvesting, then Killeen knew he had been running a bit too long. He deliberately did not use the time display in his suit, since the thing was ageold and its symbols were a confusing scramble of too much data, unreadable to his untutored mind. Instead he checked his inboard system. The timer stuttered out a useless flood of information and then told him he had been running nearly an hour. He did not know very precisely how long an hour was, but as a rule of thumb it was enough.”
[Tides of Light, by Gregory Benford, Chapter One, Copyright © 1989 by Abbenford Associates]
“Languages evolve, just as in biology, by descent and divergence. We can read Shakespeare but need notes to fathom some of his archaic words. Without substantial help, Beowulf is beyond us. As a rule of thumb, basic vocabularies change about twenty percent in a thousand years. Even if a language survives (as most don’t) for five thousand years, it will be vastly different.”
[‘Deep Time’, by Gregory Benford]
[‘Deep Time’ fascinating, thought provoking, disturbing
‘Deep Time’
by Gregory Benford
Avon, $20
Review by L.D. Meagher
March 25, 1999
Web posted at: 4:22 p.m. EST (2122 GMT)
http://www.cnn.com/books/reviews/9903/25/deep.time/
]
“A general rule of thumb is that you should measure metabolic rate under normal, low-stress conditions.”
[THE LOST CHAPTER FROM THE LONG TOMORROW
This chapter was left out of MRR’s recent book, The Long Tomorrow; How Advances in Evolutionary Biology Can Help Us Postpone Aging, Oxford University Press, 2005. Here it is for you to judge if this was the right decision.
http://www.benford-rose.com/wormisatwork.php
]
I submitted a comment, with several quotes from Professor Gregory Benford, putting poor Ray B. (not to be confused with Ray Bradbury) in context.
Then, while waiting for it to be evaluated and posted, I thought to add the following.
NOT to be confused with the F. Benford of “Benford’s Law: A phenomenological law also called the first digit law, first digit phenomenon, or leading digit phenomenon. Benford’s law states that in listings, tables of statistics, etc., the digit 1 tends to occur with probability ∼30%, much greater than the expected 11.1% (i.e., one digit out of 9). Benford’s law can be observed, for instance, by examining tables of logarithms and noting that the first pages are much more worn and smudged than later pages (Newcomb 1881). While Benford’s law unquestionably applies to many situations in the real world, a satisfactory explanation has been given only recently through the work of Hill (1996).”
Weisstein, Eric W. “Benford’s Law.” From MathWorld–A Wolfram Web Resource.
Benford, F. “The Law of Anomalous Numbers.” Proc. Amer. Phil. Soc. 78, 551-572, 1938.
Mark,
Now here is a demonstrated “clueless idiot”….”It’s all just games with notation”….Ah dah ya tink so….genius? And what might the double helix and DNA sequencing be ….genius?
And how does mathematics tautology direct the genius of “Mark Chu-Carroll (aka MarkCC) is a PhD Computer Scientist, who works for Google as a Software Engineer.” to design his own blog? The answer is with directional sterility, where the commenter’s have to imploy periods to attempt any vertical sequencing….ah that’s genius….but who’s.
“Like the old 0.99999….=1 thing. There’s nothing deep there.” Your right again genius…. there’s nothing of value here for any one who can’t differentiate between “whole” number and fractional number mathematics.
It’s my bet that you, like that ass kissing (apple polishing Torbjörn Larsson, OM ), can remember which of your professors planted your last original thought.
Just for your edification I’ll match IQ’s with you all day long, but that’s not got you your doctorate degree was it. It was how long you persisted at the academic game.
Ray:
(A) Go look at the URL. I didn’t set up this site. I don’t administrate it. I’ve got very little control over the what happens in the backend. Believe me, if I did, we’d have a better way for me to do mathematical notation that the crufty HTML entities that I struggle with.
(B) Tone down the personal attacks, or you’re out of here. I’ll tolerate all sorts of pig-ignorant bullshit, but I won’t tolerate pointless personal attacks. If you really think your “ideas” have any merit, then feel free to defend them – using actual arguments. If the only way you respond to criticism is by making personal attacks against your critics, that’s a pretty solid sign that you can’t respond to them any other way. (For example, I’ll note that that you completely ignore the fact the “amazing properties” that you claim for 9 and 11 only exist in base-10, and that they exist for 6/11/13 in base 12, 8/15/17 in base 16, and so on. Instead of actually responding to the criticism that your special properties are only special for notational reasons, you just ignore the point, and respond with a ton of pointless personal attacks. Could it possibly be because you can’t actually answer that criticism?)
That is backwards. I thanked Mark for sparing me the trouble of an answer to your comment. You should suggest that Mark polishes my apple.
Of course, that would destroy your argument, but hey – why avoid your beaten path?
“B) Tone down the personal attacks, or you’re out of here. I’ll tolerate all sorts of pig-ignorant bullshit, but I won’t tolerate pointless personal attacks” …. BULLSHIT, I will counter attack when I’m attacked and I don’t need your authorization to do so, especially when your determination is so biased favoring ass kissers.
“For example, I’ll note that that you completely ignore the fact the “amazing properties” that you claim for 9 and 11 only exist in base-10, and that they exist for 6/11/13 in base 12, 8/15/17 in base 16″….What is it you don’t understand about “reduction” mathematics where the ordered magnitude is “Nine” then everything equates to “nine” where 10 is (9+1), 11 = (9+2) therefore two 99’s is 198 and three 99’s are 297 so five 99’s = 495 It is the Mobius twist to the (dynamic/static) relationship. This is how to conjugate 1 thru 9 and 0 thru 9 as nine and ten values while maintaining 9 as it’s magnitude. (9+10) = 19 = (1+9) =10 = (1+0) = 1 “reduction”
Why do you think when one takes any three digit number in declining order as; 983 reverser them 389 and subtracts the smaller from the larger (983-389)= 594 then reverse 594 to 495 and add (594+495) = 1089 every time, regardless of what three declining numbers are used.. Do you really think this is a trick?
apple polishing Torbjörn Larsson, OM
At least we’ve established it’s “ass-kissing” who’s ever lips are puckered (Torbjörn).
Ray:
(A) Congratulations. You’re out of here.
(B) No, I don’t *think* that’s a trick, I *know* it’s a trick.
Ray: it should be “it’s genius… but WHOSE.”
So you don’t realize the reverse order is stupid. Why would a blogger be concerned with a single poster?
Hmm. Not enough logic comprehension for a math blog perhaps, on part of that Anonymous blogger.