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.

Is it true that for each Set $M$ a given injective function $f: M \rightarrow M$ is surjective, too?

Can someone explain why it is true or not and give an example?

share|improve this question
10  
If the set $M$ is finite, then yes. –  Mariano Suárez-Alvarez Oct 21 '11 at 21:19
    
I could swear that this question was asked 10 times before. I guess it's easier to write a one line answer than to find the duplicates... –  Asaf Karagila Oct 21 '11 at 21:24
    
@Asaf In that case, it would also make sense to include this as a frequently asked question. :) –  Srivatsan Oct 21 '11 at 21:28
1  
@Srivatsan: Yes, it would very much make sense to do that. In fact it might be worth a while to add a few other elementary set theory questions there. –  Asaf Karagila Oct 21 '11 at 21:29

3 Answers 3

up vote 5 down vote accepted

This statement is true if $M$ is a finite set, and false if $M$ is infinite.

In fact, one definition of an infinite set is that a set $M$ is infinite iff there exists a bijection $g : M \to N$ where $N$ is a proper subset of $M$. Given such a function $g$, the function $f : M \to M$ defined by $f(x) = g(x)$ for all $x \in M$ is injective, but not surjective. Henning's answer illustrates this with an example when $M = \mathbb N$. To put that example in the context of my answer, let $E \subseteq \mathbb N$ be the set of positive even numbers, and consider the bijection $g: \mathbb N \to E$ given by $g(x) = 2x$ for all $x \in \mathbb N$.

On the other hand, if $M$ is finite and $f: M \to M$, then it is true that $f$ is injective iff it is surjective. Let $m = |M| < \infty$. Suppose $f$ is not surjective. Then $f(M)$ is a strict subset of $M$, and hence $|f(M)| < m$. Now, think of $x \in M$ as pigeons, and throw the pigeon $x$ in the hole $f(x)$ (also a member of $M$). Since the number of pigeons strictly exceeds the number of holes (both these numbers are finite), it follows from the pigeonhole principle that some two pigeons go into the same hole. That is, there exist distinct $x_1, x_2 \in M$ such that $f(x_1) = f(x_2)$, which shows that $f$ is not injective. (See if you can prove the other direction: if $f$ is surjective, then it is injective.)

Note that the pigeonhole principle itself needs a proof and that proof is a little elaborate (relying on the definition of a finite set, for instance). I ignore such complications in this answer.

share|improve this answer
    
I didn't get why this is true for finite sets. What is the difference here between finite and infinite sets? –  sschaef Oct 21 '11 at 21:44
    
@Antoras: For starters, infinite sets are not finite. They allow more room to move things around. –  Asaf Karagila Oct 21 '11 at 22:02
    
Yes, that is true. But why do they make the injective function f not surjective? –  sschaef Oct 21 '11 at 22:07
2  
@Antoras: It does not mean that every injective function is not surjective. It just means that some injective functions are not surjective, and some surjective functions are not injective either. –  Asaf Karagila Oct 21 '11 at 22:27
1  
@Antoras: It appears that you believe a function is some universal object, but it is not. Different functions can have different domains (the set on which they operate). In fact the categorical approach defines a function along with its domain and codomain. This is exactly the point. If the function has a finite domain then injective is the same as surjective. If it has an infinite domain then this is no longer true. –  Asaf Karagila Oct 22 '11 at 8:42

No. Consider $f:\mathbb N\to\mathbb N$ defined by $f(n)=2n$. It is injective but not surjective.

share|improve this answer
    
Or $f(n)=n+1$. Peano says that $f$ is not surjective. –  lhf Oct 21 '11 at 22:47
    
Right. I wrote that first, but then changed it to $2n$ because I didn't want the confusion of choosing between saying "1 is not in the image" and "0 is not in the image". Then I forgot to add "the odd numbers are not in the image" to the answer anyway, so I might as well have left it at the successor function. –  Henning Makholm Oct 21 '11 at 22:53

For finite sets, consider the two point set $\{a,b\}$ . If you have an injective function, $f(a)\neq f(b)$, so one has to be $a$ and one has to be $b$, so the function is surjective. The same idea works for sets of any finite size. If the size is $n$ and it is injective, then $n$ distinct elements are in the range, which is all of $M$, so it is surjective.

share|improve this answer

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.