Suppose \({ ( A , f ) }\) is a monoid with identity element \({ i }\). \({ y ∈ A }\) is said to be an inverse to \({ x ∈ A }\) if \[ f ( x , y ) = i \] and \[ f ( y , x ) = i \] and \({ x }\) is then said to be invertible. It’s immediate from the definition that \({ y }\) is an an inverse to \({ x }\) if and only if \({ x }\) is an inverse to \({ y }\). Also, the identity element is its own inverse.
As previously with identity elements I’ve deliberately written “an” rather than “the” to allow for the possibility that there might be more than one but we can show that this can’t happen. Suppose \({ y }\) and \({ z }\) are inverses to \({ x }\). Then we have the following equations: \[ f ( y , i ) = y , \] \[ f ( x , z ) = i , \] \[ f ( y , f ( x , z ) ) = y , \] \[ f ( y , f ( x , z ) ) = f ( f ( y , x ) , z ) , \] \[ y = f ( f ( y , x ) , z ) , \] \[ f ( y , x ) = i , \] \[ y = f ( i , z ) , \] \[ f ( i , z ) = z , \] \[ y = z . \] Each equation in this chain is one of the following: substitution one of two equal values for the other, the definition of an identity element applied to \({ i }\), the definition of an inverse applied to \({ y }\) or to \({ z }\), or the associativity of \({ f }\).
We can go through our list of monoids and identify the invertible elements, if any, and their inverses. In almost all cases the only invertible element is the identity. The only exception is \({ ∘ }\) on the set of functions from a given set to itself, or on the set of relations on a set, where the identity function is the identity element and the bijective functions are the invertible elements. The inverse of a function is the inverse function.
In the case of the addition operation on the natural numbers we can extend the operation to a larger monoid in such a way that every element acquires an inverse. The larger monoid in this case is the set of integers and the inverse of \({ x }\) is just \({ - x }\). In the other examples this is not possible, though this is easier to see in some cases than in others.
If \({ a }\) and \({ b }\) are invertible elements of a monoid \({ ( A , f ) }\) \({ f ( a , b ) }\) is also invertible. More precisely, let \({ c }\) be the inverse of \({ a }\) and \({ d }\) the inverse of \({ b }\). Then \({ f ( d , c ) }\) is an inverse of \({ f ( a , b ) }\). The proof is as follows. \[ f ( f ( a , b ) , f ( d , c ) ) = f ( a , f ( b , f ( d , c ) ) , \] \[ f ( a , f ( b , f ( d , c ) ) = f ( a , f ( f ( b , d ) , c ) ) , \] \[ f ( a , f ( f ( b , d ) , c ) ) = f ( a , f ( i , c ) ) , \] \[ f ( a , f ( i , c ) ) = f ( a , c ) , \] and \[ f ( a , c ) = i , \] so \[ f ( f ( a , b ) , f ( d , c ) ) = i . \] The same argument, with \({ a }\) and \({ d }\) swapped and \({ b }\) and \({ c }\) swapped gives \[ f ( f ( d , c ) , f ( a , b ) ) = i . \]
A monoid where every element is invertible is called a group.
Given a monoid the set of invertible elements has, as we just saw, the property that \({ f ( a , b ) }\) is a member if \({ a }\) and \({ b }\) are, and so is a subsemigroup. It has the identity as a member and so is a submonoid, and in particular is a monoid. Every element is invertible so it’s actually a group.
A subset of a group is called a subgroup if it is a submonoid and has the property that if \({ x }\) is a member then so is the inverse of \({ x }\). A subgroup is, as the name suggests, a group.
In all but one of the examples of monoids considered above the set of invertible elements is a trivial group, i.e. a group with no elements other than the identity. The exception is the monoid of functions from a set to itself, where we get the group of bijective functions on that set. In the important special case where the set is finite the group is called a permutation group. If the set on which our functions are defined had \({ n }\) elements then the corresponding permutation group has \({ n ! }\) elements.
Other important examples of groups are the integers, with the operation of addition, or the non-zero rationals, with the operation of multiplication, or the set of invertible matrices with a given number of rows and columns, with the operation of matrix multiplication. Another example of a group is the set of rigid motions of Euclidean space, i.e. the set of rotations, reflections, translations and the identity.
One common source of groups is symmetries of some structure. For example the set of isomorphisms of a graph is a group, with composition as the operation and the identity function as the identity. The permutation groups arise in this way, as the isomorphism groups of the complete graphs.