0
$\begingroup$

I need to show that $(m,n) \mapsto 2^{m-1}(2n-1)$ is a bijection of $\mathbb{N} \times \mathbb{N}$ on $\mathbb{N}$

I think I need to show that the expression is both injective and surjective, but I am not sure how to do that.

Maybe a kind person can help me in some direction?

Thanks in advance.

$\endgroup$
3
  • $\begingroup$ I see a problem: $(0,0) \to 2^{-1}(-1) = -\frac{1}{2}$. $\endgroup$
    – J.-E. Pin
    Oct 6, 2013 at 13:49
  • $\begingroup$ @J.-E.Pin: I'd wager that the OP's natural numbers are positive integers. $\endgroup$
    – Cameron Buie
    Oct 6, 2013 at 13:50
  • $\begingroup$ @J.-E.Pin I guess the person posing the problem works with the definition $\mathbb{N} = \mathbb{Z}^+$. $\endgroup$
    – Daniel Fischer
    Oct 6, 2013 at 13:50

1 Answer 1

Reset to default
0
$\begingroup$

For surjectivity, you'll want to show that every natural number is an odd number (possibly $1$) times some non-negative integer power of $2$.

For injectivity, suppose that $$2^{m_1-1}(2n_1-1)=2^{m_2-1}(2n_2-1),$$ where $m_1\ge m_2,$ so that $$2^{m_1-m_2}=\frac{2^{m_1-1}}{2^{m_2-1}}=\frac{2n_2-1}{2n_1-1}$$ is an integer. Since a ratio of two odd numbers can't be even, it follows that $2^{m_1-m_2}=1,$ so $m_1=m_2,$ and likewise $n_1=n_2$.

$\endgroup$
2
  • $\begingroup$ Thanks a lot, I think I can do it. Maybe you can give a hint on how I could show that $\mathbb{N} \times \mathbb{N}$ is numerable according to the above? $\endgroup$
    – Peter
    Oct 6, 2013 at 14:34
  • $\begingroup$ Well, take any $k\in\Bbb N$. If $k$ is odd, then $k+1$ is even and positive, and so $\frac{k+1}2$ is a natural number, say $n,$ so that $k=2n-1=2^0(2n-1).$ If $k$ is even, then we can write $k=2^mj$ for some positive integer $m$ and some odd integer $j$ (why?), and so.... $\endgroup$
    – Cameron Buie
    Oct 6, 2013 at 16:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .