The pigeonhole principle on $\mathbb{N}$

Transpositions. For a set $X$ and $a,b\in X$ define ${\tau }_{a,b}^X:X\to X$ by ${\tau }_{a,b}^X(a)=b$, ${\tau }_{a,b}^X(b)=a$, and ${\tau }_{a,b}^X(x)=x$ for $x\mathrm{\notin }\{a,b\}$; the clauses agree where they overlap (if $a=b$ all three read $a\mapsto a$, so the map is the identity), so this is a well defined function, and ${\tau }_{a,b}^X\circ {\tau }_{a,b}^X={\mathrm{i}\mathrm{d}}_X$, whence ${\tau }_{a,b}^X$ is a bijection of $X$ onto itself. It carries $X\setminus \{a\}$ onto $X\setminus \{b\}$: when $a=b$ this is the identity statement, and when $a\mathrm{\ne }b$ the elements of $X\setminus \{a\}$ are $b$, sent to $a$, together with the $x\mathrm{\notin }\{a,b\}$, each fixed, so the image is $\{a\}\cup (X\setminus \{a,b\})=X\setminus \{b\}$.

Base case of claim 1. Here $\sigma (0)=0\cup \{0\}=\{0\}$ and $0=\mathrm{\varnothing }$, so a function $f:\sigma (0)\to 0$ would have to supply a value $f(0)\in \mathrm{\varnothing }$, and $\mathrm{\varnothing }$ has no elements; hence there is no function $\sigma (0)\to 0$ at all, injective or not.

Inductive step, hypotheses. Fix $n\in \mathbb{N}$, assume there is no injection $\sigma (n)\to n$, and suppose towards a contradiction that some $f:\sigma (\sigma (n))\to \sigma (n)$ is injective. Note $\sigma (\sigma (n))=\sigma (n)\cup \{\sigma (n)\}$, so $\sigma (n)\subseteq \sigma (\sigma (n))$ and $\sigma (n)\in \sigma (\sigma (n))$; note also $n\in \sigma (n)$.

Normalising $f$ at the top point. Put $a=f(\sigma (n))$, an element of $\sigma (n)$ because $\sigma (n)$ is the codomain of $f$, and let $\tau ={\tau }_{a,n}^{\sigma (n)}$, which is legitimate since $a$ and $n$ both lie in $\sigma (n)$. Then $f^{\mathrm{\prime }}=\tau \circ f:\sigma (\sigma (n))\to \sigma (n)$ is a composite of an injection with a bijection, hence injective, and $f^{\mathrm{\prime }}(\sigma (n))=\tau (a)=n$.

Every $k\in \sigma (n)$ satisfies $k\mathrm{\ne }\sigma (n)$: were $k=\sigma (n)$ we would have $\sigma (n)\in \sigma (n)$, and no natural number is a member of itself, $\sigma (n)$ included, since $\mathbb{N}$ is closed under $\sigma$.

Let $k\in \sigma (n)$. Then $k\in \sigma (\sigma (n))$, so $f^{\mathrm{\prime }}(k)$ is defined; and $k\mathrm{\ne }\sigma (n)$, so injectivity of $f^{\mathrm{\prime }}$ gives $f^{\mathrm{\prime }}(k)\mathrm{\ne }{f}^{\mathrm{\prime }}(\sigma (n))=n$. Since $f^{\mathrm{\prime }}(k)\in \sigma (n)=n\cup \{n\}$, this forces $f^{\mathrm{\prime }}(k)\in n$. Hence the restriction of $f^{\mathrm{\prime }}$ to $\sigma (n)$ takes all its values in $n$ and is an injection $\sigma (n)\to n$.

Claim 1. The injection produced in step 3.1 contradicts the assumption made in step 1.3, so no injection $\sigma (\sigma (n))\to \sigma (n)$ exists. Since $n$ was arbitrary, this is exactly the induction step for the property $P(n)$ that there is no injection $\sigma (n)\to n$, and step 1.2 is $P(0)$; so $P(n)$ holds for every $n\in \mathbb{N}$.

Claim 2. Let $m<n$. Then $m\in n$, and $m\le n$ gives $m\subseteq n$, so $\sigma (m)=m\cup \{m\}\subseteq n$. If some $g:n\to m$ were injective, its restriction to $\sigma (m)$ would be an injection $\sigma (m)\to m$, which step 4.1 forbids. Hence there is no injection $n\to m$.

Claim 4. Since $\mathbb{N}$ is closed under $\sigma$ we have $\sigma (n)\in \mathbb{N}$, and $\mathbb{N}$ is a transitive set, so $\sigma (n)\subseteq \mathbb{N}$. If some $F:\mathbb{N}\to n$ were a bijection, it would in particular be an injection, and its restriction to $\sigma (n)$ would be an injection $\sigma (n)\to n$, which step 4.1 forbids. Hence $\mathbb{N}\approx ̸n$.

Claim 5. Let $A\subseteq n$ with $n\approx A$, and suppose $A\mathrm{\ne }n$. Then $n\mathrm{\ne }0$, since the only subset of $0=\mathrm{\varnothing }$ is $\mathrm{\varnothing }=0$ itself, so $n=\sigma (m)$ for some $m\in \mathbb{N}$; moreover $m\in \sigma (m)=n$ and $m\mathrm{\notin }m$, so $n\setminus \{m\}=(m\cup \{m\})\setminus \{m\}=m$. Choose $j\in n\setminus A$, possible because $A\subseteq n$ and $A\mathrm{\ne }n$, and let $h:n\to A$ be a bijection; since $j\mathrm{\notin }A$ we have $A\subseteq n\setminus \{j\}$, so $h$ read as a map into $n\setminus \{j\}$ is an injection $n\to n\setminus \{j\}$. The transposition ${\tau }_{j,m}^n$ is a bijection of $n$ carrying $n\setminus \{j\}$ onto $n\setminus \{m\}=m$, so its composite with $h$ is an injection $n\to m$, that is an injection $\sigma (m)\to m$, which step 4.1 forbids. Hence $A=n$.

Claim 3. Let $n,m\in \mathbb{N}$ with $n\approx m$, and suppose $n\mathrm{\ne }m$. By trichotomy either $m<n$ or $n<m$. If $m<n$, a bijection $n\to m$ is in particular an injection $n\to m$, which step 5.1 forbids. If $n<m$, a bijection $n\to m$ has an inverse bijection $m\to n$, which is in particular an injection $m\to n$, and step 5.1 forbids that too, with the roles of $m$ and $n$ interchanged. Hence $n=m$.

Claims 1, 2, 3, 4 and 5 are established in steps 4.1, 5.1, 6.1, 5.2 and 5.3 respectively.