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

• The Captain
Suppose you're given the positive integers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, and you're asked to find (a,b) so that f(a,b) is 12. You could easily do it by counting up from 1, then doubling the number you counted, and adding 1 to that.

## 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

## 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?

Last edited:
The Captain said:

## 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

## The Attempt at a Solution

I have absolutely no idea how to start this.
So what's the question?

Sorry, forgot that.

Question is, "Prove f is bijection."

The Captain said:
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.

Last edited: