Proof of Uniqueness of the Number of Elements

We use the numbered claims of Basic Properties of Initial Segments of the Natural Numbers, of Arithmetic of Addition on the Natural Numbers and of Injectivity, Composition, and Restriction of Bijections. Every appeal to induction means an application of Principle of Induction for the Natural Numbers, so that it suffices to verify a property at $1$ and to pass from $n$ to $S(n)$, where $S$ is the successor map of Natural Numbers.

Step 1: reduction to initial segments. Suppose $f:[m]\to X$ and $g:[n]\to X$ are bijections. Define $h:[m]\to[n]$ as follows: for $i\in[m]$ the element $f(i)$ lies in $X$, so there is exactly one $k\in[n]$ with $g(k)=f(i)$; set $h(i)=k$. By construction, for $i\in[m]$ and $k\in[n]$ we have $h(i)=k$ if and only if $f(i)=g(k)$. Fix $k\in[n]$. Since $f$ is a bijection, there is exactly one $i\in[m]$ with $f(i)=g(k)$, i.e. exactly one $i\in[m]$ with $h(i)=k$. Hence $h$ is a bijection from $[m]$ onto $[n]$.

It therefore suffices to prove the following statement for all $n\in\mathbb{N}$:

$P(n)$: for every $m\in\mathbb{N}$, if there exists a bijection $h:[m]\to[n]$, then $m=n$.

Step 2: base case $P(1)$. By claim 2 of Basic Properties of Initial Segments of the Natural Numbers we have $[1]=\{1\}$. Let $h:[m]\to[1]$ be a bijection and suppose $m\ne 1$. By claim 6 of Arithmetic of Addition on the Natural Numbers we may write $m=S(p)$ with $p\in\mathbb{N}$. By claim 3 of Basic Properties of Initial Segments of the Natural Numbers, $[m]=[p]\cup\{m\}$ with $m\notin[p]$, and by claim 1 of that lemma $1\in[p]$; hence $1$ and $m$ are distinct elements of $[m]$. But $h(1)$ and $h(m)$ both lie in $[1]=\{1\}$, so $h(1)=h(m)$, contradicting injectivity of $h$ (claim 1 of Injectivity, Composition, and Restriction of Bijections). Hence $m=1$.

Step 3: inductive step. Assume $P(n)$, let $m\in\mathbb{N}$, and let $h:[m]\to[S(n)]$ be a bijection. By claims 1 and 3 of Basic Properties of Initial Segments of the Natural Numbers we have $n\in[n]$, $S(n)\notin[n]$, $S(n)\in[S(n)]$ and

In particular $n\ne S(n)$, so $[S(n)]$ contains the two distinct elements $n$ and $S(n)$.

First, $m\ne 1$: otherwise $[m]=\{1\}$ by claim 2 of Basic Properties of Initial Segments of the Natural Numbers, and surjectivity of $h$ would give $h(1)=n$ and $h(1)=S(n)$, forcing $n=S(n)$, a contradiction. Hence $m=S(p)$ for some $p\in\mathbb{N}$ by claim 6 of Arithmetic of Addition on the Natural Numbers, and claim 3 of Basic Properties of Initial Segments of the Natural Numbers gives

Since $h$ is a bijection, there is exactly one $c\in[m]$ with $h(c)=S(n)$. Let $\tau:[m]\to[m]$ interchange $c$ and $m$ and fix every other element of $[m]$; explicitly $\tau(c)=m$, $\tau(m)=c$, and $\tau(i)=i$ otherwise (if $c=m$ this is the identity map). Since $\tau(\tau(i))=i$ for every $i\in[m]$, each $y\in[m]$ has $\tau(y)$ as a preimage, and it is the only one because $\tau(i)=\tau(i')$ implies $i=\tau(\tau(i))=\tau(\tau(i'))=i'$. Hence $\tau$ is a bijection, and $h'=h\circ\tau$ is a bijection from $[m]$ onto $[S(n)]$ by claim 2 of Injectivity, Composition, and Restriction of Bijections. It satisfies $h'(m)=h(c)=S(n)$.

We claim that the restriction of $h'$ to $[p]$ is a bijection onto $[n]$. First, let $i\in[p]$. Then $i\ne m$ because $m\notin[p]$, so $h'(i)\ne h'(m)=S(n)$ by claim 1 of Injectivity, Composition, and Restriction of Bijections; since $h'(i)\in[S(n)]=[n]\cup\{S(n)\}$, we conclude $h'(i)\in[n]$. Second, let $y\in[n]$. Since $h'$ is a bijection onto $[S(n)]$ and $y\in[n]\subseteq[S(n)]$, there is exactly one $i\in[m]$ with $h'(i)=y$. This $i$ satisfies $i\ne m$, because $h'(m)=S(n)$ while $y\in[n]$ and $S(n)\notin[n]$. Hence $i\in[m]\setminus\{m\}=[p]$, and it is the unique element of $[p]$ mapped to $y$. This proves the claim.

Applying $P(n)$ to this bijection from $[p]$ onto $[n]$ gives $p=n$, hence $m=S(p)=S(n)$. This proves $P(S(n))$.

By induction $P(n)$ holds for every $n\in\mathbb{N}$, and with Step 1 this completes the proof.