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.