(related to Proposition: More Characterizations of Finite Sets)

By hypothesis, $X,Y$ are finite sets equal cardinalities $|X|=|Y| < \infty.$

- Let $f:X\to Y$ be surjective.
- Assume $f$ wasn't injective. Then there would exist some $v_1,v_2\in X$ with $x_1\neq x_1$ but $f(x_1)=f(x_2).$
- Since, in this case, at least $2$ elements $x_1,x_2$ of $X$ were mapped to a single element $f(x_1)=f(x_2)$ and because $X,Y$ are finite, this would mean that there is an $y\in Y$ such that no $x\in X$ are left with $f(x)=y$. But this would contradict the surjectivity of $f$.
- Therefore, $f$ is injective.

- Let $f:X\to Y$ be injective.
- This means that $f(x_1)\neq f(x_2)$ if $x_1\neq x_2.$
- It follows that $f$ maps different elements of $X$ on different elements of $Y.$
- Since $X$ has the same number of elements as $Y$, every element of $x\in X$ will be mapped to a distinct value $y\in Y.$
- It follows that $f$ is surjective. Now, $X,Y$ are finite sets with unequal cardinalities.

- By hypothesis, the cardinalities $|Y|=n$ and $|X|=m$ and $n < m.$
- For the sake of transparency in the notation, we write $Y_n$ for $Y$ with $|Y|=n$ and $X_m$ for $X$ with $|X|=m.$
- We will prove this lemma by induction of $m.$
- Base case: $m=1$.
- Assume for the sake of contradiction that there is an injective function $f:X_1\to Y_n$ and $n > 1.$
- This assumption means that there are some $a,b\in X_1$ with $a\neq b$ and $f(a)=f(b).$
- But this is impossible, since $X_1$ has only one element.
- Therefore, there is no injective function, and the lemma is true.

- Induction step: $m\to m+1$
- Assume, there is no injective function $f:X_m\to Y_n$ for some $m < n.$
- By contraposition, this is equivalent to saying that if $n > m$ for some $m\in\mathbb N$ then there
*is*an injective function $f:X_m\to Y_n.$ - Holding $n$ fixed and using this injective function $f$, we will now construct another injective function $f':X_{m+1}\to Y_n.$ as follows: * Without loss of generality, let $X_m=\{x_1,\ldots,x_m\}$ and $X_{m+1}:=X_m\cup \{x_{m+1}\}.$ * Since $n > m,$ and $f$ is injective, there is an element $y\in Y_n$ with $y\neq f(x_k)$ for all $k=1,\ldots,m.$ * Define the function $f':X_{m+1}\to Y_n$ by $$f'(x_k):=\begin{cases}f(x_k)\in Y_n&\text{if }k\le m\\y&\text{if }k=m+1.\end{cases}$$ * By construction $f'$ is injective.

- Another proof:
- From $(3)$ it follows that if $f:X\to Y$ is injective than $|X|\le |Y|$.
- Vice versa, if $g:Y\to X$ is injective than $|Y| \le |X|$
- By the Schroeder-Bernstein Theorem, it follows $|X|=|Y|.$
- By the definition of equipotent sets, this is the case if an only if $f$ and $g$ are bijective.∎

**Knauer Ulrich**: "Diskrete Strukturen - kurz gefasst", Spektrum Akademischer Verlag, 2001