# 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. Aug 14, 2019 at 14:33
• Thanks @HenningMakholm Aug 14, 2019 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. Aug 14, 2019 at 15:10
• Very concise, thank you. Aug 14, 2019 at 15:19
• @Henning Makholm - You're right. I was seeking an intuitive proof that would steer the OP to a figorous one. Aug 14, 2019 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. Aug 14, 2019 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. Aug 24, 2019 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).
– user524154
Aug 24, 2019 at 21:50

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$$