Talk:Pairing function

Questions

No mention of Gödelization? —Preceding unsigned comment added by 213.249.223.158 (talk • contribs)

This pairing function can be used for Gödelization, but other methods can be used as well. This pairing function also has other uses. So there is no necessary connection between them. Mentioning Gödelization would be a distraction. JRSpriggs 19:07, 20 August 2007 (UTC)

Is the w formula unnecessary complicated?

here it gives as the w function w = int[ {sqr(8 * z +1) -1} /2 ]

while mathworld gives the simpler w = int { sqr(2 * z) -1/2} —The preceding unsigned comment was added by 193.61.13.138 (talk) 15:45, August 20, 2007 (UTC)

I proved that the first formula works. Do you have a proof that the second formula works? Also, the second formula seems to fail when z=0, since it gives w=-1 when it should be w=0. JRSpriggs 19:07, 20 August 2007 (UTC)

In Mathworld $x+y=w+2$, unlike in the article: $x+y=w$. —Preceding unsigned comment added by 77.124.183.77 (talk) 05:42, 9 July 2009 (UTC)

Is there a closed-form polynomial expression for the inverses of the pairing function as opposed to the current algorithmic definition? Somenick 20:28, 17 September 2007 (UTC)

Apparently, the MathWorld article covers two different pairing functions. The first does pairing on the positive integers. The second on the non-negative integers. So naturally, the formulas for the first and second cases are slightly different. Our article only covers the second case (which is sufficient to my mind).

I am not aware of any polynomial formula in one variable which would give either x or y as a function of z=<x,y>. And I doubt that any such formula is possible. However, if one allows other variables whose values will be ignored, then there may be one. See Hilbert's tenth problem. JRSpriggs (talk) 06:19, 9 July 2009 (UTC)

minor edit

Changed the author's name in reference to comply with Mathworld's citation scheme. (plus it's the correct author name, now) —Preceding unsigned comment added by 24.37.252.19 (talk) 14:15, 9 August 2008 (UTC)

Thanks. JRSpriggs (talk) 06:35, 10 August 2008 (UTC)

Question

i don't get the line " we get that " line, where you conclude

$w\leq {\frac {{\sqrt {8z+1}}-1}{2}}<w+1$

129.187.41.61 Infinity ive (talk) 13:43, 19 November 2009 (UTC)

First notice that there are two strictly increasing functions from the non-negative reals to the non-negative reals: the triangle function T and its inverse, the triangle root R.

$t=T(w)={\frac {w^{2}+w}{2}}\,$

$w=R(t)={\frac {{\sqrt {8t+1}}-1}{2}}\,.$

For any non-negative real number w,

$R(T(w))=w\,.$

Now notice that because

$0\leq y<w+1\,$

we get

$t\leq t+y<t+(w+1)\,$

which is the same as

$T(w)\leq z<T(w+1)\,.$

If we apply R to these we get

$R(T(w))\leq R(z)<R(T(w+1))\,$

which is the same as

$w\leq R(z)<w+1\,$

in other words

$w\leq {\frac {{\sqrt {8z+1}}-1}{2}}<w+1\,.$ OK? JRSpriggs (talk) 17:47, 20 November 2009 (UTC)

This was very helpful, thank you. — Preceding unsigned comment added by 93.129.94.221 (talk) 23:22, 16 April 2012 (UTC)

Question

The definition of the Cantor pairing function in the MathWorld article differs from that given here in the fact that their arguments (x,y or i,j) are inverted. It can be seen that, in the MathWorld matrix the first argument ( i ) increases along the vertical axis, while in the Wikipedia article the first argument ( x ) increases along the horizontal axis. That difference yields to the following formulae:

Wikipedia article:

$\langle x,y\rangle ={\frac {(x+y)(x+y+1)}{2}}+y$

MathWorld article:

$\langle x,y\rangle ={\frac {(x+y)(x+y+1)}{2}}+x$

Which is the true definition of the Cantor pairing function ? --Aldo Caruso (talk) 02:05, 10 July 2010 (UTC)

They are functionally equivalent since one merely has to reverse the order of the arguments to convert one into the other. Thus, it is purely a matter of taste as to which function one prefers to use. Personally, I would rather increase x (the first argument) before increasing y (the second argument) when listing the pairs in order of the result. Thus I prefer Wikipedia's version. JRSpriggs (talk) 07:37, 10 July 2010 (UTC)

Alternate methods

There are other ways to make a pairing function too, such as INTERCAL's bit interleave operator (extended so it is not limited to sixteen or thirty-two bits); this was my first idea when I thought about pairing functions, actually. There may be more possiblities? What would they be, if it is? --Zzo38 (talk) 06:34, 10 August 2012 (UTC)