Talk:Cartesian Product of Countable Sets is Countable

Can't we formalize the informal proof? To count $\mathbb N^2$, we have

$(0,0)$

$(0,1),(1,0)$

$(0,2),(1,1),(2,0)$

etc. We can define this recursively:

$s_1 = (0,0)$

If $(s_n)_2 = 0$, then $s_{n+1} = (0,(s_n)_1+1)$.

If $(s_n)_2 \ne 0$, then $s_{n+1} = ((s_n)_1+1, (s_n)_2-1)$.

Now $(s_n)_1 + (s_n)_2$ is monotonically increasing, so it eventually reaches any given natural. It's then clear that $s_n$ reaches any ordered pair of naturals. I'll try to do this sometime soon.--Dfeuer (talk) 03:53, 21 December 2012 (UTC)

As long as you don't replace that existing informal proof, but instead create a new instance of a proof, knock yourself out. --prime mover (talk) 10:28, 21 December 2012 (UTC)