0
$\begingroup$

$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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Matias Heikkilä May 9 '16 at 20:54
  • $\begingroup$ I think for $k=1$ you have, for example. $\endgroup$ – Noam May 9 '16 at 20:58
  • $\begingroup$ Of course, sorry. For some reason I read "$\mathbb{N}$" as "$\mathbb{Z}$". $\endgroup$ – Matias Heikkilä May 9 '16 at 21:04
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Can you explain yourself ? What do you mean when you write $k = \# A$ ? $\endgroup$ – Noam May 9 '16 at 21:20
  • $\begingroup$ By $\# A$ I mean the (finite) cardinality of $A$. $\endgroup$ – Matias Heikkilä May 9 '16 at 21:21
  • $\begingroup$ Ahh ok, I used to write $|A|$. But,I still dont understand how this helps you. $\endgroup$ – Noam May 9 '16 at 21:22
  • $\begingroup$ Well if $A$ is finite, you can just label the elements as $a_0, \dots a_n$ and define $f(a_i) =i$. $\endgroup$ – Matias Heikkilä May 9 '16 at 21:24
  • $\begingroup$ Ok,I got the idea. But, How can i write it by algebric way ? $\endgroup$ – Noam May 9 '16 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.