Permutations

Proposition 7.2.5   Let $A$ and $B$ be two finite sets such that $\vert E\vert=\vert F\vert$ and let $f$ be a mapping from $A$ to $B$. Then the following properties are equivalent:

(i)

$f$ is an injection;

(ii)

$f$ is a surjection;

(iii)

$f$ is a bijection.

Proof. It suffices to prove that in this case injection and surjection are equivalent.

1. Suppose that $f$ is an injection. Then the set $f(A)$ is finite and $\vert f(A)\vert=\vert A\vert$. It follows that $f(A)$ is a subset of $B$ such that $\vert f(A)\vert=\vert B\vert$, hence $f(A)=B$, i.e. $f$ is a surjection.
2. Suppose that $f$ is a surjection, i.e. $f(A)=B$. Thus $\vert A\vert=\vert f(A)\vert$ and $f$ must be an injection.

$\qedsymbol$

Corollary 7.2.6   The set $\mathbb{N}$ of natural numbers is not finite.

Proof. The mapping $n \mapsto 2n$ from $\mathbb{N}$ to $\mathbb{N}$ is an injection (prove it!), but not a surjection. The result is a consequence of Proposition 2.5. $\qedsymbol$

Non finite sets are called infinite. We will see later that there is still a need for further classification among infinite sets, namely into countable (v.i. section ) and non countables sets. If $A$ and $B$ are infinite then there exist injections which are not bijections and vice versa. For instance if $A = B = \mathbb{N}$, define

$$f(n) = \begin{cases}1 & n = 1 \\ n-1 & \text{otherwise}\end{cases} \qquad g(n) = n+1.$$

Then $f$ is surjective but not injective and $g$ is injective but not surjective.

Corollary 7.2.7   If $E$ is a non empty finite set such that $\vert E\vert=n$, then the number of permutations of $E$ is equal to $n!$.

Proof. As $E$ is finite, the permutations are exactly the injections from $E$ to itself. Thus, the number of permutations of $E$ is equal to $A_n^n=n!/(n-n)! = n!$. $\qedsymbol$

Example 7.2.8       

1. If we wish to place 8 books on a shelf, there are $8!$ possible orderings. .
2. We wish to place 5 chemistry books and 8 physics books on the same shelf, letting together books of the same discipline. Among the chemistry books, there are $5!$ orderings and among the physics books, there are $8!$ orderings. Axs there are two choices for the respective places of the discipline (physics on the left and chemistry on the right, or physics on the right and chemistry on the left), the number of different orderings is here $5! \cdot 8! \cdot 2 =9676800$.