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

  • #1

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?
 
Last edited:

Answers and Replies

  • #2
107
0

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?
 
  • #3
Sorry, forgot that.

Question is, "Prove f is bijection."
 
  • #4
Please check my assumption.
 
  • #5
107
0
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:

Related Threads on How to start Z+ X Z+ -> Z+

  • Last Post
Replies
3
Views
6K
  • Last Post
Replies
3
Views
2K
Replies
28
Views
3K
Replies
1
Views
2K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
4
Views
5K
  • Last Post
Replies
3
Views
4K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
772
  • Last Post
Replies
2
Views
4K
Top