Associativity makes brackets redundant I would like to prove the statement in the title: Associativity makes brackets redundant for 'things' being composed.
I didn't make precise what I'm talking about because I guess there is some kind of general approach. I saw this property being used in a book about category theory, and then again in my Abstract algebra lecture, but couldn't find a proof for it. I guess the question is kind of Bourbaki-ish so everybody just uses the statement without proof.
I will stay informal for generality, but what I want is for example this:
$$i\circ h\circ g\circ f=i\circ(h\circ g)\circ f $$
where $f,g,h,i$ are elements of a semigroup, or arrows in a category, etc.
So far my approach for small numbers of 'things being composed' was showing that any one way of bracketing can be transformed into any other way, but for more than three things this already becomes tedious.
So my question is: How can I prove this for $n\in\mathbb{N}$ things-being-composed? I assume it works by induction, but that's just a guess.
 A: There's an exercise in the first chapter of Spivak's Calculus that guides you through this proof. It's several consecutive inductions. Here's the outline: 


*

*Define $a_1+...+a_n=a_1+(a_2+...+(a_{n-1}+a_n)...)$. Show that $(a_1+...+a_{n-1})+a_n=a_1+...+a_n$. 

*Prove that $(a_1+...+a_k)+(a_{k+1}+...+a_n)=a_1+...+a_n$.

*Prove that an arbitrarily bracketed sum is $a_1+...+a_n$ by splitting it into two smaller sum.

A: Here is the germ of the idea used in an inductive proof:
Suppose we want to show that any $4$-fold composition is equal to:
$a \circ (b \circ (c \circ d))$.
If our $4$-fold composition is $a\circ(b\circ c)\circ d))$, we can apply associativity to show that $(b \circ c)\circ d) = b \circ (c\circ d)$, and we are done. This is one way the "inductive step" is used (we passed from $n= 4$ to $n = 3$ easily).
So we may as well assume for starters our composition is: $(a \circ\dots\ $ Our immediate goal is to strip away the left parenthesis on $a$, so as to reduce it to the case we solved above.
Continuing, we either have $(a \circ (b\dots\ $, or $(a \circ b)\dots$. The second case can only be  $(a \circ b) \circ (c \circ d)$. Regarding $c \circ d$ as a single entity (let's call it $k$ for now), regular associativity gives:
$(a\circ b)\circ k = a\circ (b\circ k)$, that is:
$(a \circ b)\circ (c\circ d) = a\circ(b \circ (c \circ d))$, which concludes the examination of that case.
The first case, likewise, can only be $(a \circ (b \circ c))\circ d$. In this case, letting $k = b \circ c$, we have:
$(a \circ k)\circ d = a \circ (k \circ d)$, that is: $(a \circ (b \circ c))\circ d = a\circ ((b\circ c) \circ d)$, which we dispatched at the very outset.
It might happen, though, that our $4$-fold composition begins $((a \circ\dots$.
Again, our goal is to reduce the left parentheses around $a$ by one, leading to cases we have already solved.
In this final case, it must be that our $4$-fold composition is $((a\circ b)\circ c)\circ d$. Here, we take $ k = a \circ b$, and regular associativity gives us:
$(k \circ c) \circ d = k \circ (c \circ d)$, that is:
$((a \circ b)\circ c)\circ d) = (a \circ b)\circ (c \circ d)$. Since we've handled the latter composition above, mission accomplished.
So, the general idea is, starting with the "innermost" composition (or the "left-most innermost", if there is more than one), we can always move the outermost left parenthesis to the right. When the left-most term has no left parenthesis around it, we apply our induction hypothesis, and bam!
