# Surjectivity implies injectivity

Let S be a finite set.Let F be a surjective function from S to S.

How do I prove that it is injective?

• Have you tried counting elements yet? – Sebastian Sep 9 '11 at 10:32
• Suppose $x \neq y \in S$ and that $f(x) =f(y)$. Let $|S|=n$. How many distinct elements can lie in the image of $f$? – Matthew Towers Sep 9 '11 at 10:36

Let $S$ be a finite set, and $f : S \to S$ a function. Then the following are equivalent:

• $f$ is injective.
• $f$ is surjective.
• $f$ is bijective.

This is really just a counting argument. First, suppose $f$ is injective. If $S$ has $n$ elements, by our assumption, this means the image of $f$ has at least $n$ elements. But the image of $f$ is contained in $S$, so it has at most $n$ elements; so the image of $f$ contains exactly $n$ elements and is therefore the whole of $S$, i.e. $f$ is surjective.

Next, suppose $f$ is surjective. So, for each $y$ in $S$, there is an $x$ in $S$ such that $y = f(x)$; we choose one such $x$ for each $y$ and define a function $g : S \to S$ so that $g(y) = x$. By construction, $f(g(y)) = y$, so $g$ must be injective, and hence, must be surjective by the above argument. So $g$ is a bijection, and $f$ is a left inverse for $g$. But a left inverse for a bijection is also a right inverse, so this implies $f$ is a bijection, and a fortiori an injection.

Notice that the very first part of the argument fails when $S$ is not finite. For example, let us consider the function $f : \mathbb{N} \to \mathbb{N}$ defined by $f(x) = x + 1$. This function is certainly injective but is not surjective. Similarly, the function $g : \mathbb{N} \to \mathbb{N}$ defined by $f(0) = 0$ and $f(x + 1) = x$ is surjective, but not injective.

• Why is the function g injective? – Mohan Sep 9 '11 at 11:06
• @user774025: Because we send $y$ to its $x$ such that $f(x)=y$. Since $f$ is a function there can only be one element as $f(x)$. – Asaf Karagila Sep 9 '11 at 11:46
• Though technically correct, the claim that "the image of [an injective] $f$ has at least $n$ elements" is odd and misleading. It follows from the definition of a function that the image of any function has at most $n$ elements when its domain has $n$ elements. So proving the first part really just amounts to noticing that injectivity implies the image of $f$ has exactly $n$ elements, i.e., it coincides with $S$. – pash Jul 26 '13 at 18:10
• So these statements are equivalent only when the function is from finite set to the "same" "finite" set, that is when $f:S\rightarrow S$ for finite set $S$? or any two finite sets with same size will do? That is will these statements be equivalent for $f:S_1\rightarrow S_2$ where both $S_1$ and $S_2$ are finite and of same size? Just want to come up with requirements for surjectivity to imply injectivity. – anir May 26 '18 at 16:12
• Just want to know if there is any special reason for saying that the surjectivity and injectivity imply each other when the same set $S$ maps to itself when you say $f:S\rightarrow S$ in the answer. I feel surjectivity and injectivity imply each other for $f:S_1 \rightarrow S_2$ for finite sets $S_1$ and $S_2$ of same size. Right? – anir May 26 '18 at 17:39

Suppose that $f$ is an injective function and not surjective, i.e. there is point $y\in S$ such that there is no point $x\in S$ with $f(x)=y$. Since $f$ is a function, every $x\in S$ must work as abscissa in the relation $f$. Hence we must have some $x_1 \ne x_2$ with $f(x_1)=f(x_2)$, which gives a contradiction. Therefore $f$ must be onto.