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.

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

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