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)