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

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<s$ , 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
Canonical name	ProofOfGeneralAssociativity
Date of creation	2014-05-11 15:12:33
Last modified on	2014-05-11 15:12:33
Owner	pahio (2872)
Last modified by	pahio (2872)
Numerical id	10
Author	pahio (2872)
Entry type	Proof
Classification	msc 20-00
Related topic	PowerSet
Related topic	Cardinality