Question regarding cardinality and pigeonhole principle Suppose $A$ and $B$ are finite sets and $f:A\rightarrow B$. Prove that if $|A|>|B|$, then $f$ is not one-to-one.
Scratch work:
Since the goal is in negation, I try to prove it by contradiction and assume that $f$ is one-to-one. Since $A$ has more elements than $B$, it can't be the case that $f$ is one-to-one because some $a\in A$ has to share images with other. But other than the false assumption $f$ is one-to-one, I have no other clue to proceed with the question. What technique should I apply? Please give hints and guidance. Thanks in advance.
 A: Let $f(A)$ be the set of images. Then $f(A)\subseteq B$ so $|f(A)|\le |B|$.
If $f$ is one-to-one then $|f(A)|=|A|$.
A: Select a subset $A' \subset A$ such that $|A'| = |B|$. Let $A' = \{a_1, a_2, \dots, a_n\}$ and $B = \{b_1, b_2, \dots, b_n\}$. There is a trivial bijection (one-to-one and onto) $f:A' \to B$.
Now assume $g$ is a one-to-one mapping $A \to B$ which when restricted to $A'$ is $f$.
There exists $a_{n+1} \in (A - A')$ which is mapped to some element $b_i \in B$. However, for every element $b_i \in B$, there already exists $a_i \in A'$ such that $f(a_i) = b_i$. Hence $g(a_{n+1}) = g(a_i) = f(a_i) = b_i$ and $g$ is not one-to-one.
A: We write $A\preceq B$ if there exists an injection $A\to B$.
Theorem: Let $A, B$ be finite sets. Then, $A \preceq B, \iff \#A \le \#B$.
Proof: ($\Rightarrow$)
Let $\varphi(n)$ be the statement "B is a set of size $\,n\,$ and $A \preceq B \rightarrow \#A \le n$."
$$S = \left\{\,n\in \omega:\varphi(n)\, \right\}.$$
For $n = 0\,$, B is the empty set, and the only injection is to itself. So, clearly $0 \in S.$ Assume $n \in S $ we need to show that $n^{+} \in S$.
Suppose  $ \#B =n^{+}$ and $\,f: A \rightarrow B\,$ is an injective map. We choose an element $b\in B$. If $\,b \in f[A] $ then $ f(a) = b\,$ for a unique $a\in A$. Let $A^{*} = A-\left\{a \right\}$ and $\,B^{*} = B -\left\{b \right\}$. We define the function $g: A^{*} \rightarrow B^{*}$ to be the restriction of $f$ in $A^{*}$, i.e., $\,g = f\restriction_{A^{*}}$. Then, $g\,$ is a one-to-one function and by our inductive hypothesis $\#A^{*} \le \#B^{*}.$ But since $\#A^{*} = \#A-1\,$ and $\#B^{*} = n$. Then, $\#A-1 \le \ n \rightarrow \#A \le n^{+} .$
If $b \notin f[A]$. Let $B^{*} = B-\left\{b \right\}$. Where $f: A \rightarrow B^{*}$ is a one-to-one function, and by inductive hypothesis $\#A \le \#B^{*}.$ But since $\#B^{*} = \#B-1 = n$. Then, $\#A \le n^{+} $. 
Hence $n^{+} \in S$ which close the induction.
($\Leftarrow$) We need to show that $\#A \le \#B$ implies the existence of an injective map $f: A\rightarrow B$.
For $\#B = 0\,$, that means $\#A = 0$. And clearly $f: \emptyset \rightarrow \emptyset $ is an injection. Suppose our claims holds for n, we need to show that also holds for $n^{+}$.  For $\# B = n^{+}$, as $n^{+} \not = 0\,$ the set is nonempty, so  there exist an element $b \in B$. Let $B^{*} = B -\left\{b \right\}$, then we have that $\#B^{*} = n$. 
If $\#A \le \#B^{*}$ by our inductive hypothesis, there exist a injective map $g : A \rightarrow B^{*}$. Let $i_{ B^{*} \rightarrow B}$ be the inclusion map, i.e., $i_{ B^{*} \rightarrow B}: B^{*} \rightarrow B : j \mapsto j\,$, which is an injection. Therefore, the composition $\, i_{ B^{*} \rightarrow B} \circ g: A \rightarrow B\,$, is an injection as desired. 
If $\, \#A \not\le \#B^{*}$ but $ \#A \le \#B $, i.e., $ \#A = n^{+}$. We set $A^{*} = A-\left\{a \right\}$. Then $\#A^{*}\le \#B^{*}$ and by the inductive hypothesis there exist an injective map $h': A^{*} \rightarrow B^{*}$. We can define the function $h: A \rightarrow B$, by adding the ordered pair $ \langle a, b \rangle $ to the function $h'$. That is, $h: = h' \cup \left\{\,  \langle a, b \rangle  \, \right\}$ (as $ \langle a, b \rangle $ is a genuine extra element, the map $h$ is one-to-one).  $\;\;\ \Box$
Since $\#A> \# B$ then by the above theorem cannot exists an injective map $A$ to $B$. 
