Skip to content

Instantly share code, notes, and snippets.

@anfedorov
Last active August 29, 2015 14:26
Show Gist options
  • Save anfedorov/f796e5d8703b8b3aaee3 to your computer and use it in GitHub Desktop.
Save anfedorov/f796e5d8703b8b3aaee3 to your computer and use it in GitHub Desktop.
def check_group(S, O, check_abelian=False):
"""Checks group properties on set S and operation O.
Arguments:
S (set): elements of this group
O (callable): operation on two elements of S, returns an element of S
check_abelian (bool): check if this is an abelian group
"""
# check that S is closed under O
for a in S:
for b in S:
x = O(a, b)
y = O(b, a)
assert x in S, ('error: S must be closed under O!', a, b, x)
assert y in S, ('error: S must be closed under O!', a, b, y)
if check_abelian:
assert x == y, 'error: O(%s,%s) not commutative!' % (a, b)
# check associativity
for a in S:
for b in S:
for c in S:
assert O(O(a, b), c) == O(a, O(b, c)), 'error: not associative!'
# check identity element is unique
is_id = lambda i, s: O(s, i) == O(i, s) == s
identities = {i for i in S if all(is_id(i, b) for b in S)}
assert len(identities) == 1, 'no identity element found!'
e = identities.pop()
# check inverse exists
for a in S:
invs_of_a = [b for b in S if O(a, b) == e and O(b, a) == e]
assert len(invs_of_a) > 0, 'error: %s has no inverse!' % a
return S, O
# trivial group
check_group({0}, lambda a, b: a)
# int_mod2 under addition
check_group({0, 1}, lambda a, b: (a + b) % 2)
# even_int_mod8 under addition
check_group({0, 2, 4, 6}, lambda a, b: (a + b) % 8)
# int_mod8 under addition
check_group({0, 1, 2, 3, 4, 5, 6, 7}, lambda a, b: (a + b) % 8)
# int_mod7 sans 0 under multiplication
check_group({1, 2, 3, 4, 5, 6}, lambda a, b: (a * b) % 7)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment