# proof of general associativity

We suppose that “$\cdot$” is an associative binary operation of the set $S$.

Let  $f_{1}\!:\,S\to 2^{S}$  be the mapping

 $f_{1}(a_{1})\;:=\;\{a_{1}\}\quad\forall a_{1}\in S.$

We define recursively the mapping

 $f_{n}\!:\,\underbrace{S\!\times\!S\!\times\!\ldots\!\times\!S}_{n}\to 2^{S}$

such that

 $\displaystyle f_{n}(a_{1},\ldots,\,a_{n})\;:=\;\bigcup_{r=1}^{n-1}f_{r}(a_{1},% \ldots,\,a_{r})\cdot f_{n-r}(a_{r+1},\ldots,\,a_{n})$ (1)

for  $n=2,\,3,\,4,\,\ldots$

For example,

 $f_{2}(a_{1},a_{2})\;=\;\{a_{1}\}\cdot\{a_{2}\}\;=\;\{a_{1}\cdot a_{2}\},$
 $f_{3}(a_{1},a_{2},a_{3})\;=\;\{a_{1}\cdot(a_{2}\cdot a_{3})\}\cup\{(a_{1}\cdot a% _{2})\cdot a_{3}\}\;=\;\{a_{1}\cdot(a_{2}\cdot a_{3}),\,(a_{1}\cdot a_{2})% \cdot a_{3}\}\;=\;\{(a_{1}\cdot a_{2})\cdot a_{3}\};$

the last equality due to the associativity.  It’s clear that always

 $|f_{1}(a_{1})|\;=\;1,\qquad|f_{2}(a_{1},a_{2})|\;=\;1,\qquad|f_{3}(a_{1},a_{2}% ,a_{3})|\;=\;1.$

We shall show by induction that

 $\displaystyle|f_{n}(a_{1},a_{2},\ldots,\,a_{n})|\;=\;1$ (2)

for each positive integer $n$.  This means that all groupings of the $n$ fixed elements using parentheses in forming the products with “$\cdot$” yield one single element.

We make the induction hypothesis, that (2) is true for all  $n

Now let $z$ and $z^{\prime}$ be arbitrary elements of  $f_{k}(a_{1},\ldots,\,a_{k})$.  Then there exist the elements $x,y,x^{\prime},y^{\prime}$ of $S$ and the integers$r,s\in\{1,\,\ldots,\,k\!-\!1\}$  such that

 $z\;=\;x\cdot y,\quad x\in f_{r}(a_{1},\ldots,\,a_{r}),\quad y\in f_{k-r}(a_{r+% 1},\ldots,\,a_{k}),$
 $z^{\prime}\;=\;x^{\prime}\cdot y^{\prime},\quad x^{\prime}\in f_{s}(a_{1},% \ldots,\,a_{s}),\quad y^{\prime}\in f_{k-s}(a_{s+1},\ldots,\,a_{k}).$

If specially  $r=s$,  then, by the induction hypothesis,  $x=x^{\prime}$  and  $y=y^{\prime}$,  whence  $z=x\cdot y=x^{\prime}\cdot y^{\prime}=z^{\prime}$.  If on the contrary,  $r\neq s$,  e.g.  $r,  then the induction hypothesis guarantees the existence of an element $v$ of $S$ such that

 $f_{s-r}(a_{r+1},\ldots,\,a_{s})\;=\;\{v\}$

and

 $x^{\prime}\;=\;x\cdot v,\quad y\;=\;v\cdot y^{\prime}.$

Since “$\cdot$” is associative, we have

 $z\;=\;x\cdot y\;=\;x\cdot(v\cdot y^{\prime})\;=\;(x\cdot v)\cdot y^{\prime}\;=% \;x^{\prime}\cdot y^{\prime}\;=\;z^{\prime}.$

Thus the equation (2) is in force for  $n=k$.

Title proof of general associativity ProofOfGeneralAssociativity 2014-05-11 15:12:33 2014-05-11 15:12:33 pahio (2872) pahio (2872) 10 pahio (2872) Proof msc 20-00 PowerSet Cardinality