A non-empty set $ G $ that can perform some "binary operation" (That is, if $ g, h \ in G $, there is a binary operation $ g \ cdot h $, and the operation result is also the element of G, that is, $ g \ cdot h \ in G $) Those that meet the following conditions are called groups.
-(Identity element) There is an element $ e \ in G $ called an identity element, and $ e \ cdot a = a \ cdot e = a $ holds for any element $ a \ in G $. -(Inverse element) For any element $ a \ in G $, a certain element $ b \ in G $ exists, and $ a \ cdot b = b \ cdot a = e $ holds. $ b $ is called the inverse element of $ a $ and is written as $ a ^ {-1} $ -(Associative law) For any element $ a, b, c \ in G $, $ (a \ cdot b) \ cdot c = a \ cdot (b \ cdot c) $ holds.
--The integers that can be added are groups (identity element → $ 0 $, inverse element of $ a $ → $ -a $, associative law → addition is known to hold the associative law) --There are also groups of rational numbers that can be added (same as above). There are also groups of rational numbers minus 0 that can be multiplied. (If it is a rational number including 0, it is not a group because the inverse element of 0 cannot be defined.)
Free groups have no restrictions other than the definition of groups.
Here, we consider $ F_2 $ generated from two elements in the free group. In other words, from the identity element, the two elements $ a, b \ in F_2 $, and the inverse element $ a ^ {-1}, b ^ {-1} $, choose the one you like and calculate, and you like Think of something that can be repeated as many times as possible.
I understand that the inverse element of $ a $ is $ a ^ {-1} $, but what about the inverse element of a combination such as $ ab ^ {-1} aab $? Actually, this is the inverse element of each element, and the order is reversed, that is, $ b ^ {-1} a ^ {-1} a ^ {-1} ba ^ {-in this case. 1} $ is the inverse element. In fact, when I try to calculate these
\begin{eqnarray}
ab^{-1}aab\cdot b^{-1}a^{-1}a^{-1}ba^{-1} & = & ab^{-1}aa \cdot a^{-1}a^{-1}ba^{-1}\\
& = & ab^{-1}a \cdot a^{-1}ba^{-1}\\
& = & ab^{-1} \cdot ba^{-1}\\
& = & a \cdot a^{-1}\\
&=&e\\
\\
b^{-1}a^{-1}a^{-1}ba^{-1}\cdot ab^{-1}aab & = & b^{-1}a^{-1}a^{-1}b\cdot b^{-1}aab\\
& = & b^{-1}a^{-1}a^{-1}\cdot aab\\
& = & b^{-1}a^{-1}\cdot ab\\
& = & b^{-1}\cdot b\\
& = & e
\end{eqnarray}
You can see that it is the inverse element.
Python is easy to do because operator overloading is easy. I will try it immediately.
As an implementation policy, we will have $ a $ and $ ab $ as strings. Also, the inverse element will be held by uppercase letters A and B.
For the inverse element calculation, use the str.swapcase
method to flip the string.
I've been using Python for many years, but this is the first time I've used swapcase
in my life.
This method is to make uppercase letters lowercase and lowercase letters uppercase.
'heLLo woRLd,ゎ ゎ ゎ ωπ'.swapcase() # =>The result is next
'HEllO WOrlD,ゎ ゎ ΩΠ'
Unfortunately (?), Small hiragana does not grow, but it seems that Greek letters are converted even if they are not ASCII letters. Well, I don't care about that, so let's implement it.
I've thought about the important things, so let's write the code.
from collections import namedtuple
FreeGroupBase = namedtuple('FreeGroupBase', 's')
class FreeGroup(FreeGroupBase):
def __init__(self, s: str):
if s.lower().replace('a', '').replace('b', ''):
# a,Check if it is generated only from b
raise ValueError('Unexpected element is contained')
#Inverse element~I will take it like a
def __invert__(self) -> 'FreeGroup':
return FreeGroup(self.s.swapcase()[::-1])
#Arithmetic*I will do it in
def __mul__(self, other: 'FreeGroup') -> 'FreeGroup':
return FreeGroup(self._mul_impl(self.s, other.s))
@classmethod
def _mul_impl(cls, lhs: str, rhs: str) -> str:
'Implementation of arithmetic'
if not lhs: #lhs is the identity element
return rhs
if not rhs: #rhs is the identity element
return lhs
if lhs[-1].swapcase() == rhs[0]: # ...a * ~a...In the form of, a* ~can cancel a
return cls._mul_impl(lhs[:-1], rhs[1:])
return lhs + rhs #Otherwise, it's just a string attached
def __repr__(self) -> 'str':
if not self.s:
return 'e'
return ' * '.join(e if e.lower() else '~' + e.tolower() for e in self.s)
a = FreeGroup('a')
b = FreeGroup('b')
e = FreeGroup('')
g = a * b * b * a * ~b * ~b * ~a * a * b * (a * a * b)
print(g)
print(g * ~g)
print(~g * g)
Yeah, it feels good.
Recommended Posts