Proving $\mathbb{N} \times \mathbb{N} \cong \mathbb{N}$ when $\mathbb{N}$ includes $0$ I am struggling to find an explicit bijection $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ when $\mathbb{N}$, by definition, includes $0$. If $\mathbb{N}$ were to exclude $0$, I could note that any positive integer can be written uniquely in the form $2^{a-1} (2b - 1)$ and then map $(a,b) \to n$. Including $0$, I have to change $a - 1$ to $a$ and $2b - 1$ to $2b + 1$, but I still run into the issue of what to map to $0$. I can't map $(0,0)$ to $0$, for example, because $2^{0} (2(0) - 1) = 1$ is the unique element of the form $2^{a-1} (2b - 1)$ mapping to $1$.
Does anyone have any tips for how to repair this bijection?
 A: Just.... combine.
You have $f:\mathbb N_{1} \times \mathbb N_1 \to \mathbb N_1$ via $f(a,b) = 2^{a-1}(2b-1)$.
And you have $g:\mathbb N_0 \to \mathbb N_1$ via $g(n) = n+ 1$.
So you have $g\times g: \mathbb N_0 \times \mathbb N_0 \to \mathbb N_1 \times \mathbb N_1$ via $g\times g(a,b) = (g(a), g(b)) = (a+ 1, b+1)$ and
You have $f\circ g\times g:  \mathbb N_0 \times \mathbb N_0 \to \mathbb N_1 \times \mathbb N_1 \to \mathbb N_1$ via $f\circ g\times g (a, b) = f(a+1, b+1) = 2^a(2b + 1)$.
And you have $g^{-1}\circ f\circ g\times g: \mathbb N_0 \times \mathbb N_0 \to \mathbb N_1 \times \mathbb N_1 \to \mathbb N_1\to \mathbb N_0$ via $g^{-1}\circ f\circ g\times g(a,b) = g^{-1} (f(a+1,b+1)) = 2^a(2b+1) -1$.
======
Alternatively the other standard bijection (that works on the cross product of any two countable sets) is to simply list pairs by weaving a diagonal path:
$(1,1), (2,1), (1,2), (3,1), (2,2),(1,3),(4,1), (3,2),(2,3),(1,4), (5,1),(4,2).....(4,2),(1,5), (6,1),(5,2)....,(2,5),(1,6),(7,1).....\to$
$1,2,3,4,5,7......$
Then just adding the index $0$ does not change anything significant.
$(0,0),(1,0),(0,1),(2,0),(1,1),(0,2),(3,0),..... \to $
$0,1,2,3,4,5,6....$
The trouble is we aren't actually explicitely defining what the algebraic expression of the bijection is; just showing intuitively it must exist.  But then again there is nothing in the definition that says we have to define what the bijection is and if we can demonstrate via induction that it exists that is fine.
But with little math we can get the first one is:
For any $(1,k)$ we map $(1,k) \to \sum_{j=0}^k = j$.  And so for the following next batch $(k+1, 1)$ to $(1, k+1)$ we map $(a=(k+1)-(b-1), b)\mapsto (\sum_{j=0}^k j) + b$.... of $(a,b)\to [\sum_{j=0}^{a+b-1} j] + b = \frac {(a+b-1)(a+b)}2 + b= \frac {(a+b)^2+(b-a)}2$.
The second is similar.
If $k = a+ b+ 1$ then $(0, a+b)\mapsto [\sum_{j=0}^k j]-1 = \frac {(a+b+1)(a+b+2)}2 - 1 = \frac{(a+b)^2 +3(a+b)}2 + 1$ and $(a,b)\mapsto \frac{(a+b)^2 +3(a+b)}2 + 1- a = \frac {(a+b)^2 + (a+3b) +2}2$
It may or may not be worth noting with shifiting indexes.
The first $\frac {(a+b)^2+(b-a)}2$ becomes $\frac {(a+1+b+1)^2 - (b-1-a+1)}2-1$ is the same as the same as the second.
