Help prove $f:X \rightarrow Y$ is an injection $\Leftrightarrow$ $f:X\rightarrow Y$ is a surjection when $|X|=|Y|$

Question

I need to prove:

Given non-empty finite sets $X$ and $Y$ with $|X| = |Y|,$ a function $X\rightarrow Y$ is an injection if and only if it is a surjection.

The hint given is to use the pigeonhole principle and proof by contradiction.

Here's what I've tried:

1. From the given assumptions, I know that:

   • $|X|=|Y|=n$ for some $n\in \mathbb{Z}^+$
   • There exist bijections $g:\mathbb{N}_n \rightarrow X$ and $h:\mathbb{N}_n \rightarrow Y$

2. So I need to prove:

   $f:X \rightarrow Y$ is an injection $\Leftrightarrow$ $f:X\rightarrow Y$ is a surjection

3. So, to prove the case $\Rightarrow$:

   Suppose for contradiction,

   $f:X\rightarrow Y \text{ is injective but not surjective} \tag{1}$

   Furthermore, $f:X\rightarrow Y$ is an injection $\Rightarrow |X|\le |Y|$, by the pigeonhole principle.

   This is where I am stuck. I think I need to conclude that $|X|>|Y|$ from $(1)$ so that I can get the contradiction:

   $|X|\le |Y| \text{ and } |X|>|Y|$

4. To prove the case $\Leftarrow$:

   Suppose for contradiction:

   $f:X\rightarrow Y \text{ is surjective but not injective }\tag{ 2}$

   Furthermore,

   $\begin{align} f:X \rightarrow Y \text{ is a surjection } & \Rightarrow & \exists g:Y\rightarrow X \text{ an injection (previous exercise) }\\ & \Rightarrow & |Y| \le |X|, \text{ pigeonhole principle } \end{align}$

I'm also stuck here. Similar to 3, I think I need to conclude $|Y|>|X|$ from $(2)$ to get a contradiction.

Can I please get some help to complete steps 3 and 4?

Answer 1

Before throwing around the pigeonhole principle, just try to reason through a few simple cases. It may help to look at the situation with sets of 4 or 5 elements, and then generalize what you find. Here are some things to think about:

For #3, note that it is impossible to have distinct $a, b \in X$ such that $f(a) = f(b)$. So what does that tell you about the number of elements of $Y$ that are in the image of $f$?

For #4, suppose there are two distinct elements of $X$, say $a$ and $b$, that get mapped to the same $y \in Y$. Then use the surjectivity assumption to count how many elements $X$ must have.

Note that the analogous statement is clearly not true when dealing with sets of the same infinite cardinality (e.g. take $X = \mathbb{N}$ and $Y = \mathbb{N}$, it's easy to come up with a counterexample).

Answer 2

The following is a proof which uses the following version of the pigeonhole principle:

Pigeonhole Principle: For each natural number $ n $ and for each proper subset $ Y $ of $\{m\in\mathbb{N}:m<n\}$, $ Y\nsim n $. (page 134 in Elements of Set Theory by Enderton)

In other words, proper subsets of a finite set $A$ are not bijective to $A$.

Sorry for the picture format; it was the best I could do to transfer one of my .tex files with numerous "newcommands" and such into stackexchange.