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.
\({ ∧ }\) on Boolean truth values: the value false is an identity element.
\({ ∨ }\) on Boolean truth values: the value true is an identity element.
\({ + }\) on the natural numbers: 0 is an identity element.
\({ · }\) on the natural numbers: 1 is an identity element.
the maximum operation on natural numbers: 0 is an identity element.
the minimum operation on natural numbers: there is no identity element.
\({ ⋂ }\) on the power set of a given set: the whole set is an identity element.
\({ ⋃ }\) on the power set of a given set: the empty set is an identity element.
\({ ∘ }\) on the set of functions from a given set to itself: the identity function is an identity element.
\({ ∘ }\) on the set of relations on a given setf: the identity function is an identity element.
the concatenation operation on lists all of whose items belong to a given set: the empty list is an identity element.
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.