# Prooving 1-1 Function

• Oct 21st 2009, 07:58 AM
neelpatel89
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
• Oct 21st 2009, 08:33 AM
Hello neelpatel89
Quote:

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 $\displaystyle f$ is (a) an injection (one-to-one); and (b) a surjection (onto function).

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

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

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

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

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

• Oct 21st 2009, 08:57 AM
neelpatel89
Quote:

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

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

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

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

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

For (b) you need to show that for any $\displaystyle n \in \mathbb{N}\cup \{0\}$, we can find an $\displaystyle m \in \mathbb{Z}$ such that $\displaystyle n = f(m)$. Again you'll need to consider two separate cases: this time it will be whether $\displaystyle 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
• Oct 21st 2009, 01:39 PM
Hello neelpatel89

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

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

First: $\displaystyle p\ge 0$ and $\displaystyle q \ge 0$
$\displaystyle \Rightarrow 2p = 2q$
$\displaystyle \Rightarrow p = q$
Then $\displaystyle p < 0$ and $\displaystyle q < 0$
$\displaystyle \Rightarrow -(2p+1) = -(2q+1)$
$\displaystyle \Rightarrow p = q$
Finally, we note that if $\displaystyle p \ge 0, f(p)$ is even and if $\displaystyle q < 0$, $\displaystyle f(q)$ is odd. So $\displaystyle f(p) \ne f(q)$ if $\displaystyle p$ and $\displaystyle q$ have different signs.

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

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

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

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

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

$\displaystyle \Rightarrow m = f(-n)$

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