Semigroups

A pair \({ ( A , f ) }\), where \({ A }\) is a set and \({ f }\) is an associative binary operation on \({ A }\), is called a semigroup.

If \({ ( A , f ) }\) is a semigroup and \({ B }\) is a subset of \({ A }\) then we can restrict \({ f }\) to get a function from \({ B ^ 2 }\) to \({ A }\). If the range of this function is a subset of \({ B }\), i.e. if \({ f ( x , y ) ∈ B }\) whenever \({ x ∈ B }\) and \({ y ∈ B }\), then this restriction is a binary operation on \({ B }\). It is necessarily associative because if \({ x ∈ B }\), \({ y ∈ B }\), and \({ z ∈ B }\), then \({ x ∈ A }\), \({ y ∈ A }\), and \({ z ∈ A }\), and so \[ f ( x , f ( y , z ) ) = f ( f ( x , y ) , z ) , \] by the associativity of \({ f }\) on \({ A }\). If \({ f ( x , y ) ∈ B }\) whenever \({ x ∈ B }\) and \({ y ∈ B }\) then we say that \({ B }\) is a subsemigroup of \({ A }\). As an example, the set of even natural numbers, with addition as the operation, is a subsemigroup of the natural numbers, also with addition. Not every subset is a subsemigroup though. The set of prime numbers is not a subsemigroup because the sum of prime numbers needn’t be prime.

There is a general associativity property for semigroups which I hinted at with the equation \[ f ( w , f ( x , f ( y , z ) ) ) = f ( f ( w , x ) , f ( y , z ) ) = f ( f ( f ( w , x ) , y ) , z ) \] above. In stating this it’s convenient to use the word “multiplication” for the function \({ f }\), even though multiplication is just one of the possible binary operations we might consider, and to refer to the result of applying \({ f }\) to two members of \({ A }\) as the “product” of those elements. With this convention the generalised associativity property we want to prove says that the order in which multiple multiplications is performed doesn’t change the final product.

One way to state it more precisely, related to our discussion of parsing earlier, is in terms of binary trees. Given a list of \({ n }\) members of \({ A }\) and a binary tree with \({ n }\) leaves we can compute a corresponding product by filling in the list items in the leaves and then proceeding up the tree to the root, multiplying the values of a node’s children to obtain its value. There are, for example, five possible shapes for a binary tree with four leaves, which you found in Assignment 0. Each of these gives a different way to compute the product of a list \({ ( w , x , y , z ) }\) of members of \({ A }\), illustrated in the five accompanying figures.

One way to see that these are all give the same result for any associative operation is to look at the accompanying graph, where the five vertices are the five products and the edges connect those products which can be shown equal with a single application of the associative law.

The fact that this graph is connected implies that we can show any two are equal via repeated applications of the associative law, since any walk tells us the order in which we need to apply the associative law in order to get from the product labeling its initial vertex to the one labeling its final vertex.

Nothing but boredom prevents us from doing the same thing for products of size \({ n }\) for any larger value of \({ n }\). The accompanying diagram shows the graph for \({ n = 5 }\).

It’s harder to see, visually, that this graph is connected, but it is. We’d like an argument which applies to all values of \({ n }\) though, rather than treating each one separately.

The easiest way to prove that all possible products for a given list are equal is to prove that each is equal to some particular product. We’ll call the product where we take our list and continue multiplying the two leftmost items until there’s only a single item the leftmost product. In our earlier example, starting with the original list \({ ( w , x , y , z ) }\) we would go through the steps \({ ( f ( w , x ) , y , z ) }\), then \({ ( f ( f ( w , x ) , y ) , z ) }\), then \({ ( f ( f ( f ( w , x ) , y ) , z ) ) }\) so the leftmost product would be \({ f ( f ( f ( w , x ) , y ) , z ) }\), the second of the trees shown previously, and the one which leans to the left the most. This is the product which we will show that all others are equal to. We won’t define the leftmost product of the empty list but the leftmost product of a list with only a single item is just that item, which is the trivial case of the procedure described above of multiplying the leftmost items until only a single item remains.

We can start with the special case that the product of two leftmost products is a leftmost product. In other words if \({ p }\) is the leftmost product of some list \({ P }\) of members of \({ A }\) and \({ q }\) is the leftmost product of some list \({ Q }\) of members of \({ A }\) then \({ f ( p , q ) }\) is equal to the leftmost product of the concatenation of the list \({ P }\) and the list \({ Q }\). If this were not true then there would be a shortest list \({ Q }\) for which it failed. We’re not defining lists of length zero so \({ Q }\) is either of length one or length greater than one. If it’s of length one then it is just \({ ( q ) }\) and the concatenation of \({ P }\) and \({ Q }\) is the list \({ P }\) with a \({ q }\) appended at the end. When we compute its leftmost product as described above we first multiply all the items to the left of this final \({ q }\), obtaining \({ p }\) and then multiply it with \({ q }\), obtaining \({ f ( p , q ) }\), which is what we’re meant to find, so the property cannot fail when \({ Q }\) is of length one. It follows that \({ Q }\) must of length greater than one. Let \({ R }\) be the list consisting of all but the last item in \({ Q }\) and let \({ s }\) be the last item. Let \({ r }\) be the leftmost product of \({ R }\). Then \[ q = f ( r , s ) \] so \[ f ( p , q ) = f ( p , f ( r , s ) ) \] and hence, by the associativity property, \[ f ( p , q ) = f ( f ( p , r ) , s ) . \] Now \({ R }\) and \({ ( s ) }\) are shorter then \({ Q }\) and \({ Q }\) is a list of the least length for which the product of the leftmost products is not the leftmost product so \({ f ( p , r ) }\) is the leftmost product of the concatenation of \({ P }\) and \({ R }\). and \({ f ( f ( p , r ) , s ) }\) is the leftmost product of the concatenation of that list with \({ ( s ) }\), which is the concatenation of \({ P }\) with \({ Q }\). In other words \({ f ( p , q ) }\) is the leftmost product of the concatenation of \({ P }\) with \({ Q }\). We’ve just seen that even if we assume we have a counterexample to the statement that the product of the leftmost products is the leftmost product of the concatenation then we find out that it isn’t one. There therefore isn’t a counterexample. This concludes the proof of the special case.

We can now continue to the proof of the general case. Suppose there is a product of a list which is not equal to the leftmost product. There must then be a shortest such list. We haven’t defined products for lists of length zero and there’s only one possible product for a list of length one so our list must be of length greater than one and so must be of the form \({ f ( p , q ) }\) where \({ P }\) and \({ Q }\) are lists whose concatenation is this list and \({ p }\) and \({ q }\) are some products of \({ P }\) and \({ Q }\). But \({ P }\) and \({ Q }\) are shorter than the whole list and so any product for them is equal to the leftmost product. The previous paragraph therefore shows that \({ f ( p , q ) }\) is equal to the leftmost product of the concatenation of \({ P }\) and \({ Q }\), which is the list we started with. So again, even if we assume the existence of a counterexample we find that it isn’t one.

So now any two products for a list are equal to the leftmost product and therefore equal to each other, and therefore all products for a list are equal. We can therefore forget about the order of products in a semigroup.