Hello,

I need to show that is a bijection of on

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.

Printable View

- Oct 6th 2013, 06:36 AMpeter89Bijection question
Hello,

I need to show that is a bijection of on

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. - Oct 6th 2013, 06:51 AMPlatoRe: Bijection question
- Oct 6th 2013, 08:08 AMpeter89Re: Bijection question
Thanks for your reply. I am not quite sure how to show that every natural number is an odd number (possibly 1) times some non-negative integer power of 2. I can see it works by doing some examples, but how I precisely can show it? Hmm, maybe a hint?

- Oct 6th 2013, 08:23 AMPlatoRe: Bijection question
- Oct 6th 2013, 11:17 AMemakarovRe: Bijection question
This can be shown by strong induction. However, you need to decide what facts you can rely on. You are not going to prove commutativity of addition, right? Similarly, it is somewhat obvious that dividing a positive integer repeatedly by 2 will eventually yield an odd number because with each division the number is getting smaller, and this can't go on forever.

- Oct 6th 2013, 12:44 PMHallsofIvyRe: Bijection question
Definition of "even": a natural number, n is even if and only if n= 2k where k is a natural number.

If N is a natural number, it can be written as N= 2K for some natural number K. If K is odd, you are done- N is "2 to the 1 power" times n odd number. if K is even, K= 2M for some integer M. If M is odd, you are done: N= 2K= 2(2M)= 4M is "2 to the 2 power" times an odd number. If M is even, M= 2J for some integer J. If J is odd....

Note that N> K> M> J... so that will eventually terminate.