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