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