Surjections from $\mathbb{N}_m$

• (C)
  Let a non-empty set $\mathbb{B}$ be given.
  Suppose that there exists, for some $m \in \mathbb{N}$ a surjection $p: \mathbb{N}_m \rightarrow \mathbb{B}$.
  Then either $p$ is a bijection, or $m > 1$ and there exists a surjection $q: \mathbb{N}_{m - 1} \rightarrow \mathbb{B}$.

Proof:
If $m = 1$, then $\mathbb{N}_1 = \{1\}$ and any map from $\mathbb{N}_1$ to any non-empty set has range a single element, so if the map is surjective, $\mathbb{B}$ must be a one-element set, in which case the map $p$ is also injective so $p$ is bijective and we are done.
So henceforth we may assume that $m > 1$ and that $p$ is not a bijection, since otherwise we are done.
Since $p$ is not a bijection, $p$ is not injective, so there exist $r$ and $s$ in $\mathbb{N}_m$ such that $r\ne s$ and yet $p(r) = p(s) = b$, say, where $b \in \mathbb{B}$.
Define the map $g: \mathbb{N}_m \rightarrow \mathbb{B}$ by the composition $g = p\circ S_{r,m}$.
Then since $S_{r, m}$ is a bijection, the map $g$, being a composition of surjections, is a surjection.
Note that we have $S_{r, m}(r) = m$ and $S_{r, m}(s) = t$, say, where $t \in \mathbb{N}_m$ and $t \ne m$, since $r\ne s$ and $S_{r, m}$ is injective.
So $t < m$ and $t \in \mathbb{N}_{m-1}$.
Now the map $g$ obeys $g(m) = p(S_{r, m}(m)) = p(r) = b$ and $g(t) = p(S_{r, m}(t)) = p(s) = b$.
Define $q$ as the restriction to $\mathbb{N}_{m - 1}$ of the map $g$.
Then since $t < m$ and $g(t) = g(m) = b$ and $g(t) \in g(\mathbb{N}_{m - 1})$, we see that:

$$\hspace{-30pt} \mathbb{B}= g(\mathbb{N}_m) = g(\mathbb{N}_{m - 1}... ...athbb{N}_{m - 1})\cup \{g(t)\} = g(\mathbb{N}_{m - 1}) = q(\mathbb{N}_{m - 1}).$$

So $q: \mathbb{N}_{m - 1} \rightarrow \mathbb{B}$ is a surjection and we are done.

Then, by POW, we have the corollary:

• (D)
  Let a non-empty set $\mathbb{B}$ be given.
  Suppose that there exists, for some $m \in \mathbb{N}$ a surjection $p: \mathbb{N}_m \rightarrow \mathbb{B}$.
  Then either $p$ is a bijection, or $m > 1$ and there exists a positive integer $k < m$ and a bijection $q: \mathbb{N}_{k} \rightarrow \mathbb{B}$.

Proof:
Here $k \ge 1$ is the least integer such that an surjection $q: \mathbb{N}_k\rightarrow \mathbb{B}$ exists.
Then $q$ is bijective, since otherwise we could lower the integer $m$, by (C).