Register to reply

Prove N X N is countable and provide a bijective function

Share this thread:
riskybeats
#1
Apr3-11, 11:03 PM
P: 17
1. The problem statement, all variables and given/known data

Prove that N X N is denumerable and provide a bijective function (also prove that the function is bijective)

2. Relevant equations

Cantor's Diagonalization argument

3. The attempt at a solution

My teacher provided a full solution, but it is in coming up with the function which is where I get stumped. He provides this algorithm:

For (a,b) proceeding (c,d) in the list, we list (a,b) following this algorithm

i) Either a + b < c + d
ii) or if a + b = c + d, a < c

note if a + b = c + d, and a = c, then b = d.

He goes on to list the pairs following the algorithm:
(1,1);
(1,2),(2,1);
(1,3),(2,2),(3,1);
...
(1,a+b - 2),(2,a+b-3),...,(a+b-2,1);
(1,a+b-1),(2,a+b-2),...(a-1,b+1),(a,b);

Then if k is the step belonging to where the pair is in the list (with k belonging to N), then
k = 1 + 2 + 3 + ... + a + b - 2 + a = (a + b - 2)(a + b - 1)/2 + a

I get that induction is used in the last point, and we are summing all the pairs. The only thing I don't understand is how we know that a + b - 2 is always the number of terms in the "group" of numbers following the "group" containing (a,b). I can see when I plug in some arbitrary a,b, that yes, it does end up that way. But I want it to be a bit more rigorous than that.

Any insights? Thanks!
Phys.Org News Partner Science news on Phys.org
Suddenly, the sun is eerily quiet: Where did the sunspots go?
'Moral victories' might spare you from losing again
Mammoth and mastodon behavior was less roam, more stay at home
Stephen Tashi
#2
Apr4-11, 12:18 AM
Sci Advisor
P: 3,245
Quote Quote by riskybeats View Post

Then if k is the step belonging to where the pair
What pair? (a,b) ?
is in the list (with k belonging to N), then
k = 1 + 2 + 3 + ... + a + b - 2 + a = (a + b - 2)(a + b - 1)/2 + a

I get that induction is used in the last point, and we are summing all the pairs. The only thing I don't understand is how we know that a + b - 2 is always the number of terms in the "group" of numbers following the "group" containing (a,b).
Do you mean "following" or "preceding"? By "the group containing (a,b)", do you mean the set of pairs whose sums are equal to a+b ?

The set preceding those that sum to a+b are the (x,y) such that x+y = a + b -1. For a sum of N, there are N-1 ordered pairs of numbers with that sum since the first number can be any of 1,2...N-1. So the number of (x,y) pairs is (a+b-1)-1 = a + b -2.
riskybeats
#3
Apr4-11, 12:35 AM
P: 17
Sorry for the confusing wording, I meant preceding. That makes more sense, but I am still not sure why there is the condition that x + y = a + b - 1. For the set of paired numbers before the set containing (a,b), there are a + b - 2 members. For the set containing (a,b), there are a members, since it stops at that pair. So why wouldn't it be a + b - 3? Making k = 1 + 2 + ... + a + b - 3 + a ?

Also, how do we know that it goes
(1,1)
(1,2)(2,1)
...
(1,a + b - 2).. ?

Meaning, is it just observation that b would be a + b - 2 in the set of numbers preceding the set containing (a,b)?

Thanks for your help

riskybeats
#4
Apr4-11, 12:51 AM
P: 17
Prove N X N is countable and provide a bijective function

Actually I get what you mean, and that would work with the conditions of the algorithm as well. But how do we know that the set preceding the set which has the pairs satisfying a + b contain the pair (a,b)?

Ps. This is a great way to practice talking about this stuff correctly (or at least trying to). Thanks for the practice!
Stephen Tashi
#5
Apr4-11, 12:59 AM
Sci Advisor
P: 3,245
Quote Quote by riskybeats View Post
Sorry for the confusing wording, I meant preceding. That makes more sense, but I am still not sure why there is the condition that x + y = a + b - 1.
The set of ordered pairs that preceeds those whose sum is a+b, is the set whose sum is one less than a+b.

For the set of paired numbers before the set containing (a,b), there are a + b - 2 members.
Yes
For the set containing (a,b), there are a members, since it stops at that pair.
Yes
So why wouldn't it be a + b - 3?
What do you mean by "it"? , the sum that defines the ordered pairs in the set that preceeds (a,b) ? Or the number of ordered pairs in that set?

Making k = 1 + 2 + ... + a + b - 3 + a ?

Also, how do we know that it goes
(1,1)
(1,2)(2,1)
...
(1,a + b - 2).. ?
I think it goes
(1,1) (those that sum to 2)
(1,2)(2,1) (those that sum to 3)
....
(1,a+b-2)(2,a+b-3)(3,a+b-4)....(a+b-2,1) (those that sum to a+b-1)
(1,a+b-1)(2,a+b-2)...(a,b) (some of those that sum to a+b)


Meaning, is it just observation that b would be a + b - 2 in the set of numbers preceding the set containing (a,b)?
I don't know what that means.
riskybeats
#6
Apr4-11, 11:16 AM
P: 17
Okay that makes sense. Thanks for your help.


Register to reply

Related Discussions
Prove set S is countable iff there exists a surjective/injective function Set Theory, Logic, Probability, Statistics 2
Figuring out if a 3d function is bijective Calculus & Beyond Homework 0
Prove a map of a space onto itself is bijective Set Theory, Logic, Probability, Statistics 7
Bijective function Calculus & Beyond Homework 2
Bijective function Set Theory, Logic, Probability, Statistics 1