Prooving 1-1 Function

**neelpatel89** · October 21st 2009, 07:58 AM

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

**Grandad** · October 21st 2009, 08:33 AM

Hello neelpatel89

Originally Posted by neelpatel89

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

Let me set out for you what you need to prove.

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

For (a), you need to show that if $p, q \in \mathbb{Z}$ and $f(p) = f(q)$ , then $p = q$ . You'll need to consider the cases where $p$ and $q$ take various combinations of positive and negative signs.

To start you off, suppose $p\ge0, q\ge0$ , and $f(p) = f(q)$ . Then ...?

Then look at what happens if $p$ and $q$ are both negative. Finally show that if $p$ and $q$ have different signs, then $f(p) \ne f(q)$ .

For (b) you need to show that for any $n \in \mathbb{N}\cup \{0\}$ , we can find an $m \in \mathbb{Z}$ such that $n = f(m)$ . Again you'll need to consider two separate cases: this time it will be whether $n$ is even or odd.

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

Grandad

**neelpatel89** · October 21st 2009, 08:57 AM

Originally Posted by Grandad

Hello neelpatel89Let me set out for you what you need to prove.

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

For (a), you need to show that if $p, q \in \mathbb{Z}$ and $f(p) = f(q)$ , then $p = q$ . You'll need to consider the cases where $p$ and $q$ take various combinations of positive and negative signs.

To start you off, suppose $p\ge0, q\ge0$ , and $f(p) = f(q)$ . Then ...?

Then look at what happens if $p$ and $q$ are both negative. Finally show that if $p$ and $q$ have different signs, then $f(p) \ne f(q)$ .

For (b) you need to show that for any $n \in \mathbb{N}\cup \{0\}$ , we can find an $m \in \mathbb{Z}$ such that $n = f(m)$ . Again you'll need to consider two separate cases: this time it will be whether $n$ is even or odd.

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

Grandad

i kind of not see it
i haven't done proofs extensively
still confused

**Grandad** · October 21st 2009, 01:39 PM

Hello neelpatel89

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

(a) Consider $p, q \in \mathbb{Z}$ , where $f(p) = f(q)$

First: $p\ge 0$ and $q \ge 0$

$\Rightarrow 2p = 2q$

$\Rightarrow p = q$

Then $p < 0$ and $q < 0$

$\Rightarrow -(2p+1) = -(2q+1)$

$\Rightarrow p = q$

Finally, we note that if $p \ge 0, f(p)$ is even and if $q < 0$ , $f(q)$ is odd. So $f(p) \ne f(q)$ if $p$ and $q$ have different signs.

So for all $p,q \in \mathbb{Z}, f(p) = f(q) \Rightarrow p = q$ , and therefore $f$ is injective.

(b) Consider $m \in \mathbb{N} \cup \{0\}$ .

Then if $m$ is even, $m = 2n$ for some $n \in\mathbb{N} \cup \{0\}$ . Also $m \ge 0$ . So $n \ge 0$ . Therefore $f(n) = m$ for some $n \in \mathbb{Z}$ .

If $m$ is odd, $m \ge 1$ and therefore $m = 2n-1$ for some $n > 0$

$\Rightarrow m = -(2(-n)+1)$ , where $(-n) < 0$

$\Rightarrow m = f(-n)$

Therefore for all $m \in \mathbb{N} \cup \{0\}$ , there is an $n \in \mathbb{Z}$ such that $f(n) = m$ . Therefore $f$ is surjective.

Grandad

Thread: Prooving 1-1 Function

LinkBack

Thread Tools

Display

Prooving 1-1 Function

Similar Math Help Forum Discussions

Role of Rule in Prooving a Function? Help!

Prooving

[ASK] Logic Prooving

Prooving and Identity

Need help with prooving

Search Tags