10
$\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$
2
  • 4
    $\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$ Aug 14, 2019 at 14:33
  • $\begingroup$ Thanks @HenningMakholm $\endgroup$ Aug 14, 2019 at 15:02

3 Answers 3

6
$\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$
3
  • $\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$ Aug 14, 2019 at 15:10
  • 1
    $\begingroup$ Very concise, thank you. $\endgroup$ Aug 14, 2019 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$ Aug 14, 2019 at 15:57
5
$\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$
3
  • $\begingroup$ That's pretty nice, thanks. $\endgroup$ Aug 14, 2019 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, 2019 at 13:10
  • 1
    $\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$
    – user524154
    Aug 24, 2019 at 21:50
0
$\begingroup$

The OP was attempting a proof to

$\quad$ (*) "show that a surjection implies an injection using induction"

Now user524154 worked on the other half and stated that (*) could be handled in exactly the same way. Well, there are some subtleties when using that technique.

Proposition: For all $n \ge 0$ and sets $A$ and $B$,
$\quad \quad \quad \quad \quad$ if $n = |A| = |B|$ and $f: A \to B$ is a surjection then $f$ is an injection.
Proof by induction:
For the base case $n = 0$ there is exactly one function, the empty graph mapping $A = \emptyset$ to $B = \emptyset$, and it is vacuously a bijection.
Step case: Assume the proposition is true for $n = k$. If $k = 0$ then the proposition holds for $n = k + 1 = 1$, since the (unique) function mapping one singleton set $A$ to another singleton set $B$ must be a bijection.
So we assume that $n = k + 1 \ge 2$ so that $B$ has at least two elements. Assume to get a contradiction that there is an element $b \in B$ such that

$\quad |f^{-1}(b)| \ge 2$

Select an element $a \in f^{-1}(b)$ and let $F = \bigcup f^{-1}(b) \setminus \{a\}$ so that the preimage is partitioned,

$\quad f^{-1}(b) = \{a\} \bigcup F $

Select an element $\hat b \in B$ such that $\hat b \ne b$;
note that there exists an $\hat a \in A$ not belonging to $f^{-1}(b)$ satisfying $\hat a \in f^{-1}(\hat b)$.

Consider the binary relation $\rho$ equal to

$\quad \text{Graph}(f) \setminus \bigr(f^{-1}(b) \times \{b\}\bigr) \; \bigcup \; F \times \{\hat b \}$

Checking, we verify that $\rho$ is actually a function $g$,

$\quad g: A \setminus \{a\} \to B \setminus \{b\}$

that is a surjective mapping between two sets with cardinality $k$ with at least two distinct elements in $g^{-1}(\hat b)$.

But this contradicts the inductive hypothesis. $\quad \blacksquare$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .