calculus - Induction Proof on the existence of Injections and Bijections from Natural numbers into arbitrary sets

I found a Note in my old Calc I script. Where it was stated that: for any set

$M\neq \emptyset$ and ${ \mathbb{N} }_{ m }=\left\{ n\quad \epsilon \quad \mathbb{N} :\quad n\le m,\quad m\quad \epsilon \quad \mathbb{N} \right\}$ ( N denoting the natural numbers).

Their either exists: a fixed $m\ \epsilon \ \mathbb{N}$ and a bijective Map $\varphi :{ \mathbb{N} }_{ m }\rightarrow M\\$

or an injective Map $\varphi :{ \mathbb{N} }_{ m }\rightarrow M\\$

for all $m\ \epsilon \ \mathbb{N}$

I tired to proof this as refreshing exercise. It is fairly easy if you use counatbility arguments but i tried another way to proof it by induction where i got completley stuck. My quetions is now if it is even possible to proof it by induction and if yes how?

Answer

Well, clearly there if $a \in M$ then $f:\{1\} \to M$ via $f(1) = a$ is injective.

Suppose $k$. If there is a $m \le k$ so that there is a bijection from $N_m \to M$ we are done and there is nothing left to prove.

Assume there is not but there is an injection $\varphi: N_k \to M$. Since $\varphi$ is not a bijection but is an injection, $\varphi$ is not surjective. So there is an $a \in M$ so that $a \ne \varphi(j)$ for any $j \in N_k$.

Let $\varphi': N_{k+1}\to M$ via $\varphi'(k+1) = a$ and for $j \le k$ $\varphi'(j) = \varphi(j)$. $\varphi'$ is clearly an injection[$*$]. And it might be a bijection (in which case we won't need to do any further induction) but it is definitely an injection. (And if it isn't a bijection we can do another induction).

==== after edit ===

In a current edit there is a condition I have not addressed. That if there is a $m$ so that there is a bijection $\varphi:N_m \to M$ that $m$ is fixed, or in other words there is precisely one such $m$ that will have bijections from $N_m$ to $M$ and no other natural number will.

Claim: If a bijection exists between $N_m$ and $M$ then no bijection exist between $N_k$ and $M$ for any other $k$.

Pf: Suppose $k < n$ and bijections $\varphi_n:N_n\to M$ and $\varphi_k:N_k\to M$ exist.

Then $f = \varphi_n\circ\varphi_k^{-1}\circ\varphi_n(i):N_n\to M$ is a bijection as it is a composition of bijections.

But then for $j > k$ we must have an $f(i) = \varphi_n(j)$or $\varphi_n(\varphi_k^{-1}(varphi_n(i))= \varphi_n(j)$. But $\varphi_n$ is a bijection, so $\varphi_k^{-1}(\varphi_n(i)) = j$ which would mean $j \in N_k$ which is a contradiction.

......

[$*$] If $\varphi'(b) = \varphi'(c)$ either $\varphi'(c) = a$ or $\varphi'(c) \ne a$.

If $\varphi'(c) = a$ then $c \not \le k$ so $c = b = k+1$.

If $\varphi'(c) \ne a$ then $c \ne k+1$ and $b \ne k+1$ so $\varphi'(c) = \varphi(c)$ and $\varphi(b) = \varphi(b)$, and, as $\varphi$ is an injection $b = c$.

Either way $b = c$ and $\varphi'$ is an injection.