Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

How do I prove that it is injective?

share|cite|improve this question
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$? – m_t_ Sep 9 '11 at 10:36
up vote 11 down vote accepted

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.

share|cite|improve this answer
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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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