Compositions & Transpositions of permutations

Question

Consider the set of all permutations $S_n$.

Fix an element $\tau\in S_n$.

Then the sets $\{\sigma\circ\tau\mid \sigma\in S_n\}= \{\tau \circ\sigma\mid \sigma\in S_n\}$ have exactly $n!$ elements.

I am confused what the above theorem stands for? How can $\{\sigma\circ\tau \mid \sigma\in S_n\}=\{\tau \circ\sigma \mid \sigma \in S_n\} = S_n$?

(This has been stated as an equivalence statement of the above theorem)? What is the logic behind? Does the term element above refer to a complete permutation? See link.

Answer 1

If $\sigma \in S_n$ then $\sigma \circ \tau^{-1} \in S_n$, and $\tau^{-1} \circ \sigma \in S_n$ so multiplying by $\sigma$ on either side is a surjective map $S_n \rightarrow S_n$.

Answer 2

The first thing you should note is that if $\tau, \sigma \in S_n$, then $\tau \circ \sigma \in S_n$. This means that if you have two permutations, then their product is also a permutation of the same permutation group.

You also know that $S_n$ has exactly $n!$ elements.

Now imagine I give you a set $A$ where all of its elements are permutations from $S_n$. Mathematically speaking this means that $A \subset S_n$.

Now let's think about how many elements $A$ can have.

If $A = S_n$, then $A$ contains all permutations from $S_n$. So how many elements does $A$ have? Exactly $n!$, since there are exactly $n!$ permutations in $S_n$.

What if $A$ contains exactly $n!$ permutations from $S_n$? Then $A$ must contain all permutations from $S_n$, since there are only $n!$ elements in $S_n$. So $A = S_n$

What I have shown is that any set $A$ that only contains permutations from $S_n$ has exactly $n!$ elements if and only if $A = S_n$.

The key point here is that $A$ only has permutations from $S_n$ as its elements. And if it has $n!$ permutations (that is, all permutations) as its elements, then it must be equal to $S_n$ (and vice versa).

This is essentially all the proposition says.

The set $\left\{\sigma \circ \tau : \sigma \in S_n\right\}$ is a subset of $S_n$, that is it only contains permutations from $S_n$. Why? See my first statement at the top of this post.

So $\left\{\sigma \circ \tau : \sigma \in S_n\right\} = S_n$ is equivalent to saying that $\left\{\sigma \circ \tau : \sigma \in S_n\right\}$ has exactly $n!$ elements.

The same holds for $\left\{\tau \circ \sigma: \sigma \in S_n\right\} = S_n$