Identity elements, monoids

Suppose \({ ( A , f ) }\) is a semigroup, i.e. that \({ f }\) is an associative binary operation on the set \({ A }\). A member \({ i }\) of \({ A }\) is said to be an identity element if for all \({ x ∈ A }\) we have \[ f ( i , x ) = x \] and \[ f ( x , i ) = x . \] Going back to our earlier examples of associative operations we can see that all but one of them have identity elements.

For the ones which do have an identity element it’s straightforward in each case to see that the given element is indeed an identity. For the minimum the non-existence of an identity is the statement that there is no natural number \({ i }\) such that \[ \min ( i , x ) = x \] and \[ \min ( x , i ) = x \] for all \({ x }\), which is clear because the equations above would fail for \({ x = i + 1 }\).

I’ve referred to an identity rather than the identity above to allow for the possibility that there might be more than one, but in fact this can’t happen. Suppose \({ i }\) and \({ j }\) are identity elements. Then \[ f ( i , j ) = j \] because \({ i }\) is an identity and \[ f ( i , j ) = i \] because \({ j }\) is an identity so \[ i = j . \]

A semigroup with an identity element is called a monoid, so all the semigroups listed above, except for the minimum operation on the natural numbers, are monoids.

A subsemigroup of a monoid which contains the identity element is also a monoid, with the operation being the restriction of the original operation and the identity being the identity from the larger monoid. The subsemigroup is then called a submonoid. The set of even natural numbers, considered earlier as a subsemigroup of the natural numbers, is a submonoid. Not all subsemigroups of a monoid are submonoids though.

Another example of a monoid is what’s called the bicyclic semigroup. The set in this case is the set \({ N ^ 2 }\) of ordered pairs of natural numbers and the binary operation is \[ f ( ( a , b ) , ( c , d ) ) = ( a + c - \min ( b , c ) , b + d - \min ( b , c ) ) . \] I will skip the straightforward but tedious verification that this operation is associative and therefore that this is a semigroup. It is not commutative since \[ f ( ( 0 , 1 ) , ( 1 , 0 ) ) = ( 0 , 0 ) \] while \[ f ( ( 1 , 0 ) , ( 0 , 1 ) ) = ( 1 , 1 ) . \] We have \[ f ( ( 0 , 0 ) , ( x , y ) ) = ( x , y ) \] and \[ f ( ( x , y ) , ( 0 , 0 ) ) = ( x , y ) \] for all \({ ( x , y ) }\) so \({ ( 0 , 0 ) }\) is an identity element. This is therefore not just a semigroup but a monoid. It would make more sense therefore to refer to it as the bicyclic monoid, but for historical reasons it is referred to as the bicyclic semigroup. That name isn’t wrong, since it is a semigroup, but it’s imprecise.