3
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Henning Makholm Aug 14 at 14:33
  • $\begingroup$ Thanks @HenningMakholm $\endgroup$ – JacobCheverie Aug 14 at 15:02
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Aug 14 at 15:10
  • $\begingroup$ Very concise, thank you. $\endgroup$ – JacobCheverie Aug 14 at 15:19
  • $\begingroup$ @Henning Makholm - You're right. I was seeking an intuitive proof that would steer the OP to a figorous one. $\endgroup$ – Chris Leary Aug 14 at 15:57
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That's pretty nice, thanks. $\endgroup$ – JacobCheverie Aug 14 at 18:11
  • $\begingroup$ @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. $\endgroup$ – Philipp Aug 24 at 13:10
  • $\begingroup$ 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). $\endgroup$ – palmpo Aug 24 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.