From: toby@ugcs.caltech.edu (Toby Bartels)
Subject: Re: Group theory question
Date: 29 Jul 2000 02:57:18 GMT
Newsgroups: sci.math.research
Summary: [missing]

Paul Dufort wrote:

>As I understand it, you can
>think of the elements of a group as a set of transformations of the state of
>a system. Certain sequences of transformations then take the system through a
>sequence of states and back to itself, etc. The definition seems to imply that
>it must be possible to subject the system, in any of its possible states, to
>any of the possible transformations. But what if some state/transformation
>pairs don't make physical sense?

Then you need to study, not a group, but a groupoid.
(Warning!: some people use the term "groupoid" in other senses.)

Really, groups are appropriate only for systems with a single state.
For multistate systems, groupoids are most natural;
however, you can get away with groups in some cases.

Recall that a group is a set G with an identity element e,
an inverse function ', and a binary operation *,
such that e * g = g = g * e, g * g' = e = g' * g,
and (g * h) * i = g * (h * i).
Then we may interpret the elements of G as transformations;
e is the transformation of doing nothing whatsoever,
' indicates the reversal of a transformation,
and * indicates the result of performing transformations in succession.
This should all be familiar.

A groupoid is *2* sets G_0 and G_1 with
an identity *function* e from G_0 to G_1,
an inverse function ' from G_1 to G_1,
a *partially defined* binary operation * on G_1,
and 2 functions s and t from G_1 to G_0, such that
g * h is defined if and only if t_g = s_h,
s_{e_x} = x = t_{e_x}, s_g' = t_g and t_g' = s_g
s_(g * h) = s_g and t_(g * h) = t_h,
e_{s_g} * g = g = g * e_{t_g}, g * g' = e_{s_g} and g' * g = e_{t_g},
and (g * h) * i = g * (h * i) whenever * is defined for this.

Now to ground this mass of symbols with an interpretation.
G_0 is a set of *states* of a system,
while G_1 is a set of *transformations* of the system.
s is the function which indicates the source of a transformation,
while t is the function which indicates the target.
Thus, each transformation transforms its source into its target.
If two transformations don't share sources and targets,
then they are distinct transformations, however similar they may be!
In particular, there are many transformations which do nothing,
specifically, 1 for each state; these are the e_x.
' again indicates the reversal of a transformation,
and * indicates the result of performing transformations in succession
*if this is possible* (which it usually won't be).

This suggests that a group should be a groupoid with exactly 1 state.
Setting G_0 = {x} and looking at the defintions confirms this.
The functions s and t must map every g to x,
so they're not really a property of the 1state groupoid.
The function e is defined by the single element e_x,
* is automatically always defined,
the equations between certain values of s and t become trivial,
and the remaining equations reduce to those defining a group.

BTW, I have been assuming here that x * y
indicates the result of doing x and *then* y.
If you want it to mean doing y and then x
(to agree with the application of matrices to column vectors, for example),
then you must reverse the role of source (s) and target (t)
in my definition and interpretation above.
There is no general agreement about which way to do things.
The notation for e, s, and t will also vary widely;
you may see "id" for e, "dom" for s, and "cod" or "codom" for t, for example.
Of course, just as with groups, ' is usually written as a superscript "-1".

>For example, say the system consists of a single
>piece on a checker board. There are four transformations that each move the
>piece by one position up (u), down (d), left (l), or right (r). In most cases,
>the sequence u-l-d-r will take the system back to itself. But if the piece is
>already at the left border of the board, then a move left (l) is not possible.

Here, G_0 is a 64element set indicating the 64 positions on the board.
But G_1 is quite a bit larger than simply {u,l,d,r}!
For one thing, combinations like u * l * d should belong to G_1 as well.
More significantly, there are 56 different versions of u,
1 for each possible source of a u transformation; same for l, d, and r.
And we shouldn't forget about the 64 identity transformations.
Still, the 56 x 4 = 224 u, l, d, and r may be said to *generate* G_1.

Now, this 64state groupoid defines 64 different groups.
Each state x has a group G_x consisting of
all those transformations g such that s_g = x = t_g.
While no u, l, d, or r will belong to any G_x,
each of the 49 defined u * l * d * r transformations does.
The fact that l doesn't exist for every possible source
just shows that u * l * d * r doesn't exist in every possible G_x.

Nevertheless, the groups G_x are all isomorphic!
It's just that nothing as simple as u <-> u, l <-> l,
d <-> d, r <-> r ever describes the isomorphism.
Rather, to find an isomorphism between G_x and G_y,
first find a transformation g with source x and target y.
Then map h in G_x to g'hg in G_y to get the isomorphism.
Since there are many different transformations from x to y,
there is no natural choice of isomorphism, however.

A few more random comments:

Much of the relationships of groups to topology
can be more fully understood with groupoids.
Just as you can define the fundamental group on a point p,
you can define the fundamental groupoid on a set G_0 of points.
(G_0 is generally taken to be either discrete or the entire space.)

A monoid is like a group only without the inverse operation '
(so that not every transformation is invertible).
A category is like a groupoid only without '.
Categories show up all over mathematics,
and each has an associated groupoid of invertible transformations.

Arbitrary groupoids can be decomposed into connected components;
2 states x and y are connected if there is a transformation between them.
You understand the whole groupoid if you understand each component,
so people usually study only connected groupoids.
Your checkerboard example is a connected groupoid,
but a similar example involving 2 checkerboards would be unconnected.
Obviously, you can consider each checkerboard in isolation,
since the checker will always remain on whichever board it begins on.


-- Toby
   toby@ugcs.caltech.edu