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.


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$.


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$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.