Talk:Pairing function

Old 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)

Don't you think it's a good idea to include the above answer in the article?

It's not at all easy to see or conclude. 197.79.64.248 (talk) 15:17, 4 June 2014 (UTC)

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

Related Question

Why is it important that

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

We know a priori that w=x+y is a natural number. We just _know_ that

$w={\frac {{\sqrt {8z+1}}-1}{2}}\,,$

no need to worry about taking integer parts... — Preceding unsigned comment added by 131.111.243.142 (talk) 16:11, 24 January 2013 (UTC)

The inequality is how we can show that the equality

$w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor$

holds. Notice the floor function. I just stopped my argument at that point (the inequality) because that was the question which I was asked.

You do not "just know" what you said that you "just know", because it is not true if y≠0. JRSpriggs (talk) 10:05, 25 January 2013 (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)

No, they are different:

Wikipedia article: <1,0> = 1 (correct)

MathWorld article: <1,0> = 2 (wrong) Jack Rusell (talk) 20:28, 19 April 2024 (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. (It also seems that this can then be used not only for natural numbers but for p-adic numbers too.) There may be more possiblities? What would they be, if it is? --Zzo38 (talk) 06:34, 10 August 2012 (UTC)

Certainly, there are an infinite number of distinct pairing functions. So I will not try to list them. This one is perhaps the simplest one mathematically (at least of those which do not give undue weight to one of the two inputs) which is why we use it here. JRSpriggs (talk) 07:07, 10 August 2012 (UTC)

Is it really invertible?

I'm not sure that the section on inverting the pairing function is entirely correct. The section proves that given a $z\in \mathbb {N}$ there exist $x,y\in \mathbb {N}$ such that $\pi (x,y)=z$ and thus that $\pi$ is onto. We still need to prove that $\pi$ is one-to-one before we can conclude that $\pi$ has an inverse. — Preceding unsigned comment added by 24.212.164.204 (talk • contribs) 16:53, 23 June 2015‎ (UTC)

Frankly, to a mathematician, it is obvious from the formula and the diagram that π is one-to-one and onto.

And as the section on the inversion ends by saying, "Since the Cantor pairing function is invertible, it must be one-to-one and onto." which is the converse of the theorem to which you are appealing (and also a theorem).

Any z is bracketed between two successive triangle numbers, so the lower of those two (t) is unique. Thus y=z-t is unique. And t 's triangle root (w) is unique. Thus x=w-y is unique. So π is one-to-one. OK? JRSpriggs (talk) 07:38, 24 June 2015 (UTC)

It really looks to me that this whole section just shows that if π is invertible, then this function we get here will be the inverse of π, because it seems to assume that the x and y can be found even though that is what it should prove. The bijectivity of the pairing function might be “obvious” from the formula to someone who has been staring primitive recursive functions for years, but most Wikipedia users have not been (and at least it should be said that the proof is based on the assumtion). (I admit that the diagram is pretty believable but diagrams are never mathematical proofs.) I just spent quite some time myself thinking this through and concluded that you first need to know that the function is one-to-one and onto because proving the inverse function to actually be the inverse function is something that is nowhere near trivial. Stupid Hedgehog (talk) 11:06, 9 April 2017 (UTC)

Encoded or not?

Given a number, is there a way to check whether that number has been encoded using Cantor Pairing function or not? — Preceding unsigned comment added by 1.186.134.44 (talk) 11:13, 13 July 2015 (UTC)

No. A natural number is just a natural number. How you interpret it must be determined from the context, not from the number itself. JRSpriggs (talk) 21:06, 13 July 2015 (UTC)

Wrong: As the pairing function is surjective, each natural number is in the range of the pairing function. I.e. the "check" answers "yes" for each number. Jack Rusell (talk) 20:32, 19 April 2024 (UTC)

Suggestion

A numerical example of coding and decoding would be helpful.--Billymac00 (talk) 23:58, 6 September 2015 (UTC)

I added a new section, Pairing function#Examples, in which I calculated π forwards for one case and backwards for another case. JRSpriggs (talk) 02:17, 7 September 2015 (UTC)

Why not backward for the same case to empirically show invertibility? paolor (talk) 22:00, 3 March 2021 (UTC)

Reversing the calculations is trivial and would add nothing. To show invertibility, we need to see that it is not necessary to know ahead of time what the forward calculation is, when doing the backward calculation. And that is what I showed. JRSpriggs (talk) 02:25, 4 March 2021 (UTC)

Origin of the Elegant pairing function

Szudzik's pairing function already appeared in a 1965 paper Nagashima, Takashi (1965), "On a certain class of recursive functions", Hitotsubashi Journal of Arts and Sciences, 16: 72–81. This idea goes back to Godel according to Nagashima's paper. Sillycrown (talk) 05:44, 6 September 2022 (UTC)

"Inductive definition"

The "inductive definition" is not a definition as the given equations do not enable to calculate the values of π. E.g. try π(1, 0). The following equations define π recursively:

π(0,0) := 0

π(x+1,0) := π(x,0)+x+1

π(x,y+1) := π(x+1,y)+1

π is well-defined as the arguments of the recursive calls at the equations' right-hand sides are lexicographic smaller than the respective arguments on the left-hand sides. The proof that π satisfies Cantor's definition is by induction on the recursion structure of π and obtained with basic school math.

Hilbert's Hotel page

There are many more pairing functions listed at https://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand_Hotel#Infinitely_many_coaches_with_infinitely_many_guests_each. They would be a useful addition, though there are no sources on that page for them. 70.106.246.156 (talk) 16:29, 18 June 2024 (UTC)