12
$\begingroup$

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

How do I prove that it is injective?

$\endgroup$
  • $\begingroup$ Have you tried counting elements yet? $\endgroup$ – Sebastian Sep 9 '11 at 10:32
  • $\begingroup$ 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$? $\endgroup$ – Matthew Towers Sep 9 '11 at 10:36
23
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why is the function g injective? $\endgroup$ – Mohan Sep 9 '11 at 11:06
  • $\begingroup$ @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)$. $\endgroup$ – Asaf Karagila Sep 9 '11 at 11:46
  • 5
    $\begingroup$ 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$. $\endgroup$ – pash Jul 26 '13 at 18:10
  • $\begingroup$ 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. $\endgroup$ – anir May 26 '18 at 16:12
  • $\begingroup$ 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? $\endgroup$ – anir May 26 '18 at 17:39
2
$\begingroup$

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.

$\endgroup$

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.