0

Does anyone have the closed form for the Cantor-Snake function and its inverse?

By Cantor-Snake, I mean the bijection that maps the Naturals to the Rations - the classic proof that the rationals are denumerable.

I recall seeing the function as follows:

Consider the Natural Numbers, N = { 1,2,3,4... }

Consider the table of (N x N):

| 0 | 1 | 2 | ... |

| 1 | 2 | 3 | ... |

| 2 | 3 | 4 | ... |

And so on. We see that we could map 1 to (0,0), 2 to (0,1), 3 to (1,0), and so, "snaking" through the table. It's clearly surjective, and that's enough to have a bijection in this case (onto from Naturals to an infinite set proves the existence of a bijection).

I want the closed form for that snake function and its inverse. When working with that Rationals proof, we have to skip fractions that reduce - I don't want to skip those, I want to hit all of N cross N.

Thoughts?

en_Knight
  • 175

1 Answers1

1

The Cantor pairing function does what you need. $(x,y) \to z=\frac 12(x+y)(x+y+1)+y$ is a bijection. To invert it, let $w$ be the largest natural such that $\frac 12w(w+1) \le z,$ Let $t=\frac 12w(w+1), y=z-t, x=w-y$

Ross Millikan
  • 374,822
  • Pairing, not snake, gotcha. Thanks! – en_Knight Aug 01 '13 at 03:31
  • @Ross Millikan, is there a closed-form function the other way around? Namely to go from $z \in \mathbb{N}$ to (x,y) for $x,y \in \mathbb{N}$? – ENV Oct 04 '21 at 18:44
  • @ENV: yes, and it is given in a large paragraph in the Wikipedia article I link to. It is also the second sentence of the answer – Ross Millikan Oct 04 '21 at 23:44