Finite Sets, Equal Cardinality, Injective $\iff$ Surjective.

This proof seems odd to me. I have come to the conclusion that I will use induction. I would like to see a smoother way or just some improvements on my technique.

Let $$f:A\rightarrow B$$ be a function between two finite sets of equal cardinality. Show that $$f$$ is surjective if and only if it is injective.

To start, I will show that a surjection implies an injection using induction. I will dismiss the cases that both sets are empty or contain one element as being trivial (essentially vacuously true).

Assume $$|A| \geq 2$$, $$|B| \geq 2$$, $$|A| = n = |B|$$, and $$f:A \rightarrow B$$ is a surjection. For the base case, let $$n = 2$$.

There are two elements in both $$A$$ and $$B$$. Due to surjection, every element $$b \in B$$ must be mapped to, through $$f$$, by at least one element $$a \in A$$. If each of the two elements in $$B$$ were mapped to by the same element in $$A$$, the definition of function would be violated. Therefore, they are mapped to by unique elements in $$A$$. Thus, for $$f(p), f(q) \in B$$, if $$f(p) = f(q)$$, it must be true that $$p = q$$ so $$f$$ is injective.

Now assume that the surjection implies an injection for $$n \geq 2$$. We must show this to be true for $$|A| = n + 1 = |B|$$. Since it is true for $$|A| = n = |B|$$, the $$n + 1$$ case represents the addition of one new element to both $$A$$ and $$B$$. The new element in $$B$$ cannot be mapped to any other element in $$A$$ except for the new one. If mapped to by an old one, the definition of function would be violated. It must be mapped to by something since $$f$$ is surjective, hence it must be the new element. Finally, the new element in $$A$$ cannot be mapped to an old element in $$B$$ because it is unique and the previous $$B$$ was shown to be injective.

$$\blacksquare$$

This is a very wordy and awkward proof in my opinion. I have been out of proofs for a long time. I would like to see one that is more clear or seek validation if there isn't. I know that I have only completed half of the proof and have yet to go the other way.

• Instead of saying "dismiss the cases that both sets are empty or contain one element as being trivial" you should use $n=0$ as the base case for your induction. – Henning Makholm Aug 14 at 14:33
• Thanks @HenningMakholm – JacobCheverie Aug 14 at 15:02

If the sets have cardinality $$n$$ and $$f$$ is injective, then the image of $$f$$ must be an $$n$$ element subset of $$B$$ and so equal to $$B.$$ If $$f$$ is surjective, then the preimage of each element of $$B$$ contains at least one element, and the preimages are disjoint. So the union of the preimages of the elements of $$B$$ has at least $$n$$ elements. Since $$A$$ has only $$n$$ elements, each preimage of an element of $$B$$ can contain only one element of $$A.$$ so that $$f$$ is injective.

• I think this is, to some degree, begging the question -- the theorem to be proved here is part of the things you'd need to prove to know that "an $n$-element subset" is a robust concept where we know that our intuitive understanding will map to rigorous set-theoretic proofs. – Henning Makholm Aug 14 at 15:10
• Very concise, thank you. – JacobCheverie Aug 14 at 15:19
• @Henning Makholm - You're right. I was seeking an intuitive proof that would steer the OP to a figorous one. – Chris Leary Aug 14 at 15:57

For the statement "$$f$$ injective implies $$f$$ surjective", induct on the cardinality of $$A$$ and $$B$$.

You can check $$n=0$$.

For $$n=k+1$$, let $$f:A\to B$$ be injective. $$A$$ has at least one element $$a$$. Define $$f^-:A\setminus\{a\}\to B\setminus\{f(a)\}$$, gotten by forgetting about $$a$$ and its value $$f(a)$$. $$f^-$$ is injective as restricting injections preserves injectivity (check this if you don't know). Then $$f^-$$ is also surjective by induction hypothesis. Appending back $$a$$ and $$f(a)$$ preserves surjectivity so $$f$$ is surjective.

The other direction is exactly the same; replace injective with surjective everywhere.

• That's pretty nice, thanks. – JacobCheverie Aug 14 at 18:11
• @palmpo, why do you remove $a$ and it's image and then make the induction hypothesis on $f^-$? Is it also possible to do it the other way around? Let the induction hypothesis be $f: A \to B$ is also surjective. Then I add another element $a$ and an image of $a$ which are not equal to any of the elements in $A$ or $B$. So the new function which maps between $A \cup a$ and $B \cup f(a)$ is still injective and surjective. – Philipp Aug 24 at 13:10
• the induction hypothesis is for cardinality $k$, not $k+1$. And your argument doesn't work; the resulting function is not equal to the original function $f$ (having cardinality $k+1$), which is what we want to prove injective (and surj). – palmpo Aug 24 at 21:50