(adsbygoogle = window.adsbygoogle || []).push({}); 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!

**Physics Forums - The Fusion of Science and Community**

# Prove N X N is countable and provide a bijective function

Know someone interested in this topic? Share a link to this question via email,
Google+,
Twitter, or
Facebook

Have something to add?

- Similar discussions for: Prove N X N is countable and provide a bijective function

Loading...

**Physics Forums - The Fusion of Science and Community**