# Problem 7 from Topics of Algebra I.N.Herstein

If $S$ is a nonempty set then $A(S)$ is the set of all one-to-one mappings of $S$ onto itself.

If the set $S$ has $n$ elements, prove that $A(S)$ has $n!$ elements.

Proof: First of all we'll prove the following useful lemma.

Lemma: Let $\sigma: S\to S$, $|S|=n$ and $\sigma$ is one-to-one mapping then $\sigma$ is onto.

Proof of lemma: Suppose $\sigma$ is not onto then $\exists y\in S$ such that for any $x\in S$ we have $\sigma (x)\neq y$. Hence $|\sigma(S)|\leqslant n-1$ but $|S|=n$. Thus some two elements from $S$ have the identical images so $\sigma$ is not one-to-one. Contradiction.

Let's find the number of injective mappings from $S$ to $S$, since $|A(S)|=$ the number of injective functions. Let $S=\{x_1, x_2, \dots, x_n\}$ and $\sigma: S\to S$. In order $\sigma$ to be injective it should correspond $\{x_1, x_2, \dots, x_n\}$ to some of its permutations. There $n!$ permutations. So, we have proven that $|A(S)|=n!$

Is it correct?

## 1 Answer

Yes, it is the case. To be more precise, we can say: there is $n$ possibility to $\sigma(x_1)$, and $n-1$ for $\sigma(x_2)$ and so on.