# set theory – Showing \$| mathbb{N} | =|mathbb{N} times mathbb{N}|\$ using the diagonal argument Showing $$| mathbb{N} | =|mathbb{N} times mathbb{N}|$$ using the diagonal argument is seeming a little hard for me to prove by an explicit function.

It’s clear that we need a function $$f: mathbb{N} to mathbb{N} times mathbb{N}$$, and arranging them diagonally seems to work very well.

In other words:

$$(0,0) (0,1) (0,2) (0,3) …$$

$$(1,0) (1,1) (1,2) (1,3) …$$

$$(2,0) (2,1) (2,2) (2,3) …$$

… (Not sure how to put in a table).

And we can say $$f(0) = (0,0), f(1) = (0,1), f(2) = (1,0), f(3) = (0,2), f(4) = (1,1) …$$, going diagonally all the way through. I’m trying to find an explicit function for $$f$$ though. The most I’ve come up with is that:

$$0$$ maps to $$(0,0)$$

$$1$$ and $$2$$ get mapped to the points $$(a,b)$$ with $$a,b in { 0,1 }$$, and $$a + b = 1$$.

$$3,4,$$ and $$5$$ get mapped to points $$(a,b)$$ with $$a,b in { 0,1,2 }$$ and $$a+b = 2$$.

$$6, 7, 8$$, and $$9$$ get mapped to points $$(a,b)$$ with $$a,b in { 0,1,2,3 }$$ and $$a + b = 3$$.

How can we write an explicit formula for $$f(n)?$$

I’m aware there are many other ways to show these sets are the same, but I’d like to stick with this technique for now.

Thanks. Posted on Categories Articles