Re: [Tutor] Cantor pairing in three dimensions?

[Brian van den Broek]

On 24 December 2013 16:21, Brian van den Broek
 wrote:
> On 23 December 2013 13:32, Danny Yoo  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




> 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:




Hi Danny and all,

What I said was not right. (I cannot now see how I thought it was.) Apologies.

For an actual proof:
http://planetmath.org/thecartesianproductofafinitenumberofcountablesetsiscountable.

Best,

Brian vdB
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

Re: [Tutor] Cantor pairing in three dimensions?

[Brian van den Broek]

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

Re: [Tutor] Cantor pairing in three dimensions?

[Steven D'Aprano]

On Mon, Dec 23, 2013 at 10:32:14AM -0800, Danny Yoo 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
[...]
> So here's the question: is there an analogy of the Cantor pairing
> function that maps N to N^3?

The Wikipedia article talks about generalizing the function so as to 
map N^k -> N for any integer k >= 1, so I would say so.

The mapping from N^3 -> N seems to be called the tripling function. Try 
this to start:

http://szudzik.com/ElegantPairing.pdf


Translating the Mathematica code into Python should be straight-forward.



-- 
Steven
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor

[Tutor] Cantor pairing in three dimensions?

[Danny Yoo]

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?
___
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor