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!