# Prove that $\exists k \in \mathbb{N}$ such that $k\leq m$. And such that exists Bijective function $g:A \rightarrow \mathbb{N}^{<k}$.

$k \in \mathbb{N}$

$\mathbb{N}^{< k} = \{ j\in \mathbb{N} |j<k \}$

Let A be a set,Assume $m \in \mathbb{N}$ such that exists Injective function $f:A\rightarrow \mathbb{N}^{<m}$

$\textbf{Prove}$ that $\exists k \in \mathbb{N}$ such that $k\leq m$. And such that exists Bijective function $g:A \rightarrow \mathbb{N}^{<k}$.

My attempt: I tried to define $B\subseteq \mathbb{N}$ In this way - $B = \{ n\in \mathbb{N}|\: \: \exists\: Injective \: function\: \: h:A\rightarrow \mathbb{N}^{<n} \}$.

I dont know how to continue,Thanks.

• The claim does not hold in general. For example, there is an injection from $\left\{ 0 \right\}$ to $\mathbb{N}^{<m}$ for all $m$, but for any $k$ you don't have a bijection. – Matias Heikkilä May 9 '16 at 20:54
• I think for $k=1$ you have, for example. – Noam May 9 '16 at 20:58
• Of course, sorry. For some reason I read "$\mathbb{N}$" as "$\mathbb{Z}$". – Matias Heikkilä May 9 '16 at 21:04

Let $A$ be such that there is an injection $f: A \to \mathbb{N}^{< m}$. Then $A$ is a finite set (why?). Take $k = \#A$.
• Can you explain yourself ? What do you mean when you write $k = \# A$ ? – Noam May 9 '16 at 21:20
• By $\# A$ I mean the (finite) cardinality of $A$. – Matias Heikkilä May 9 '16 at 21:21
• Ahh ok, I used to write $|A|$. But,I still dont understand how this helps you. – Noam May 9 '16 at 21:22
• Well if $A$ is finite, you can just label the elements as $a_0, \dots a_n$ and define $f(a_i) =i$. – Matias Heikkilä May 9 '16 at 21:24