- #1
riskybeats
- 18
- 0
Homework Statement
Prove that N X N is denumerable and provide a bijective function (also prove that the function is bijective)
Homework Equations
Cantor's Diagonalization argument
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!