Proof of An Injective Self-Map of a Finite Set is a Bijection

Claim 1. We argue by induction on $n$, using Principle of Induction for the Natural Numbers, on the statement $P(n)$: every injective map $u:[n]\to[n]$ is a bijection.

For $P(1)$: by claim 2 of Basic Properties of Initial Segments of the Natural Numbers we have $[1]=\{1\}$, so $u(1)=1$, and $1$ is the one and only element of $[1]$ whose image under $u$ is $1$. Thus $u$ is a bijection by Bijection of Sets.

Assume $P(n)$ and let $u:[S(n)]\to[S(n)]$ be injective. Put $a=u(S(n))$ and define $\theta:[S(n)]\to[S(n)]$ by

$$\theta(a)=S(n),\qquad \theta(S(n))=a,\qquad \theta(k)=k\ \text{ for }k\in[S(n)]\text{ with }k\ne a\text{ and }k\ne S(n);$$

if $a=S(n)$ this prescription is consistent and gives $\theta(k)=k$ for every $k$. In all cases $\theta(\theta(k))=k$ for every $k\in[S(n)]$, so $\theta$ is a two-sided inverse of itself and claim 3 of Inverse of a Bijection shows that $\theta$ is a bijection from $[S(n)]$ onto $[S(n)]$.

Let $v:[S(n)]\to[S(n)]$ be the map $v(k)=\theta(u(k))$. It is injective: $\theta$ is injective by claim 1 of Injectivity, Composition, and Restriction of Bijections, so $v(j)=v(k)$ gives $u(j)=u(k)$ and hence $j=k$. Moreover $v(S(n))=\theta(a)=S(n)$.

Let $k\in[n]$. If $v(k)=S(n)$ then $v(k)=v(S(n))$, so $k=S(n)$ by injectivity, contradicting $S(n)\notin[n]$ from claim 3 of Basic Properties of Initial Segments of the Natural Numbers. Since $[S(n)]=[n]\cup\{S(n)\}$ by that same claim, it follows that $v(k)\in[n]$. Hence the restriction $v'$ of $v$ to $[n]$ is a map from $[n]$ to $[n]$, and it is injective because $v$ is. By $P(n)$ it is a bijection.

We check that $v$ is a bijection from $[S(n)]$ onto $[S(n)]$. Let $y\in[S(n)]$. If $y=S(n)$, then $v(S(n))=y$, while no $k\in[n]$ satisfies $v(k)=y$, since $v(k)\in[n]$ and $S(n)\notin[n]$; so $S(n)$ is the unique preimage. If $y\in[n]$, then there is exactly one $k\in[n]$ with $v'(k)=y$, and $v(S(n))=S(n)\ne y$, again because $S(n)\notin[n]$; so that $k$ is the unique preimage. Thus $v$ is a bijection.

Finally, $\theta(v(k))=\theta(\theta(u(k)))=u(k)$ for every $k$, so $u$ is the composition of the bijections $v$ and $\theta$ and is therefore a bijection by claim 2 of Injectivity, Composition, and Restriction of Bijections. This proves $P(S(n))$. That a bijection from $[n]$ to $[n]$ is a permutation of $[n]$ is Permutation of the Set $\{1,\dots,r\}$.

Claim 2. Let $X$ be nonempty and finite, so that $X$ has $n$ elements for some $n\in\mathbb{N}$, and let $\varphi:[n]\to X$ be a bijection, as provided by Number of Elements of a Set. By claims 1 and 2 of Inverse of a Bijection the inverse $\varphi^{-1}:X\to[n]$ exists and is a bijection. Let $w:[n]\to[n]$ be the map $w(k)=\varphi^{-1}\bigl(u(\varphi(k))\bigr)$. If $w(j)=w(k)$, then applying $\varphi$ and using $\varphi\circ\varphi^{-1}=\mathrm{id}$ gives $u(\varphi(j))=u(\varphi(k))$, hence $\varphi(j)=\varphi(k)$ since $u$ is injective, hence $j=k$ since $\varphi$ is injective by claim 1 of Injectivity, Composition, and Restriction of Bijections. So $w$ is injective, and claim 1 shows that $w$ is a bijection.

For every $x\in X$ we have $\varphi(w(\varphi^{-1}(x)))=u(x)$, using $\varphi\circ\varphi^{-1}=\mathrm{id}$ twice. Thus $u$ is the composition of the three bijections $\varphi^{-1}$, $w$ and $\varphi$, and two applications of claim 2 of Injectivity, Composition, and Restriction of Bijections show that $u$ is a bijection from $X$ onto $X$.