Take the 2-minute tour ×
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.

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|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$? –  mt_ Sep 9 '11 at 10:36
add comment

2 Answers

up vote 6 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|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
1  
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
add comment
  1. suppose that $f$ is 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 function then every $x$ in $S$ must work as abscissa in the relation $f$ hence we must have there is $x_1 \ne x_2$ implies that $f(x_1)=f(x_2)$ which gives a contradiction there for f must be onto
share|improve this answer
add comment

Your Answer

 
discard

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.