Results 1 to 4 of 4

Thread: Prooving 1-1 Function

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    5

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello neelpatel89
    Quote Originally Posted by neelpatel89 View Post
    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.

    Grandad
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    5
    Quote Originally Posted by Grandad View Post
    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.

    Grandad
    i kind of not see it
    i haven't done proofs extensively
    still confused
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    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.

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Role of Rule in Prooving a Function? Help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Mar 30th 2010, 01:48 PM
  2. Prooving
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: Nov 11th 2009, 03:24 PM
  3. [ASK] Logic Prooving
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 7th 2009, 05:52 AM
  4. Prooving and Identity
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: Aug 11th 2009, 01:51 PM
  5. Need help with prooving
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: May 12th 2006, 04:09 AM

Search Tags


/mathhelpforum @mathhelpforum