Theorem: prove that $f:\mathbb{N}\longrightarrow \mathbb{N}_k\times \mathbb{N}$ by $f(n)=(m,n), \forall m\in \mathbb{N}_k, \forall n\in \mathbb{N}$ is bijective.
My attempt: $\forall n_1, n_2\in \mathbb{N}$ let $f(n_1)=f(n_2)$. Then $(m,n_1)=(m,n_2)$. Therefore $n_1=n_2$ and hence $f$ is injective.
$f$ is obviously serjective, because $\forall (m,n)\in \mathbb{N}_k\times \mathbb{N}, f(n)=(m,n)$ since $n\in \mathbb{N}$. So $f$ is bijective.

Is my proof correct? Is the theorem correct at all

  • $\begingroup$ I'd say you meant $\forall n\in\mathbb{N}$. Anyway, if the first component $m$ is fixed, how can it be bijective? Or am I misunderstanding that definition? $\endgroup$ – MickG Sep 12 '15 at 16:10
  • $\begingroup$ @MickG: Yes, that was a typo. Corrected it. I don't know, maybe the theorem be wrong at all! $\endgroup$ – Sisabe Sep 12 '15 at 16:14
  • $\begingroup$ If you define $f$ to be $f(n)=(m,n)$ with a fixed $m\in\mathbb{N}_k$ and $n$ varying in $\mathbb{N}$, then take $m'\neq m$ but still in $\mathbb{N}_k$ and for no $n\in\mathbb{N}$ you have $(m',n)$ is an image of $f$, so $f$ is not surjective. Note: the above comment by Sisabe was posted while I typed this. $\endgroup$ – MickG Sep 12 '15 at 16:14
  • $\begingroup$ Your function not well defined $\endgroup$ – Hamou Sep 12 '15 at 16:14
  • $\begingroup$ @Hamou: So how to edit it to be well defined? $\endgroup$ – Sisabe Sep 12 '15 at 16:16

Your Answer

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

Browse other questions tagged or ask your own question.