On 23 December 2013 13:32, Danny Yoo <[email protected]> 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 _______________________________________________ Tutor maillist - [email protected] To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor
