How to show this map to be bijective? In Example 2 of Section 7 in his book TOPOLOGY, 2nd edition, James R. Munkres shows that the Cartesian product $Z_+ \times Z_+$, where $Z_+$ denotes the set of all positive integers, is countably infinite as follows: 
First, he defines a subset $A$ of $Z_+ \times Z_+$ as follows: 
$$A \colon= \{ \, (x,y) \in Z_+ \times Z_+ \, \colon \, y \leq x \, \}. $$ 
Then he defines a map $f \colon Z_+ \times Z_+ \to A$ as follows: 
$$f(x,y) \colon= (x+y-1, y) $$ for all $(x,y) \in Z_+ \times Z_+$. 
Finally, he defines a map $g \colon A \to Z_+$ as follows: 
$$ g(x,y) \colon= \frac{1}{2} x(x-1) + y$$ for all $(x,y) \in A$. 
Now I've managed to show that the map $f$ is bijective. How to show that the map $g$ is also bijective? 
By finding the images of the points $(1,1)$, $(2,1)$, $(2,2)$, $(3,1)$, $(3,2)$, $(3,3)$, $(4,1)$, $(4,2)$, $(4,3)$, $(4,4)$, and so on, it is intuitively clear that the map $g$ counts the points in $A$. 
How to demonstrate this bijectivity rigorously? 
 A: The general behavior of the map $g$ is exactly as you suspect. (1,1) is mapped to the first integer 1. (2,1) and (2,2) are mapped to the next integers 2, 3. (3,1), (3,2), (3,3) are mapped to the next integers 4, 5, 6.
In general, in order to find g(x,1), we must count how many pairs have been mapped before. That number is the cardinality of the set $B = \{(x', y') | 1 \leq x' \lt x, 1 \leq y' \leq x' \}$. $B$ is the disjoint union of the sets $C_{x'} = \{ (x',y') | 1 \leq y' \leq x' \}$ for $1\leq x' \lt x$. Obviously, $|C_{x'}| = x'$, so $|B| = |C_1| + \cdots + |C_{x - 1}| = 1 + 2 + \cdots + (x - 2) + (x - 1) = x (x - 1) / 2$. Here, the last equality is a "well known identity". I just assume, you've seen that before.
So, when we want to map (x,1), all the integers from 1 to $x(x-1)/2$ have already been chosen, and the next free integer is $g(x,1) = x(x-1)/2 + 1$. Continuing in this way, the next free integer for (x,y) with $1 \leq y \leq x$ is $g(x,y) = x(x-1)/2 + y$.
In order to map the pairs $(x+1,1), \ldots, (x+1,x+1)$, we repeat this whole argument with $x+1$ instead of $x$.
All in all, we see that if we order the elements of the set $A$ from your question lexicographically (i.e. $(x,y) \lt (x',y')$ iff $(x \lt x')$ or $(x = x'$ and $y \lt y')$, then g(x,y) is just the number of (x,y) in that ordering.
This shows that $g$ is a bijection. The inverse $h$ of $g$ works as follows. Given $m \in \mathbb Z^+$, set $x = \max\{x' | x' (x' - 1)/2 \lt m \}$ and $y = m - x$. Then $h(m) = (x,y)$ and $g(x,y) = m$.
