5
$\begingroup$

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?

  • 12
    If the set $M$ is *finite*, then yes.2011-10-21
  • 0
    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...2011-10-21
  • 1
    @Asaf In that case, it would also make sense to include this as a frequently asked question. :)2011-10-21
  • 3
    @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.2011-10-21

3 Answers 3

0

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.

9

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

  • 0
    Or $f(n)=n+1$. [Peano](http://en.wikipedia.org/wiki/Peano_axioms) says that $f$ is not surjective.2011-10-21
  • 0
    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.2011-10-21
9

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.

  • 0
    I didn't get why this is true for finite sets. What is the difference here between finite and infinite sets?2011-10-21
  • 0
    @Antoras: For starters, infinite sets are not finite. They allow more room to move things around.2011-10-21
  • 0
    Yes, that is true. But why do they make the injective function f not surjective?2011-10-21
  • 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.2011-10-21
  • 0
    @AsafKaragila: Can you give a small example with a function which is bijective if a set is finite and not if it is infinite? I don't want a proof, but some deeper explanation. I read somewhere something about $e^x$ which must not be surjective in infinite sets. Maybe it is possible to build a example with that function?2011-10-21
  • 0
    @Antoras, what you ask makes no sense. You cannot have a single function that is both be $A\to A$ and $B\to B$ if $A$ and $B$ are different sets. There is no function that is both a function from a finite set to itself and a function from an infinite set to itself.2011-10-21
  • 0
    @Antoras: I'm not sure I follow. However if you want then you can take the function $f(n)=n$ for $n<10$ and $f(n)=n+1$ for $n\ge 10$. Then on the set $\{0,\ldots,10\}$ it is a bijection, but on $\mathbb N$ it is not.2011-10-21
  • 0
    @AsafKaragila: Why not? Because if $f(10)$ is called, a 11 is returned and therefore it is not possible to get a 10 back?2011-10-21
  • 0
    @Antoras Well, I think you're saying that $10$ does not have a preimage (that is, there exists no $n$ such that $f(n)=10$), and hence $f$ is not surjective. That is correct.2011-10-21
  • 0
    @Antoras: If $n<10$ then $f(n)=n<10$ and if $n\ge 10$ then $f(n)=n+1>n\ge 10$ therefore $f(n)\neq 10$ for all $n\in\mathbb N$.2011-10-21
  • 0
    @AsafKaragila: Ok, this is logical. But I don't yet understand what this has to do with finite and infinite sets. If there is a function $f(n)=n+1$, there is no $0$ returned, either with a finite set $\{0,...,10\}$ nor with a infinite set $\mathbb N$.2011-10-22
  • 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.2011-10-22
  • 0
    I don't understand the point with function domains. I think it is better when I accept this and maybe in some months I will understand it.2011-10-22
  • 0
    @Antoras You seem to have a confusion about the definition of functions (which is perfectly ok, by the way). You can perhaps ask a separate question to address that. It would be difficult for people to explain using just the comment thread.2011-10-22
  • 0
    The problem is that I do not understand what I not understand. This make it difficult to ask a specific question. But you are right, if I find a question and can't answer it I will ask it.2011-10-23