[Tutor] Cantor pairing in three dimensions?

[Brian van den Broek]

On 23 December 2013 13:32, Danny Yoo <dyoo at hashcollision.org> wrote:
>
> I've got a puzzle: so there's a well-known function that maps the
> naturals N to N^2: it's called Cantor pairing:
>
>     http://en.wikipedia.org/wiki/Pairing_function
>
> It's one of those mind-blowing things that I love.  I ran across it a
> few years ago in a thread on Python-tutor a few years back:
>
>     https://mail.python.org/pipermail/tutor/2001-April/004888.html
>
>
> Recently, the topic came up again for me, but in an expanded context:
>
> https://plus.google.com/117784658632980303930/posts/4SMcjm2p9vv
>
>
> So here's the question: is there an analogy of the Cantor pairing
> function that maps N to N^3?



Hi Danny,

It does generalize; a well known result of set theory has it that the
Cartesian product of finitely many countable sets is itself countable
(where countable means either finite or infinite but able to be mapped
1:1 to the natural numbers). Here's a hand-wavy proof sketch that
assumes we've already got the map N -> N^2:

Given a map from N -> N^m we can easily create a new map N -> N^(m+1):
replicate the grid from
<http://en.wikipedia.org/wiki/File:Pairing_natural.svg> (the diagram
in the wiki page that you linked to), with the natural numbers along
the x-axis replaced by the members of N^m. Now, follow the same
procedure that was used to demonstrate the existence of the map N ->
N^2. The resulting function is a map N -> N^(m + 1), as desired.

Best,

Brian vdB