1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How to start Z+ X Z+ -> Z+

  1. Sep 14, 2010 #1
    1. The problem statement, all variables and given/known data
    Define f: Z+ X Z+ -> Z+ by
    f(a,b) = 2^(a-1)(2b-1) for all a,b in Z+
    where Z+ is the set of all positive integers,
    and X is the Cartesian product

    2. Relevant equations

    3. The attempt at a solution

    If we assume (a,b) as ordered pairs and write them as follows:

    (1,1) (1,2) (1,3) (1,4)..........(a,b+n)
    (2,1) (2,2) (2,3) (2,4)..........(a+1,b+n)

    Using diagonal processing, we deduce that f is one-one.

    Now can we also assume it is onto because f(a,b) maps to exactly one ordered pair?
    Last edited: Sep 15, 2010
  2. jcsd
  3. Sep 14, 2010 #2
    So what's the question?
  4. Sep 14, 2010 #3
    Sorry, forgot that.

    Question is, "Prove f is bijection."
  5. Sep 15, 2010 #4
    Please check my assumption.
  6. Sep 15, 2010 #5
    What this shows is that there is a bijection from Z+ x Z+ to Z+. It doesn't prove that (2^(a-1))(2b-1) is one of such bijections. So it doesn't help.

    I'm interpreting f(a,b) = 2^(a-1)(2b-1) as (2^(a-1))(2b-1), and not 2^((a-1)(2b-1)) since the latter isn't 1-1. E.g subbing in (1,1) and (1,2), both gives f = 1.

    To prove that the function is 1-1. Suppose that it isn't, i.e. there exists (a,b) not equal to (c,d) such that f(a,b) = f(c,d). Suppose that a is not equal to c, and without loss of generality assume a>c, then we have (2^(a-1))(2b-1) = (2^(c-1))(2d-1). Therefore (2^(a-c))(2b-1) = 2d - 1. Then the left hand side is an even number, and the right hand side is an odd number. Contradiction. (Notice that a-c = 0 is not possible).

    I assumed that a isn't equal to c there. Now you need to try what happens when a is equal to c, which would imply b is not equal to d (since (a,b) is not equal to (c,d)), and show that this also leads to a contradiction. (It's a simple argument). Once you've done that, you've finished the proof for 1-1.

    To prove it's onto: think about how if I gave you a positive integer, k, how you would find (a,b) so that f(a,b) = k. If that hint doesn't help much, I can be more specific.
    Last edited: Sep 15, 2010
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook