The pigeonhole principle on $\mathbb{N}$

Transpositions. For a set $X$ and $a, b \in X$ define $\tau^{X}_{a,b} : X \to X$ by $\tau^{X}_{a,b}(a) = b$, $\tau^{X}_{a,b}(b) = a$, and $\tau^{X}_{a,b}(x) = x$ for $x \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^{X}_{a,b} \circ \tau^{X}_{a,b} = \mathrm{id}_X$, whence $\tau^{X}_{a,b}$ 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 \ne b$ the elements of $X \setminus \{a\}$ are $b$, sent to $a$, together with the $x \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 = \varnothing$, so a function $f : \sigma(0) \to 0$ would have to supply a value $f(0) \in \varnothing$, and $\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^{\sigma(n)}_{a,n}$, which is legitimate since $a$ and $n$ both lie in $\sigma(n)$. Then $f' = \tau \circ f : \sigma(\sigma(n)) \to \sigma(n)$ is a composite of an injection with a bijection, hence injective, and $f'(\sigma(n)) = \tau(a) = n$.

Every $k \in \sigma(n)$ satisfies $k \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'(k)$ is defined; and $k \ne \sigma(n)$, so injectivity of $f'$ gives $f'(k) \ne f'(\sigma(n)) = n$. Since $f'(k) \in \sigma(n) = n \cup \{n\}$, this forces $f'(k) \in n$. Hence the restriction of $f'$ 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} \not\approx n$.

Claim 5. Let $A \subseteq n$ with $n \approx A$, and suppose $A \ne n$. Then $n \ne 0$, since the only subset of $0 = \varnothing$ is $\varnothing = 0$ itself, so $n = \sigma(m)$ for some $m \in \mathbb{N}$; moreover $m \in \sigma(m) = n$ and $m \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 \ne n$, and let $h : n \to A$ be a bijection; since $j \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^{n}_{j,m}$ 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 \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.