Proof of associativity under composition of functions of symmetric group $S_n$

Question

Do I have to prove that the composition of two functions $f, g \in S_n$ is also $f \circ g \in S_n$ first? If I do how could I proceed?

Answer 1

I think that it might be easier to first show the composition is associative and then prove that if $f,g\in S_n$ then $f\circ g\in S_n$.

In general, given three functions $f: A\rightarrow B,g: B\rightarrow C$ and $h: C\rightarrow D$ we can prove that $h\circ(g\circ f)= (h\circ g) \circ f$.

I am going to assume we already know that the composition of functions is a function.

The domain of $h\circ (g\circ f)$ is the domain of $g\circ f$ which is $A$. The codomain of $h\circ (g\circ f)$ is the codomain of $h$ which is $D$.

The domain of $(h\circ g)\circ f$ is the domain of $f$ which is $A$. The codomain of $(h\circ g)\circ f$ is the codomain of $h\circ g$ which is $D$.

So we have seen both functions have the same domain and codomain.

Finally let us take $a\in A$ and show both functions map $a$ to the same element:

$(h\circ (g\circ f))(a)=h((g\circ f)a)=h(g(f(a))$

$((h\circ g)\circ f)(a)=(h\circ g)(f(a))=h(g(f(a))$

---

Now let us show that if $f,g\in S_n$ then $f\circ g\in S_n$.

Clearly the domain and codomain of $f\circ g$ are appropriate, to show $f\circ g$ is bijective we can just notice that $g^{-1}f^{-1}$ is a proper inverse (we need associativity to do so).