# Injective functions also surjective?

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?

#### Solutions Collecting From Web of "Injective functions also surjective?"

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.

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

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.