Generalized associative law, gen comm law etc.

Reference : Algebra by Hungerford, Springer Verlag, GTM.

Let G be a semigroup. Given a_{1}, a_{2}, a_{3}, \ldots, a_{n} \in G, with n \geq 3, it is intuitively plausible that there are many ways of inserting parentheses in the expression latex a_{1}a_{2}\ldots a_{n}$ so as to yield a “meaningful” product in G of these n elements in this order. Furthermore, it is plausible that any two such products can be proved equal by repeated use of the associative law. A necessary prerequisite for further study of groups and rings is a precise statement and proof of these conjectures and related ones.

Given any sequence of elements of a semigroup G, (a_{1}a_{2}\ldots a_{n}) define inductively a meaningful product of a_{1}, a_{2}, \ldots, a_{n} (in this order) as follows: If n=1, the only meaningful product is a_{1}. If n>1, then a meaningful product is defined to be any product of the form (a_{1}\ldots a_{m})(a_{m+1}\ldots a_{n}) where m<n and (a_{1}\ldots a_{m}) and (a_{m+1} \ldots a_{n}) are meaningful products of m and n-m elements respectively. (to show that this statement is well-defined requires a version of the Recursion Theorem). Note that for each n \geq 3 there may be meaningful products of a_{1}, a_{2}, \ldots, a_{n}. For each n \in \mathcal{N}^{*} we single out a particular meaningful product by defining inductively the standard n product \prod_{i=1}^{n}a_{i} of a_{1}, \ldots, a_{n} as follows:

\prod_{i=1}^{1}a_{i}=a_{1}, and for n>1, \prod_{i=1}^{n}a_{i}=(\prod_{i=1}^{n-1})a_{n}

The fact that this definition defines for each n \in \mathcal{N}^{*} a unique element of G (which is clearly a meaningful product) is a consequence of the Recursion Theorem.

Theorem: Generalized Associative Law:

If G is a semigroup and a_{1}, a_{2}, \ldots, a_{n} \in G, then any two meaningful products in a_{1}a_{2}\ldots a_{n} in this order are equal.


We use induction to show that for every n any meaningful product a_{1}a_{2} \ldots a_{n} is equal to the standard n product \prod_{i=1}^{n}a_{i}. This is certainly true for n=1, 2. For n>2, by definition, a_{1}a_{2} \ldots a_{n} = (a_{1}a_{2}\ldots a_{m})(a_{m+1} \ldots a_{n}) for some m<n. Therefore by induction and associativity:

(a_{1}a_{2} \ldots a_{n}) = (a_{1}a_{2} \ldots a_{m})(a_{m} \ldots a_{n}) = (\prod_{i=1}^{m}a_{i})(\prod_{i=1}^{n-m})a_{m+i}

= (\prod_{i=1}^{m}a_{i}) ((\prod_{i=1}^{n-m-1}a_{m+i})a_{n} ) = ((\prod_{i=1}^{m})(\prod_{i=1}^{n-m-1}a_{m+i}))a_{n} = (\prod_{i=1}^{n-1}a_{i})a_{n} = \prod_{i=1}^{n}a_{i}


Corollary: Generalized Commutative Law:

If G is a commutative semigroup and a_{1}, \ldots, a_{n}, then for any permutation i_{1}, \ldots, i_{n} of 1, 2, …,n a_{1}a_{2}\ldots a_{n} = a_{i_{1}}a_{i_{2}}\ldots a_{i_{n}}

Proof: Homework.


Let G be a semigroup with a \in G and n \in \mathcal{N}^{*}. The element a^{n} \in G is defined to be the standard n product \prod_{i=1}^{n}a_{i} with a_{i}=a for 1 \leq i \leq n. If G is a monoid, a^{0} is defined to be the identity element e. If G is a group, then for each n \in \mathcal{N}^{*}, a^{-n} is defined to be (a^{-1})^{n} \in G.

It can be shown that this exponentiation is well-defined. By definition, then a^{1}=a, a^{2}=aa, a^{3}=(aa)a=aaa, \ldots, a^{n}=a^{n-1}a…and so on. Note that it is possible that even if n \neq m, we may have a^{n} = a^{m}.


Nalin Pithwa

A non trivial example of a monoid

Reference : Algebra 3rd Edition, Serge Lang. AWL International Student Edition.

We assume that the reader is familiar with the terminology of elementary topology. Let M be the set of homeomorphism classes of compact (connected) surfaces. We shall define an addition in M. Let S, S^{'} be compact surfaces. Let D be a small disc in S, and D^{'} in S^{'}. Let C, C^{'} be the circles which form the boundaries of D and D^{'} respectively. Let D_{0}, D_{0}^{'} be the interiors of D and D^{'} respectively, and glue S-D_{0} to S^{'}-D_{0}^{'} by identifying C with C^{'}. It can be shown that the resulting surface is “independent” up to homeomorphism, of the various choices made in preceding construction. If \sigma, \sigma_{'} denote the homeomorphism classes of S and S^{'} respectively, we define \sigma + \sigma_{'} to be the class of the surface obtained by the preceding gluing process. It can be shown that this addition defines a monoid structure on M, whose unit element is the class of the ordinary 2-sphere. Furthermore, if \tau denotes the class of torus, and \pi denotes the class of the projective plane, then every element \sigma of M has a unique expression of the form

\sigma = n \tau + m\pi

where n is an integer greater than or equal to 0 and m is zero, one or two. We have 3\pi=\tau+n.

This shows that there are interesting examples of monoids and that monoids exist in nature.

Hope you enjoyed !


Nalin Pithwa

Algebra is symbolic manipulation though painstaking or conscientious :-)

Of course, I have oversimplified the meaning of algebra. 🙂

Here is an example. Let me know what you think. (Reference: Algebra 3rd Edition by Serge Lang).

Let G be a commutative monoid, and x_{1}, x_{2}, \ldots, x_{n} be elements of G. Let \psi be a bijection of the set of integers (1,2, \ldots, n) onto itself. Then,

\prod_{v=1}^{n}x_{\psi(v)} = \prod_{v=1}^{n}x_{v}

Proof by mathematical induction:

PS: if one gets scared by the above notation, one can expand it and see its meaning. Try that.

It is clearly true for n=1. We assume it for n=1. Let k be an integer such that \psi(k)=n. Then,

\prod_{i}^{n}x_{\psi(v)} = \prod_{1}^{k-1}x_{\psi(v)}.x_{\psi(k)}.\prod_{1}^{n-k}x_{\psi(k+v)}

= \prod_{1}^{k-1}x_{\psi(v)}. \psi_{1}^{n-k}x_{\psi(k+v)}.x_{\psi(k)}

Define a map \phi of (1,2, \ldots, n-1) into itself by the rule:

\phi(v)=\psi(v) if v<k

\phi(v) = \psi(v+1) if v \geq k


\prod_{1}^{n} x_{\psi(v)} = \prod_{1}^{k-1}x_{\phi(v)}. \prod_{1}^{n-k}x_{\phi(k-1+v)} = \prod_{1}^{n-1}x_{\phi(v)}.x_{n}

which by induction is equal to x_{1}\ldots x_{n} as desired.

Some remarks: As a student, I used to think many a times that this proof is obvious. But it would be difficult to write it. I think this cute little proof is a good illustration of “how to prove obvious things in algebra.” 🙂


Nalin Pithwa

Wisdom of Hermann Weyl w.r.t. Algebra

Important though the general concepts and propositions may be with which the modern and industrious passion for axiomatizating and generalizing has presented us, in algebra perhaps more than anywhere else, nevertheless I am convinced that the special problems in all their complexity consitute the stock and core of mathematics, and that to master their difficulties requires on the whole hard labour.

—- Prof. Hermann Weyl.