# 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 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.

Proof:

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. 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}$

QED.

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.

Definition:

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}$.

Regards.

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 !

Regards,

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

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

Then,

$\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.” 🙂

Regards,

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.