3
$\begingroup$

I recently learned that for natural numbers, the Cantor Pairing function allows one to output a unique natural number from any combination of two natural numbers. According to wikipedia, it is a computable bijection $$f : \mathbb N \times \mathbb N \rightarrow \mathbb N$$ $$f(x,y) := \frac 12 (x+y)(x+y+1)+y$$ Will it generate a unique value for all real (non-integer) number values of $x$ and $y$? I believe there is no inverse function if using non-integer inputs, but I just want to know if the output $f(x,y)$ will still be unique.

Please forgive me if this isn't a worthwhile question, I do not have a mathematics background.

Edit: I'm interested in the case where we constrain $x$ and $y$ to real numbers $>0$.

$\endgroup$
  • $\begingroup$ This might help : The first summand is equal to the sum of the numbers from $1$ to $x+y$ $\endgroup$ – Peter Sep 20 '17 at 19:41
  • $\begingroup$ Yes, every function generates a unique output for all inputs. For example, the function $f(x,y):=3$ generates the unique number $3$ for all $x$ and $y.$ $\endgroup$ – bof Sep 21 '17 at 0:16
3
$\begingroup$

Even for positive reals the answer is no, the result is not unique. You can choose any $x,y,$ compute $f(x,y)$, then choose any $x'\lt x$ and solve $\frac 12(x'+y')(x'+y'+1)+y'=f(x,y)$ for $y'$ The only reason for the $x'$ restriction is to make sure you get a positive square root. For example, let $x=3,y=5,x'=2$. We have $f(3,5)=41$ so want $\frac 12(2+y')(3+y')+y'=41$, which has solutions $y'=\frac 12(-7\pm\sqrt{353})\approx -12.8941,5.8941$ so $f(3,5)=f(2,\frac 12(-7+\sqrt{353}))$ in the positive reals. You can allow any of $x,y,x'$ to be other than integers. $y'$ will usually not be integral.

$\endgroup$
  • $\begingroup$ Very clear and illuminating response, thank you. $\endgroup$ – Devin King Sep 20 '17 at 20:27
  • $\begingroup$ Actually, if $x$ and $y$ are real numbers, $f(x,y)=\frac12(x+y)(x+y+1)+y$ is a unique real number. That's what it means for $f$ to be a function. $\endgroup$ – bof Sep 21 '17 at 0:13
  • 1
    $\begingroup$ @bof: that is true, but in the naturals there is no other pair $(x',y')$ that results in the same value of $f$. In the naturals, given a value $f(x,y)$ you can uniquely determine $x$ and $y$. That is not true in the reals, which was what OP asked. I demonstrated a case where you cannot determine $x$ and $y$ from $f(x,y)$ $\endgroup$ – Ross Millikan Sep 21 '17 at 0:21
2
$\begingroup$

A function on two variables $x$ and $y$ is called a polynomial function if it is defined by a formula built up from $x$, $y$ and numeric constants (like $0, 1, 2, \ldots$) using addition,multiplication. So Cantor's pairing function is a polynomial function.

If $f(x, y)$ is a polynomial function, then $f$ cannot be an injection of $\Bbb{R}\times\Bbb{R}$ into $\Bbb{R}$ (because of o-minimality).

$\endgroup$
  • $\begingroup$ Ah, interesting thanks. What if I constrain x,y to rational numbers > 0? $\endgroup$ – Devin King Sep 20 '17 at 20:42
  • $\begingroup$ Constraining $x$ and $y$ to rational numbers won't help. $\endgroup$ – Rob Arthan Sep 20 '17 at 20:48
0
$\begingroup$

Observe that $f(-1,1)=f(-2,1)$

$\endgroup$
  • 1
    $\begingroup$ Thank you. I should mention I actually only care for real values > 0. I will edit the question accordingly. $\endgroup$ – Devin King Sep 20 '17 at 20:02
  • $\begingroup$ $-1$ and $-2$ are not natural numbers. $\endgroup$ – Peter Sep 20 '17 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.