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

  • $\begingroup$ Thanks for your answer. Can you explain how that is a contradiction? $\endgroup$ – Willam M Sep 28 '14 at 2:21
  • $\begingroup$ Are you asking about the second to last sentence? $\endgroup$ – C. Williamson Sep 28 '14 at 2:22
  • $\begingroup$ 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. $\endgroup$ – Willam M Sep 28 '14 at 2:58
  • $\begingroup$ 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. $\endgroup$ – Willam M Sep 28 '14 at 3:00
  • $\begingroup$ 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. $\endgroup$ – C. Williamson Sep 28 '14 at 5:22

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.