The function f : Z (INTEGERS) -> N(NATURAL NUMBER) U {0} is defined by

f(n) =

(2n) if n >= 0,

−(2n + 1) if n < 0.

Prove f is a bijection.

I know its simple, but i need to show it by using lots of math and little english

Printable View

- October 21st 2009, 07:58 AMneelpatel89Prooving 1-1 Function
The function f : Z (INTEGERS) -> N(NATURAL NUMBER) U {0} is defined by

f(n) =

(2n) if n >= 0,

−(2n + 1) if n < 0.

Prove f is a bijection.

I know its simple, but i need to show it by using lots of math and little english - October 21st 2009, 08:33 AMGrandad
Hello neelpatel89Let me set out for you what you need to prove.

You need to prove that is (a) an injection (one-to-one); and (b) a surjection (onto function).

For (a), you need to show that if and , then . You'll need to consider the cases where and take various combinations of positive and negative signs.

To start you off, suppose , and . Then ...?

Then look at what happens if and are both negative. Finally show that if and have different signs, then .

For (b) you need to show that for any , we can find an such that . Again you'll need to consider two separate cases: this time it will be whether is even or odd.

Let us know if you can't see how to complete it from here.

Grandad - October 21st 2009, 08:57 AMneelpatel89
- October 21st 2009, 01:39 PMGrandad
Hello neelpatel89

Here's the proof, then, using the structure in my earlier post.

(a) Consider , where

First: and

So for all , and therefore is injective.

(b) Consider .

Then if is even, for some . Also . So . Therefore for some .

If is odd, and therefore for some

, where

Therefore for all , there is an such that . Therefore is surjective.

Grandad