How to understand this proof of the countability of N*N? These days, I am reading Prof.Liviu Nicolaescu's lecture notes on honors calculus.But the proof of an example in Chapter3 makes me confused.

In this example, he constructs a function, and try to prove that it is a bijection. However, I can't understand his method, though he states that domain of the function is $N*N$, I find that firstly, (1,1),(2,1),(2,2),(3,1),(3,2),(3,3),...which in general can be denoted as (m,n) can not represent all elements of $N*N$, he just considered the situation that m>=n, he didn't consider the situation that m<n.Secondly, he said that $\phi$ (m,n)=#$S_1$+...+#$S_{m-1}$+n, however, when m=1,2, the results are wrong. Thirdly, I don't think that it is clear that $\phi$(m,n) is a bijection. I can't prove that it is injection and I think proving it is surjection is even harder for me.
I am a self learner, so I don't know either it is that I'm wrong or the proof itself has some problems. Hope that someone can help me.
I'm not an English native speaker, so please forgive my poor English grammer.
 A: Yes, that proof (although not the result of course!) is incorrect, the big error being the first one: that not all pairs show up in the claimed enumeration.
The general idea of proceeding by "blocks," though, is perfectly fine. Here's one way to do this which actually works: have the $n$th block consist of those pairs whose entries add up to $n+1$. (If we were including $0$ in $\mathbb{N}$, "$n+1$" would get replaced by "$n$" there.) Then each block itself can be ordered (say) by comparing left coordinates. This yields:
$$(1,1),\quad (1,2), (2,1),\quad (1,3), (2,2), (3,1),\quad (1,4), (2,3), (3,2), (4,1),\quad ...$$
(This is very close to the Cantor pairing function and I think may actually have been what Nicolaescu had in mind.) Now to get the corresponding $\phi$, note that $(m,n)$ shows up in the $(m+n-1)$th block and is the $m$th element of that block. Also, the $k$th block has $k$ elements in it. Putting these observations together you can get an explicit formula for $\phi$:

 The number of blocks appearing before $(m,n)$ shows up is $m+n-2$, and the total number of pairs in all these blocks is therefore the sum of the first $m+n-2$ many natural numbers. So the pair $(m,n)$ shows up in position $${(1+m+n-2)(m+n-2)\over 2}+m.$$


Incidentally, this is actually a great motivating moment. It should be clear at this point that actually finding an exact bijection between two infinite sets can be annoying. (Another exercise at this point is to find a bijection between $\mathbb{R}$ and $[0,1]$ - it's not as simple as it may look at first!) Fortunately, there is an extremely powerful tool which makes things much nicer for us, namely the Cantor-Schroeder-Bernstein (or whatever) theorem. This says that it's enough to just find a pair of injections. This is often vastly easier: for example, to show that there is a bijection $\mathbb{N}\rightarrow\mathbb{N}\times\mathbb{N}$ we can just consider the injections $$i\mapsto(i,i)\quad\mbox{and}\quad (m,n)\mapsto 2^m3^n.$$ Moreover, CBS doesn't use the axiom of choice - it's a perfectly direct argument.
