proof of general associativity

We suppose that “” is an associative binary operationMathworldPlanetmath of the set S.

Let  f1:S2S  be the mapping


We define recursively the mapping


such that

fn(a1,,an):=r=1n-1fr(a1,,ar)fn-r(ar+1,,an) (1)

for  n=2, 3, 4,

For example,


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

|f1(a1)|= 1,|f2(a1,a2)|= 1,|f3(a1,a2,a3)|= 1.

We shall show by inductionMathworldPlanetmath that

|fn(a1,a2,,an)|= 1 (2)

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

We make the induction hypothesis, that (2) is true for all  n<k.

Now let z and z be arbitrary elements of  fk(a1,,ak).  Then there exist the elements x,y,x,y of S and the integersr,s{1,,k-1}  such that


If specially  r=s,  then, by the induction hypothesis,  x=x  and  y=y,  whence  z=xy=xy=z.  If on the contrary,  rs,  e.g.  r<s,  then the induction hypothesis guarantees the existence of an element v of S such that




Since “” is associative, we have


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