# Use induction to prove that a function is not one to one

Suppose that m and n are positive integers with m > n and f is a function from $\{1, 2,\ldots, m\}$ to $\{1, 2, \ldots , n\}$. Use mathematical induction on the variable n to show that f is not one-to-one.

Attempt at a solution:

Predicate statement: $$P(n): ( m > n \wedge f:\{1,2,...,m\} \rightarrow \{1,2,...,n\} ) \implies \exists a, \exists b \ f(a)=f(b) \wedge a \neq b )$$

Let $n=1$, then the smallest subset of images that satisfies $m>1$ is ${1,2}$.

Since $f:{1,2} \rightarrow {1}$, then $f(1)=1$ and $f(2)=1$ where $1\neq2$.

Assume that $( m > k \wedge f:\{1,2,...,m\} \rightarrow \{1,2,...,k\} ) \implies \exists a \exists b ( f(a)=f(b) \wedge a \neq b$) is true.

Then show that $( m>k+1 \wedge f:\{1,2,...,m\} \rightarrow \{1,2,...,k,k+1\} ) \implies \exists a \exists b ( f(a)=f(b) \wedge a\neq b )$ is true.

I do not know how I would show this. I think I can say

1) Let $a \leq k$ and $b \leq k$.

2) Then by our assumption $f(a) = f(b)$ and $a ≠ b$.

What can I do next? I am lost.

Induction doesn't seem like a great proof strategy here. To prove it more simply, you can just say that $f$ is one-to-one implies that $\left|f(\{1,..., m\})\right|\geq m$. (Otherwise, use pigeonhole principle.)

But $f(\{1,...,m\})\subseteq \{1,...,n\}$, so $\left|f(\{1,...,m\})\right|\leq n$. Clearly, this is a contradiction as $m>n$.

If you must use induction, I'd start by fixing $m=n+1$. If you prove the theorem in this case, then the whole theorem follows since if you could find a one-to-one function on a larger domain, then you could restrict your function and reach a contradiction.

So, the problem is now to show that there doesn't exist a 1-1 function from $\{1,...,k+1\}$ to $\{1,...,k\}$ for all $k>1$. This is induction on $k$.

Your base case proves the $k=2$ case. Now, use your induction hypothesis to say that there is no one-to-one function from $\{1,...,k+1\}\rightarrow \{1,...,k\}$. Next, assume that there is such a one-to-one function $f$ from $\{1,...,k+2\}\rightarrow \{1,...,k+1\}$. By restricting $f$, you obtain a contradiction to your inductive hypothesis.

Specifically, if $f$ is on-to-one, then $g:=f|_{\{1,...,k+1\}}$ maps from $\{1,...,k+1\}$ to $\{1,...,k+1\}-\{j\}$, for some $j$ such that $1\leq j\leq k+1$. Then, just by renaming the range of $g$, you obtain a 1-1 function from $\{1,...,k+1\}\rightarrow \{1,...,k\}$.

• Thanks for your answer. Can you explain how that is a contradiction? – Willam M Sep 28 '14 at 2:21
• Are you asking about the second to last sentence? – C. Williamson Sep 28 '14 at 2:22
• Sorry if this sounds dumb, but I am a little confused since you are using different variable names (ie n instead of k). When you mention "use your induction hypothesis", are you talking about the one I typed in the problem? If possible, can you edit your answer to include the symbol k that I used? Sorry, I am just easily confused. – Willam M Sep 28 '14 at 2:58
• Yes. What do you mean "By restricting f, you obtain a contradiction to your inductive hypothesis?" Please explain, this is the first time I am doing a inductive proof on something like this and I have to use induction unfortunately. – Willam M Sep 28 '14 at 3:00
• For induction, you prove the base case (here, when $k=1$). Then assume the theorem holds for all $k<K$ and show that implies that the theorem holds for the next value of $k=K+1$. The inductive hypothesis in the above proof is that there is no one-to-one function $f:[K+1]\rightarrow [K]$. We want to show that this lack of existence of a 1-1 function from [K+1] to [K] implies the lack of existence of a 1-1 function from [K+2] to [K+1]. Use a proof by contradiction. Suppose such a 1-1 function $f$ exists, and use it to construct a function that is 1-1 from [K+1] to [K], a contradiction. – C. Williamson Sep 28 '14 at 5:22