[Tutor] Having Python figure out whether a set is a group

[Sheila King]

On Mon, 30 Apr 2001 19:43:38 -0500, "Julieta Rangel"
<julieta_rangel@hotmail.com>  wrote about [Tutor] Having Python figure out
whether a set is a group:

:Given the following table, how can I make the computer verify whether the 
:following set is a group or not?  The set is G = {e,a,b,ab)
:The table under the binary operation * with the elements of the set looks 
:like:
:
:         *_|     e    a    b    ab
:         ---------------------------
:          e|     e    a    b    ab
:          a|     a    e    ab   b
:          b|     b    ab   e    a
:         ab|     ab   b    a    e
:
:The computer would have to check the 4 properties of groups (closure, 
:associativity, identity element, and inverse element).  By the way, the set 
:G is in fact a group. It is closed under the binary operation (a * b = ab, 
:and ab is in G, b * ab =a and a is in G, etc), it is associative (a * (b * 
:ab) = (a * b) * ab; e * (a * b) = (e * a) * b, etc), it has an identity 
:element e (a * e = a, b * e = b, ab * e = ab, e * e = e), and every element 
:is an inverse of itself (Note: a*a = e, b*b = e, ab*ab = e, and e*e = e).How 
:could the computer check for closure?  I'm assuming the computer would have 
:to go through the elements in the table and compare them with the original 
:set.  How could this be done?  This problem requires some thinking.  Does 
:anyone want to help or do you know where I can go for help?

How about storing your table as a dictionary? Here is a partial idea:

>>> e='e'
>>> a='a'
>>> b='b'
>>> ab='ab'
>>> table ={}
>>> table[(e,e)]=e
>>> table[(e,a)]=a
>>> table[(e,b)]=b
>>> print table
{('e', 'e'): 'e', ('e', 'b'): 'b', ('e', 'a'): 'a'}
>>> 

To check for closure, have a list of the set values. I constructed a list from
the table (after I finished entering all the values for the table) as follows:

>>> set = []
>>> for elt in table.keys():
... 	if elt[0] not in set:
... 		set.append(elt[0])
... 		
>>> print set
['a', 'ab', 'b', 'e']
>>> 

Now, to check for closure, just test to see whether each item in
tables.values() is in the set. If not, then it is not closed.

To check for associativity, for example,
find the value of (a,b) and then take that value (which we know is ab) and
cross it with another element (let's say, e) and see if (ab, e) is equivalent
to
a crossed with the result of (b, e)

To test for an identity element, you could check whether there is an item in
the set, where (item, whatever) == whatever, for each whatever in the set, and
also check whether (whatever, item) == whatever.

And, to check for inverses...once you've confirmed the existence of an
identity element, check for each element in the set, whether there is a pair
such that (element, something) == identity element.

Actually, I think I really like this idea of storing the table off as a
dictionary. The table really is a function (mathematically speaking), which is
a mapping, which is what a dictionary represents.

--
Sheila King
http://www.thinkspot.net/sheila/
http://www.k12groups.org/