By induction on $n$ . It is harmless to let $n$ = $m + 1$ , since $0$ lacks proper subsets. Suppose that $f : n \to n$ is injective.

To begin, note that $m \in f[n]$ . Otherwise, $f[m] \subseteq m$ , so that by the induction hypothesis, $f[m] = m$ . Then $f[n] = f[m]$ , since $f[n] \subseteq m$ . Therefore, for some $k < m$ , $f(k) = f(m)$ .

Let $g : f[n] \to f[n]$ transpose $m$ and $f(m)$ . Then $h \vert_m : m \to m$ is injective, where $h = g \circ f$ . By the induction hypothesis, $h \vert_m[m] = m$ . Therefore:

	.