MaBloWriMo 19: groups from monoids

So, you have a monoid, that is, a set with an associative binary operation that has an identity element. But not all elements have inverses, so it is not a group. Assuming you really want a group, what can you do?

It turns out there is a very simple answer: just throw away all the elements that don’t have inverses! That is, given a monoid M, form the subset M^* \subset M of all the elements of M that do have an inverse with respect to the binary operation. I claim that M^* is in fact a group (under the same binary operation). Let’s prove it. We have to check that M^* satisfies all the laws of a group.

  • By assumption, there is some e \in M which is the identity for the binary operation. So in particular e \odot e = e, which means that e is its own inverse; so e \in M^*.
  • We know all the elements in M^* have an inverse in M, but we still need to make sure those inverses actually end up in M^*! If a \in M^* then by definition a has an inverse, a^{-1}, which means that a \odot a^{-1} = a^{-1} \odot a = e. Note that these equations are completely symmetric: not only is a^{-1} the inverse for a, we can also say that a is the inverse for a^{-1}. So a^{-1} must be in M^* too.
  • If the binary operation is associative for M then it will definitely be assocative for M^* too (since associativity holds for all elements of M, of which M^* is a subset).
  • There is one more crucial thing we have to check: it is not a priori clear that M^* is even closed under the binary operation—might there be some a, b \in M^* such that a \odot b is in M but not in M^*?. But in fact if a and b both have inverses, then a  \odot b must have an inverse as well, namely, b^{-1} \odot  a^{-1}, since

    (b^{-1} \odot a^{-1}) \odot (a \odot b) = b^{-1} \odot (a^{-1} \odot a) \odot b = b^{-1} \odot b = e.

    (The fact that (a \odot b)^{-1} = b^{-1} \odot a^{-1} is sometimes called the “socks-shoes property”: you put on your socks first (a), and then your shoes (b); the inverse operation is to first take off your shoes (b^{-1}), then your socks (a^{-1}).)

    So if a and b are in M^* then a \odot b must be as well.

Advertisements

About Brent

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in algebra, group theory, proof and tagged , , , , , . Bookmark the permalink.

One Response to MaBloWriMo 19: groups from monoids

  1. Pingback: MaBloWriMo 20: the group X star | The Math Less Traveled

Comments are closed.