Does associativity justify $(f^{-1}gf)(f^{-1}hf) = f^{-1}gff^{-1}hf$?

Question

I'm self-studying abstract algabra (Herstein) and while working on an easy problem became uneasy with a step in my derivation.

Given the symmetric group $S_n$ whose elements are bijections $f: S \to S$ and the binary operation being function composition, so that we have:

1. Closure under composition $fg \in S_n $
2. Composition is associative (given by the rule): $(fg)h = f (gh)$
3. an identity element $i_S$ exists: $i_sf = f i_s =f$
4. an inverse element $f^-1$ exists for every $f \in S_n$: $f f^{-1} =f^{-1} f = i_S$

Prove that $(f^{-1}gf)(f^{-1}hf) = f^{-1}(gh)f$.

Edited:

What's the justification for the first obvious step, which is:

$(f^{-1}gf)(f^{-1}hf) = f^{-1}gff^{-1}hf$.

(2.) does not directly say this is legal. I'm tempted to claim that (2.) equates all possible orders for performing the composition and that therefore, as a matter of notation, $fgh$ is unambiguous but that argument feels like not quite the thing.

Answer 1

Your question (and the answer you gave) show that you've missed an essential point. In group theory at a very early point one remarks that the associativity axiom can be iterated to show that any two pure product expressions (no inverses) of the same string of variables, but grouped differently by parentheses to show which sequence of multiplications is applied in each case, have equal values. Once this point is accepted, one can allow writing expressions like $abca$ in which parentheses are missing, as any way to insert them would give rise to expressions that can be proved equal. But before this point is made, $abca$ is not a valid group theoretic expression, in contrast to $a(b(ca))$, $a((bc)a)$, $(ab)(ca)$, $(a(bc))a$ and $((ab)c)a$, any of which it could equally well denote.

If one accepts this principle of suppressing parentheses (which also allows them to be inserted in any place), you can write the proof simply as $$\def\inv{^{-1}} (f\inv gf)(f\inv h f)=f\inv gff\inv hf=f\inv gihf = f\inv ghf=f\inv(gh)f. $$ If one does not accept the principle, then the question does not make sense, because both the left and right had sides contain products of three units without parentheses to indicate how they should be multiplied, so that it is unclear what is meant in the first place. One might take the intermediate stance that the associativity axiom directly allows products of three units without parentheses to be used, but not longer ones. With that rule the above proof can be rewritten $$ (f\inv gf)(f\inv h f) =(f\inv g)f(f\inv (h f)) =(f\inv g)(ff\inv(hf)) =f\inv(g(ihf))= f\inv(ghf)=f\inv(gh)f $$ (if you look carefully, there are never products of more than three units long). It would be an interesting combinatorial question to count, if no dropping of parentheses at all is allowed, how many instances of associativity are needed to complete a proof of this identity.

Answer 2

Totally correct, associativity means that the order of the operations doesn't matter (as long as the elements operated on stay in the same order), so you can drop parenteses (no need to tell in which order operations are done, if the result is the same regardless).

But you can go further, as $f f^{-1}$ is the identity: $$ (f^{-1}gf)(f^{-1}hf) = f^{-1}gff^{-1}hf = f^{-1} g h f $$

Answer 3

The gist of your question was how to "break out" an element of a product of three terms. Associativity gives you $$ \begin{eqnarray} (a(bc))d=((ab)c)d=(ab)(cd)=a(b(cd))=a((bc)d) \end{eqnarray} $$ directly. The second equality uses associativity applied to the product of $ab$ (a single element of the group), $c$, and $d$. The third uses it applied to the product of $a$, $b$, and $cd$. In general, you can show that all possible groupings of $N$ terms in a product lead to the same result, so as a matter of notation you can always add and remove parentheses as desired with an associative group.

Answer 4

Suppose we have four elements $a,b,c,d$ of $S_n$ as in your case. Then we can "combine" them in various ways: $$ ((ab)c)d $$ $$ (a(bc))d $$ $$ a((bc)d) $$ $$ a(b(cd)) $$ $$ (ab)(cd) $$ The problem is: are all those combinations equal?

Suppose they are (indeed they are), then we can simply define $abcd$ to mean any one of the preceding coupling, because there is no ambiguity.

If you want to see why it works this way in the general case of $n$ elements, I give you some hints on how to proof the claim.

Let us agree, for definiteness, that $a_1a_2\cdots a_n$ will denote $$a_1(a_2(a_3\cdots (a_{n-2}(a_{n-1}a_n)))\cdots).$$ Thus $a_1a_2a_3$ denotes $a_1(a_2a_3)$, and $a_1a_2a_3a_4$ denotes $a_1(a_2(a_3a_4))$, etc.

(a) Prove that $$(a_1\cdots a_k)a_{k+1}=a_1\cdots a_{k+1}.$$ Hint: Use induction on $k$.

(b) Prove that if $n\geq k$, then $$ (a_1\cdots a_k)(a_{k+1}\cdots a_n)=a_1\cdots a_n.$$ Hint: Use part (a) to give a proof by induction on $k$.

(c) Let $s(a_1,\dots,a_k)$ be some sum formed from $a_1,\dots,a_k$. Show that $$ s(a_1,\dots,a_k)=a_1\cdots a_k.$$ Hint: There must be two sums $s'(a_1,\dots,a_l)$ and $s''(a_{l+1},\dots,a_k)$ such that $$s(a_1,\dots,a_k)=s'(a_1,\dots,a_l)+s''(a_{l+1},\dots,a_k).$$