[Tutor] determining whether a set is a group

[Corran Webster]

>Daniel Yoo wrote:
>
>>  On Sat, 28 Apr 2001, Sheila King wrote:
>>
>>  > The axioms (basic rules) for a group are:
>>  > ( where the dot (•) symbolizes some operation...)
>>  >
>>  >    1.CLOSURE: If a and b are in the group then a • b is also in the group.
>>  >    2.ASSOCIATIVITY: If a, b and c are in the group then (a • b) 
>>• c = a • (b •
>>  > c).
>>  >    3.IDENTITY: There is an element e of the group such that for 
>>any element a
>>  > of the group
>>  >      a • e = e • a = a.
>>  >    4.INVERSES: For any element a of the group there is an 
>>element a^(-1) such
>>  > that
>>  >           a • a^(-1) = e
>>  >           and
>>  >           a^(-1) • a = e
>>
>
>The pb is that my computer can't handle very well infinite sets... how does a
>program like Mapple handle this kind of things ?

Programs like Mathematica and Maple handle infinite sets either by 
approximation (eg. for real numbers) or by dealing with a finite 
subset and hoping it doesn't get too big.  This is much the same as 
the way that python handles the potentially infinite, with floating 
point numbers and long integers.  Indeed it's universal for all 
computers without unlimited memory  ;)

Programs and routines in Maple for dealing with infinite groups 
almost certainly assume that the operations that you supply are valid 
group operations.

>How can i implement something whose cardinal is Cantor something 
>(ie. infinite) ?

In Python you could go a long way by defining a class to represent 
the elements of the set and using the __mul__, __div__ etc. special 
methods to implement the group operations.  This would allow you to 
work with a finite number of elements at a time, but taken from an 
infinite group.

You couldn't solve Julieta's problem for an infinite group using this 
sort of thing, however.

As far as I can see, the best solution to the original problem (given 
a finite set and the Cayley matrix of an operation on the set, is it 
a group?) is a brute force checking of the axioms.  For efficiency 
it's probably best use a dictionary to represent the matrix, rather 
than a list of lists, and for generality it's probably better to have 
the algortihm work with the operation as a function, rather than 
directly with the matrix, but I could be wrong.

Eg. (untested code)

def cayleyToOp(set, cayley):
   """Given a set and a Cayley matrix, returns a function which 
performs the operation on two elements."""
   matrix = {}
   for a in range(len(set)):
     for b in range(len(set)):
       matrix[(set[a], set[b])] = cayley[a][b]
   return lambda a, b, matrix=matrix: matrix[(a,b)]

Z3 = [0, 1, 2]
Z3Cayley = [[0,1,2], [1,2,0], [2,0,1]]
Z3op = cayleyToOp(Z3, Z3Cayley)

print Z3op(1,1)
#should print 2

of course Z3op could be more efficiently implimented as

def Z3op(a, b):
   return (a+b) % 3

which is why the group checking stuff will be more flexible if you 
allow functions.

>Although i remember what a group is , i don't remember what groups are useful
>for....... any math teachers?

As it so happens, I teach math at UNLV.  Groups typically come up in 
situations where there is symmetry of some sort and so can be used to 
describe the symmetry which is present.  Knowing symmetries can help 
you find and classify solutions to concrete problems.

They are also one of the fundamental building blocks of abstract 
algebra and most interesting algebraic systems involve some sort of 
group structure.  The standard addition of numbers is an example of a 
group.

Regards,
Corran