2. Binary Operations, Closure, and Semigroups

The basic definitions of algebra.

A function

\(* : A\times A\to A\)

is called a binary operation on A and a subset B of A is said to be closed under the binary operation if for any a and b in B ∗(a,b) is in B. We usually write a∗b or even ab (and we say “a times b“ for a generic operation) for ∗(a,b). A magma is a set A equipped with a binary operation ∗, written (A,∗) or simply A when ∗ is understood.

An operation on A is said to be associative if for any a, b, and c in A,

\((ab)c=a(bc).\)

In this case, we call A a semigroup. if B is a subset of A which is closed under the same operation as A, then we call B a subsemigroup of A.

It is important to note that associativity in no way implies commutativity, the property where for any a and b in A, ab=ba. I now give some examples of semigroups. It is left to the reader to prove that they are indeed semigroups.

• The set of real numbers under addition or multiplication

• The set of integers under addition/multiplication is a subsemigroup of the real numbers under addition/multiplication

• The set of even integers under addition or multiplication is a subsemigroup of the set of integers under addition/multiplication

• The set of all functions from a set to itself

• The set of all bijections from a set to itself is a subsemigroup of the set of all functions from a set to itself

• Square matrices under matrix multiplication or addition

Notably, the set of odd integers is NOT a semigroup, since 1+1=2, which is not odd. Finite semigroups may be described with a multiplication table where each entry represents the product of its row label (on the left) by its column label (on the right). A multiplication table can be checked for associativity via Light’s test.

Exercise: Consider the set S composed of rock, paper, and scissors defined by the below multiplication table. Is S a semigroup? Is S commutative?

We can also use the Cartesian product to construct a new semigroup from two existing semigroups.

Proposition: Let S and T be semigroups (written multiplicatively). Then the cartesian product of S and T is a semigroup with the following multiplication (s’s are in S and t’s in T):

\((s_1,t_1)(s_2,t_2)=(s_1s_2,t_1t_2).\)

Proof: It is evident from the definition that the Cartesian product is closed under multiplication and that multiplication is defined for all pairs. It then remains to check that multiplication is associative. We compute:

\(((s_1,t_1)(s_2,t_2))(s_3,t_3)=(s_1s_2,t_1t_2)(s_3,t_3)=((s_1s_2)s_3,(t_1t_2)t_3)\)

and

\((s_1,t_1)((s_2,t_2)(s_3,t_3))=(s_1,t_1)(s_2s_3,t_2t_3)=(s_1(s_2s_3),t_1(t_2t_3)).\)

Since multiplication in S and T is associative, we have that

\(((s_1s_2)s_3,(t_1t_2)t_3)=(s_1(s_2s_3),t_1(t_2t_3))\)

so multiplication in the cartesian product is associative. □