Exercise 6.1

Question

\begin{enumerate}[label=(\alph*)]
\item Make a list of all the injective maps
\begin{gather*}
f : \left\{1,2,3ight\} 	o \left\{1,2,3,4ight\} \,.
\end{gather*}
Show that none is bijective.
(This constitutes a \emph{direct} proof that a set $A$ of cardinality three does not have cardinality four.)
\item How many injective maps
\begin{gather*}
f : \left\{1, \ldots, 8ight\} 	o \left\{1, \ldots, 10ight\}
\end{gather*}
are there?
(You can see why one would not wish to try to prove \emph{directly} that there is no bijective correspondence between these sets.)
\end{enumerate}

Dan Whitman · Accepted Answer

\begin{lemma}\label{lem:finset:inj}
The number of injective mappings (i.e. the cardinality of the set of injective functions) from $\left\{1, \ldots, might\}$ to $\left\{1, \ldots, night\}$, where $m \leq n$, is equal to the number of $m$-permutations of $n$, which is
\begin{gather*}
\frac{n!}{(n-m)!} \,.
\end{gather*}
\end{lemma}
\begin{proof}
We fix $n$ and show this for all $m \leq n$ by induction.
First, for $m=1$, the domain of the mappings is simply $\left\{1ight\}$ so that we need only choose a single element to which to map $1$.
Since there are $n$ elements to choose from (since the range is $\left\{1, \ldots, night\}$) there are clearly
\begin{gather*}
n = \frac{n!}{(n-1)!} = \frac{n!}{(n-m)!}
\end{gather*}
mappings, all of which are trivially injective.

Now suppose that $m < n$ and that there are $n! / (n-m)!$ injective mappings from $\left\{1, \ldots, might\}$ to $\left\{1, \ldots, night\}$.
Consider any such mapping $\seqfin{f}{m}$.
Since this mapping is injective, each $f_i$ is unique so that it uses $m$ of the $n$ available numbers in $\left\{1, \ldots, night\}$.
Thus there are $n-m$ numbers to choose from to which to set $f_{m+1}$ so that the mapping $\seqfin{f}{m+1}$ is still injective.
Hence for each injective mapping $\seqfin{f}{m}$ there are $n-m$ injective mappings from $\left\{1, \ldots, m+1ight\}$ to $\left\{1, \ldots, night\}$.
Since there are $n!/(n-m)!$ such mappings by the induction hypothesis, the total number of mappings from $\left\{1, \ldots, m+1ight\}$ to $\left\{1, \ldots, night\}$ will be
\begin{gather*}
\frac{n!}{(n-m)!}(n-m) = \frac{n!}{(n-m-1)!} = \frac{n!}{[n-(m+1)]!} \,,
\end{gather*}
which completes the induction.
\end{proof}

extbf{Main Problem.}

(a) Here we have $n=4$ and $m=3$ in Lemma~ef{lem:finset:inj} so that we expect $4!/(4-3)! = 4!/1! = 4! = 24$ injective mappings.
Since the domain of each $f$ is a section of the positive integers, these maps can be written simply as 3-tuples.
They are enumerated below:
\begin{multicols}{4}
\begin{enumerate}[itemsep=0cm]
\item $(1, 2, 3)$
\item $(1, 2, 4)$
\item $(1, 3, 2)$
\item $(1, 3, 4)$
\item $(1, 4, 2)$
\item $(1, 4, 3)$
\item $(2, 1, 3)$
\item $(2, 1, 4)$
\item $(2, 3, 1)$
\item $(2, 3, 4)$
\item $(2, 4, 1)$
\item $(2, 4, 3)$
\item $(3, 1, 2)$
\item $(3, 1, 4)$
\item $(3, 2, 1)$
\item $(3, 2, 4)$
\item $(3, 4, 1)$
\item $(3, 4, 2)$
\item $(4, 1, 2)$
\item $(4, 1, 3)$
\item $(4, 2, 1)$
\item $(4, 2, 3)$
\item $(4, 3, 1)$
\item $(4, 3, 2)$
\end{enumerate}
\end{multicols}
Note that they are all injective since no number is used more than once in each tuple.
Also, none are surjective since it is easily verified that there is always an element of $\left\{1,2,3,4ight\}$ that is not in each tuple.
Thus none are a bijection since they are not surjective.

(b) Here we have $n = 10$ and $m = 8$ in Lemma~ef{lem:finset:inj} so that there are $10! / (10-8)! = 10! / 2! = 1814400$ injective mappings.
That is nearly two million!
Certainly, direct proof would be unfeasible by hand but could be done by computer fairly easily.
\end{solution}

Exercise 6.1

Answers

Comments

Exercise 6.1

Answers

Comments

Add answer