# Thread: Prooving 1-1 Function

1. ## Prooving 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

2. 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.

3. 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.

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

4. 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.