Suppose \({ ( A , f ) }\) is a semigroup and \({ R }\) is an equivalence relation on \({ A }\) with the property that if \[ ( u , x ) ∈ R \] and \[ ( v , y ) ∈ R \] then \[ ( f ( u , v ) , f ( x , y ) ) ∈ R . \] Let \({ B }\) be the set of equivalence classes for the relation \({ R }\). Let \({ H }\) be the set of \({ ( x , C ) ∈ A × C }\) such that \({ x ∈ C }\). Each member of \({ A }\) is a member of an equivalence class so \({ H }\) is left total. Every member of \({ A }\) is a member of only one equivalence class so \({ H }\) is right unique. In other words \({ H }\) is a function. This means it’s safe to use standard functional notation so I’ll write \({ C = h ( x ) }\) in place of \({ ( x , C ) ∈ H }\) or \({ x ∈ C }\) from now on. Let \({ G }\) be the relation from \({ B ^ 2 }\) to \({ B }\) consisting of those \({ ( ( C , D ) , E ) ∈ B ^ 2 × E }\) for which there are \({ x ∈ C }\), \({ y ∈ D }\) and \({ z ∈ E }\) with \({ z = f ( x , y ) }\). For any \({ ( C , D ) ∈ B ^ 2 }\) we can find \({ x ∈ C }\) and \({ y ∈ D }\) since \({ R }\) is an equivalence relation. Setting \({ z = f ( x , y ) }\) and \({ E = h ( z ) }\) we have \({ ( ( C , D ) , E ) ∈ G }\), so \({ G }\) is left total. Suppose \({ ( ( C , D ) , E ) ∈ G }\) and \({ ( ( C , D ) , F ) ∈ G }\). The fact that \({ ( ( C , D ) , E ) ∈ G }\) means there are \({ u ∈ C }\), \({ v ∈ D }\) and \({ w ∈ E }\) such that \({ w = f ( u , v ) }\) and the fact that \({ ( ( C , D ) , F ) ∈ G }\) means there are \({ x ∈ C }\), \({ y ∈ D }\) and \({ z ∈ F }\) such that \({ z = f ( x , y ) }\). Since \({ u ∈ C }\) and \({ x ∈ C }\) we have \({ ( u , x ) ∈ R }\) by the definition of an equivalence class. Similarly, \({ ( v , y ) ∈ R }\). Because our assumptions about \({ f }\) and \({ R }\) we then have \({ ( f ( u , v ) , f ( x , y ) ) ∈ R }\), i.e. \({ ( w , z ) ∈ R }\). Since \({ w ∈ E }\) and \({ z ∈ F }\) it then follows from the definition of an equivalence class that \({ E = F }\). So if \({ ( ( C , D ) , E ) ∈ G }\) and \({ ( ( C , D ) , F ) ∈ G }\) then \({ E = F }\). In other words \({ G }\) is right unique. We’ve already seen that it’s left total so its a function. As with \({ H }\) I’ll now switch to functional notation and write \({ E = h ( C , D ) }\) in place of \({ ( ( C , D ) , E ) ∈ G }\) from now on. For any members \({ x }\) and \({ y }\) of \({ A }\) if we set \({ z = f ( x , y ) }\) then \({ ( ( h ( x ) , h ( y ) ) , h ( z ) ) ∈ G }\), or, in functional notation \({ h ( z ) = g ( h ( x ) , h ( y ) ) }\). We can write this as \[ h ( f ( x , y ) ) = g ( h ( x ) , h ( y ) ) . \] This equation is the one which appeared in the definition of a semigroup homomorphism.
Functions from \({ B ^ 2 }\) to \({ B }\) are binary operations on \({ B }\) so \({ G }\) is a binary operation. I claim that it’s associative. Suppose \({ C }\), \({ D }\) and \({ E }\) are members of \({ B }\). Equivalence classes are always non-empty so there are members \({ x }\), \({ y }\) and \({ z }\) of \({ A }\) such that \({ x ∈ C }\), \({ y ∈ D }\) and \({ z ∈ E }\). By the associativity of \({ f }\) we have \[ f ( f ( x , y ) , z ) = f ( x , f ( y , z ) ) , \] from which it follows that \[ h ( f ( f ( x , y ) , z ) ) = h ( f ( x , f ( y , z ) ) ) . \] Now \[ h ( f ( f ( x , y ) , z ) ) = g ( h ( f ( x , y ) ) , g ( z ) ) \] and \[ h ( f ( x , y ) ) = g ( h ( x ) , h ( y ) ) \] so \[ h ( f ( f ( x , y ) , z ) ) = g ( g ( h ( x ) , h ( y ) ) , h ( z ) ) . \] Also, \({ h ( x ) = C }\), \({ h ( y ) = D }\) and \({ h ( z ) = E }\), so \[ h ( f ( f ( x , y ) , z ) ) = g ( g ( C , D ) , E ) . \] A very similar argument shows that \[ h ( f ( f ( x , y ) , z ) ) = g ( C , g ( D , E ) ) . \] We therefore have \[ g ( g ( C , D ) , E ) = g ( C , g ( D , E ) ) . \] In other words, \({ g }\) is an associative operation on \({ B }\) and \({ ( B , g ) }\) is a semigroup.
The semigroup \({ ( B , g ) }\) is called the quotient of the semigroup \({ ( A , f ) }\) by the equivalence relation \({ R }\). We’ve already seen that \[ h ( f ( x , y ) ) = g ( h ( x ) , h ( y ) ) \] so \({ h }\) is a semigroup homomorphism.
It is straightforward to check that if \({ i }\) is an identity for \({ ( A , f ) }\) then \({ j = h ( i ) }\) is an identity for \({ ( B , g ) }\). To see this, suppose \({ C ∈ B }\). Equivalence classes are non-empty subsets so there is an \({ x ∈ C }\), i.e. an \({ x ∈ A }\) such that \({ x ∈ C }\). Then \[ g ( C , j ) = g ( h ( x ) , h ( i ) ) , \] \[ g ( h ( x ) , h ( i ) ) = h ( f ( x , i ) ) , \] \[ f ( x , i ) = x \] and \[ h ( x ) = C \] so \[ g ( C , j ) = C . \] A similar argument shows that \({ g ( j , C ) = C }\), so \({ j }\) is an identity for \({ ( B , g ) }\). So if \({ ( A , f ) }\) is a monoid then \({ ( B , g ) }\) is also a monoid and \({ h }\) is a monoid homomorphism.
Suppose \({ ( A , f ) }\) is a group. If \({ C ∈ B }\) then there is an \({ x ∈ C }\), i.e. an \({ x }\) such that \({ h ( x ) = C }\). Every element of a group is invertible so there is a \({ y ∈ A }\) which is an inverse of \({ x }\). Then \[ g ( C , h ( y ) ) = g ( h ( x ) , h ( y ) ) , \] \[ g ( h ( x ) , h ( y ) ) = h ( f ( x , y ) ) ) , \] \[ f ( x , y ) = i , \] and \[ h ( i ) = j \] so \[ g ( C , h ( y ) ) = j \] and similarly \({ g ( h ( y ) , C ) = j }\) so \({ h ( y ) }\) is an inverse of \({ C }\), which is therefore invertible. \({ C }\) was an arbitrary element of \({ B }\) so every element of \({ B }\) is is invertible. In other words, \({ ( B , g ) }\) is a group.
An argument similar to the two above shows that if \({ f }\) is a commutative binary operation on \({ A }\) then \({ g }\) is a commutative binary operation on \({ B }\), so if \({ ( A , f ) }\) is a commutative semigroup, monoid or group then \({ ( B , g ) }\) is a commutative semigroup, monoid or group.