Results 1 to 4 of 4

Math Help - 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 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
    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 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
    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 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
    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: March 30th 2010, 02:48 PM
  2. Prooving
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 11th 2009, 04:24 PM
  3. [ASK] Logic Prooving
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 7th 2009, 06:52 AM
  4. Prooving and Identity
    Posted in the Pre-Calculus Forum
    Replies: 2
    Last Post: August 11th 2009, 02:51 PM
  5. Need help with prooving
    Posted in the Trigonometry Forum
    Replies: 1
    Last Post: May 12th 2006, 05:09 AM

Search Tags


/mathhelpforum @mathhelpforum