functions - If there is an injection $f: X to Y$ with $m=n$ then $f$ is a bijection.

The Statement of the Problem:

Let $X,Y$ be finite sets with $ \lvert X \rvert = m $ and $ \lvert Y \rvert = n $. Prove the following statement by induction on $ m \ge 1$:

If there is an injection $f: X \to Y$ with $m=n$ then $f$ is a bijection. $(*)$

My Thoughts:

I believe I'm supposed to invoke the Schröder-Bernstein theorem here, which I keep thinking I understand... until I have to actually use it in a proof. Furthermore, I always manage to screw up inductive proofs. Also, in simply thinking about the statement, I'm wondering if it is, in fact, even true. For example, is a function from an empty set to an empty set injective? I know that it's not surjective, so it wouldn't be bijective; I'm not sure about injectivity, though.

Anyway, here we have the base case, $P(1)$, in which $m=n=1$ which is obviously true. Now, even with the base case here, I understand why it's true, but a formal proof of it is still difficult for me. Would it, perhaps, be useful to use contraposition to make this claim?

And, as for the inductive step, I'm not really sure what to do. I know that I am to assume the the hypothesis is true, namely $(*)$, and then show that it's true for $m+1$. But, in order to do that, is the statement of $(*)$ simply the following:

If there is an injection $f: X \to Y$ with $m+1=n+1$ then $f$ is a bijection?

This is where I feel like I have a fundamental misunderstanding of inductive proofs. So, if anyone could give me some guidance here, I'd appreciate it. Thanks!

Answer

For $m=n=1$, the statement is true because every mapping from a one-element set to a one-element set is a bijection, because there exists exactly one mapping.

More precisely, let $X=\{x\}$ and let $Y=\{y\}$. Then, the set $M(X,Y)$ of all mappings from $X$ to $Y$ has exactly one element, $f$, defined as $f:x\mapsto y$. Therefore, every injective element of $M(X,Y)$ is also bijective.

Now, onto the inductive step. What you know (assume) in induction is the following:

For any pair of sets $X,Y$ for which $|X|=|Y|=m$, we know that if
$f:X\mapsto Y$ is injective, then it is surjective.

What you need to show is:

For any pair of sets $X,Y$ for which $|X|=|Y|=m+1$, we know that if
$f:X\mapsto Y$ is injective, then it is surjective.

To do that, you need to take an arbitrary pair of sets $X,Y$, satisfying your condition (i.e., you start your argument with: "Now, let $X,Y$ be such sets that $|X|=|Y|=m+1$")

Then, you take an arbitrary function $f:X\mapsto Y$ and prove that if it is injective, it is bijective (i.e., you say "and let $f:X\mapsto Y$ be an injective function. Then, your proof here, and thus, $f$ is bijective")

To prove that $f$ is bijective, I advise you to take a look at some arbitrary value $x\in X$ and look at the function $f$, restricted to the set $X\setminus\{x\}$.