How to start Z+ X Z+ -> Z+

[The Captain]

Homework Statement

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

Homework Equations

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)
.
.
.
.
.
.
.
(a+n,b)........(a+n,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?

 

[logarithmic]

Homework Statement

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

Homework Equations

The Attempt at a Solution

I have absolutely no idea how to start this.

So what's the question?

 

[The Captain]

Sorry, forgot that.

Question is, "Prove f is bijection."

 

[The Captain]

Please check my assumption.

 

[logarithmic]

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)
.
.
.
.
.
.
.
(a+n,b)........(a+n,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?

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.