# Proof

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

### Ad $(1)$

• 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.

### $(2)$

• 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.

### $(3)$ By Induction

• 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.

### $(4)$

• 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.

Github: ### References

#### Bibliography

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