Cantor pairing function

The Cantor pairing function (sometimes also numbering function) is a mapping used in theoretical computer science , among other things , which is based on Cantor's diagonal argument .

It can be used to represent any pair of natural numbers by a single natural number . This is used to number all pairs of numbers. This numbering is even clearly reversible. This means that you can determine the original pair of numbers from the number . Mathematically speaking, this means: Cantor's pairing function is a bijective total function . ${\displaystyle (x,y)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle (x,y)}$ ${\displaystyle \pi \colon \mathbb {N} ^{2}\to \mathbb {N} }$

The idea of ​​diagonal counting of the set of all pairs of natural numbers goes back to Georg Cantor . The generalization of Cantor's pairing function from pairs to tuples is called Cantor's tuple function .

motivation

In theoretical computer science, the Cantor pairing function or tuple function is used to reduce functions that have more than one parameter to functions that only have exactly one parameter, which makes many proofs much easier.

The tracing of a problem back to a (possibly simpler) known problem is a proven proof technique known as reduction .

With the Cantor pairing function or tuple function, the calculability of - digit number functions can be reduced to the calculability of single digit number functions. This means that when examining the calculability of number functions, you can restrict yourself to examining single-digit functions and you know that the results obtained apply to all (including multi-digit) number functions. ${\displaystyle k}$

Basics

It may not be immediately apparent that it is possible to encode any combination of two numbers by one number: the set of all pairs of numbers seems to be much larger than the set of all numbers . ${\displaystyle \mathbb {N} ^{2}=\mathbb {N} \times \mathbb {N} }$ ${\displaystyle \mathbb {N} }$

^
|
. . . . . . . . . . . . .
x x x x x x x x x x x x .
x x x x x x x x x x x x .
x x x x x x x x x x x x .              ~
x-x-x-x-x-x-x-x-x-x-x-x-. -->          =          x-x-x-x-x-x-x-x-x-x-x-x-. -->

 ${\displaystyle \mathbb {N} \times \mathbb {N} }$ als zweidimensionales Gitter 1234567890123456 ${\displaystyle \mathbb {N} }$ als Menge von Punkten auf dem Zahlenstrahl

The Cantor pairing function shows, however, that both sets are equal, because it creates a 1: 1 relationship, it is a bijection .

A set that can be mapped bijectively onto the natural numbers is called countably infinite; in particular, the natural numbers themselves have this property. The Cantor pairing function then shows that the set of pairs of natural numbers is also countably infinite.

definition

The Cantor pairing function is defined as

${\displaystyle \pi \colon \mathbb {N} _{0}\times \mathbb {N} _{0}\to \mathbb {N} _{0}}$

${\displaystyle (x,y)\mapsto \pi (x,y):=y+\sum _{i=0}^{x+y}i=y+{\frac {1}{2}}(x+y)(x+y+1)}$,

where one lets the natural numbers start at 0.

Short form:

${\displaystyle \langle x,y\rangle =\pi (x,y)=n}$

${\displaystyle n}$ encodes the pair ${\displaystyle (x,y)}$

Here is a sketch of the diagonal counting :

The two values ​​are plotted on the axes, as in a distance table you look up the value of the Cantor pairing function at the point of intersection, for example . ${\displaystyle \langle 1,2\rangle =8}$

The numbering is very simple: One counts the pairs starting diagonally with zero: (0,0), (1,0), (0,1), (2,0), (1,1), (0,2 ) etc.

You can read off the above law of formation directly if you visualize the summation in each case using a column.

Extension to k tuples

Tuples can also be clearly numbered through repeated use . One defines inductively for the functions ${\displaystyle k}$ ${\displaystyle k=1,2,3,\dotsc }$

${\displaystyle \pi ^{(k)}\colon \mathbb {N} ^{k}\to \mathbb {N} }$

using the pairing function by: ${\displaystyle \pi }$

${\displaystyle \pi ^{(1)}(x)=x}$

and

${\displaystyle \pi ^{(k+1)}(x_{1},\dotsc ,x_{k+1})=\pi (\pi ^{(k)}(x_{1},\dotsc ,x_{k}),x_{k+1})}$

The functions are called Cantor tuple functions. ${\displaystyle \pi ^{(k)}}$

Short form:

${\displaystyle \langle x_{1},x_{2},\dotsc ,x_{k}\rangle :=\pi ^{(k)}(x_{1},x_{2},\dotsc ,x_{k})}$

Inverse function

The Cantor pairing function is reversible . The reverse is clear and predictable. The latter is important for the application in theoretical computer science, since the calculability of the function and the inverse function is a condition in order to represent all calculable functions by single-digit functions without problems.

Reversible means that one can deduce the two numbers and for which applies from a number . The inverse function consists of two auxiliary functions and : ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \pi (x,y)=n}$ ${\displaystyle f}$ ${\displaystyle q}$

Formal definition

Their inverse is written component-wise as , where: ${\displaystyle \left(\pi ^{(k)}\right)^{-1}\colon \mathbb {N} \to \mathbb {N} ^{k}}$ ${\displaystyle \pi _{i}^{(k)}\colon \mathbb {N} \to \mathbb {N} }$

${\displaystyle \pi _{i}^{(k)}=\operatorname {pr} _{i}^{(k)}\circ \left(\pi ^{(k)}\right)^{-1}}$

by virtue of projection

${\displaystyle \operatorname {pr} _{i}^{(k)}(x_{1},\dotsc ,x_{k})=x_{i}}$,

which selects the -th component from a tuple of length . ${\displaystyle i}$ ${\displaystyle k}$

In the case of pairs (the case ), write and , so that the inverse of the pairing function can be written as. ${\displaystyle k=2}$ ${\displaystyle \pi _{1}^{(2)}=\pi _{1}}$ ${\displaystyle \pi _{2}^{(2)}=\pi _{2}}$ ${\displaystyle \pi ^{-1}=(\pi _{1},\ \pi _{2})}$

With the auxiliary functions ( triangular number )

${\displaystyle f(w)=\sum _{i=0}^{w}i={\frac {w(w+1)}{2}}}$

and

${\displaystyle q(z)=\max\{v\mid f(v)\leq z\}}$

or (rounded triangle root )

${\displaystyle q(z)=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor }$

you can and as follows for calculating: ${\displaystyle \pi _{1}}$ ${\displaystyle \pi _{2}}$ ${\displaystyle z}$

${\displaystyle \pi _{2}(z)=z-f(q(z))}$

${\displaystyle \pi _{1}(z)=q(z)-\pi _{2}(z)}$

example

Which pair of numbers does the number 17 represent?

To do this, you first determine the greatest natural number for which applies. This can either be determined by trial and error (the table of values ​​from ): ${\displaystyle w}$ ${\displaystyle f(w)\leq 17}$ ${\displaystyle f(w)}$

j 00 0    1    2    3    4    5    6
f(j) 0    1    3    6   10   15   21

or using the rounded formula of the triangle root:

${\displaystyle q(17)=\left\lfloor {\frac {{\sqrt {8\cdot 17+1}}-1}{2}}\right\rfloor =5}$

Now you can use:

${\displaystyle \pi _{2}(17)=17-f(5)=17-{\frac {5(5+1)}{2}}=17-15=2}$

${\displaystyle \pi _{1}(17)=5-2=3}$

So this can be easily verified using the sketch above. ${\displaystyle \langle 3,2\rangle =17.}$

Computer implementations

Implementation of the calculations in Java

With large values ​​of , the time required by the WHILE loop increases enormously, so no loops were used and the variant with the triangle root was implemented instead: ${\displaystyle z}$

  public class Cantor {
    public static long compute(long x, long y) {
      return (x+y)*(x+y+1)/2 + y;
    }
    public static long computeX(long z) {
      long j = (long) Math.floor(Math.sqrt(0.25 + 2*z) - 0.5);
      return j - (z - j*(j+1)/2);
    }
    public static long computeY(long z) {
      long j = (long) Math.floor(Math.sqrt(0.25 + 2*z) - 0.5);
      return z - j*(j+1)/2;
    }
  }

The method compute calculates the number assigned to the transferred pair of numbers (x y) , computeX and computeY are the inverse functions of compute.

Pascal program to calculate the inverse

The following Pascal program calculates the inverse function : ${\displaystyle \pi ^{-1}}$

 procedure CantorPair(I : Integer; Var X,Y : Integer);
 { Gibt das i-te Paar (X,Y) in Diagonalabzaehlung zurueck }
 var
    J : Integer;

    function F(Z : Integer) : Integer;
    begin
       F := (Z * (Z + 1)) div 2
    end;

    function Q(Z : Integer) : Integer;
    var
       V : Integer;
    begin
       V := 0;
       while F(V) <= Z do
          V := V + 1;
       Q := V - 1
    end;

 begin
    J := Q(I);
    Y := I - F(J);
    X := J - Y;
 end;

Note: If the Pascal program is compiled on real computers, it has to live with the limitations of real computers. This means that large values ​​of integer overflows falsify the result. A Pascal program is easier to understand than a register machine. ${\displaystyle z}$

Predictability

The Cantor pairing function is a total , bijective , calculable (even primitive-recursive ) function, so its inverse is also calculable.

Proof of the predictability of the Cantor pairing function

One way to prove that a function is computable is to provide a register engine that computes the function.

This machine you have to register in the function parameters and the register passed. The value of is then obtained in the output register at that point . ${\displaystyle R1}$ ${\displaystyle x}$ ${\displaystyle R2}$ ${\displaystyle y}$ ${\displaystyle R0}$ ${\displaystyle \pi }$ ${\displaystyle (x,y)}$

The following two-digit machine calculates the Cantor pairing function : ${\displaystyle \pi (x,y)={\frac {1}{2}}(x+y)(x+y+1)+y}$

R4 = R1 + R2
R5 = R4 + 1
R4 = R4 * R5
R4 = R4 / 2
R0 = R4 + R2

There is no formal proof that the register machine actually calculates the function: This is obviously recognizable when one compares the functional rule for calculating the Cantor pairing function with the machine.

However, this register machine uses commands that the simple register machine does not know. The simple register machine only knows the operations , and the simple test. ${\displaystyle R+1}$ ${\displaystyle R-1}$

By refining this register machine , however, it can be reduced to a simple register machine.

This means there is a register machine that calculates the Cantor pairing function. Thus the Cantor pairing function can be calculated.

Proof of the computability of the inverse function

For the proof of the inverse function, it is advisable to use another definition of computability:

A function can only be calculated if there is a WHILE program that calculates this function.

The Pascal program given above can be refined into a WHILE program. So there is a WHILE program that calculates the inverse function. Thus, the reversal can also be calculated.

Applying predictability

From the computability of the Cantor pairing function and its inversion it follows that it is sufficient for the theory of computability to deal with one-digit functions of . For functions of , the computability follows through the application of the Cantor pairing function and its inverse function: ${\displaystyle \mathbb {N} \to \mathbb {N} }$ ${\displaystyle \mathbb {N} ^{n}\to \mathbb {N} ^{m}}$

${\displaystyle f\colon \mathbb {N} ^{n}\to \mathbb {N} ^{m}}$ is predictable

exactly when there is a calculable function with ${\displaystyle g\colon \mathbb {N} \to \mathbb {N} }$

${\displaystyle \forall n\in \mathbb {N} ^{n}:f(n):=\pi _{m}^{-1}\left(g\left(\pi _{n}(n)\right)\right).}$

For example, one can show that all rational numbers can be represented by an ordered triplet of natural numbers. With this one can easily extend the computability from the natural numbers to the set of rational numbers. ${\displaystyle (i,j,k)}$

origin

The idea comes from Georg Cantor's set theory . He had the idea of comparing the size of one set ( cardinality , cardinality) with the size of another set by trying to find a 1: 1 mapping ( bijection ) of this set with the other set. Exactly one element of the second set should be assigned to each element of the first set and vice versa. This seems complicated, but it is justified when it comes to sets with an infinite number of elements. See also Galileo's paradox .

With a diagonal counting (as indicated above) it is easy to show that with a countable set the Cartesian product is equal to , which perhaps speaks against intuition, since tuples of different dimensions occur here. ${\displaystyle M}$ ${\displaystyle M\times M=M^{2}=\{(a,b)\mid a,b\in M\}}$ ${\displaystyle M}$

Alternatives

For two neighboring points and on the trajectory of the inverse function can be arbitrarily large, which can be undesirable when using the counting. Therefore, one also considers a variant of Cantor's enumeration, in which always applies and which is continuous in this sense. This form is called the Boustrophedonian Cantor counting, because here the path does not jump from the -axis to the -axis (as shown in the sketch above), but rather turns towards the axes. It is described on OEIS as A319571 . ${\displaystyle (x,y)}$ ${\displaystyle (x',y')}$ ${\displaystyle \max(|x-x'|,|y-y'|)}$ ${\displaystyle \max(|x-x'|,|y-y'|)=1}$ ${\displaystyle y}$ ${\displaystyle x}$

There are many other ways to bijectively encode pairs of natural numbers by a natural number, e.g. B. one can count in a spiral with the formula : ${\displaystyle \max(r,c)^{2}+\max(r,c)+(-1)^{1+\max(r,c){\text{ mod }}2}\cdot (r-c)}$

r \ c	0	1	2	3	4th
0	0	1	8th	9	.
1	3	2	7th	10	.
2	4th	5	6th	11	.
3	15th	14th	13	12	.
4th	.	.	.	.	.

The simple formula also provides a bijection between and : ${\displaystyle 2^{x}\cdot (2y+1)}$ ${\displaystyle {\mathbb {N} }\times {\mathbb {N} }}$ ${\displaystyle {\mathbb {N} }\setminus \{0\}}$

   | 0   1   2   3   4    y
 --+----------------------->
 0 | 1   3   5   7   .
 1 | 2   6  10  14   .
 2 | 4  12  20  28   .          ${\displaystyle z=2^{x}\cdot (2y+1)}$
 3 | 8  24  40  56   .
 4 | .   .   .   .   .
   |
 x v

Proof of reversibility: is the greatest natural number such that is a divisor of , i.e. the number of factors in the prime factorization of . Be . Then is . ${\displaystyle x}$ ${\displaystyle 2^{x}}$ ${\displaystyle z}$ ${\displaystyle 2}$ ${\displaystyle z}$ ${\displaystyle R={\tfrac {z}{2^{x}}}}$ ${\displaystyle y={\tfrac {R-1}{2}}}$

The prime factorization gives a possibility to encode arbitrary finite tuples of natural numbers by natural numbers:

${\displaystyle \langle i_{1},i_{2},i_{3},i_{4},i_{5},\dotsc \rangle =2^{i_{1}}3^{i_{2}}5^{i_{3}}7^{i_{4}}11^{i_{5}}\dotsb }$

Example:

${\displaystyle \langle 2,1,0,1,0,0\rangle =2^{2}3^{1}5^{0}7^{1}11^{0}13^{0}=4\cdot 3\cdot 7=84}$

literature

• Klaus Weihrauch: Computability. Springer, Berlin a. a. 1987, ISBN 3-540-13721-1 ( EATCS monographs on theoretical computer science 9).
• Eric W. Weisstein : Pairing Function . In: MathWorld (English).
• Katrin Erk, Lutz Priese: Theoretical Computer Science. A comprehensive introduction. 2nd expanded edition. Springer, Berlin a. a. 2002, ISBN 3-540-42624-8 , p. 263 f. (Springer textbook).
• Uwe Schöning : Theoretical Computer Science - in a nutshell. 4th edition. Corrected reprint. Spectrum, Heidelberg a. a. 2003, ISBN 3-8274-1099-1 , p. 111 f. (University paperback).

Individual evidence

1. ↑ Christoph Michel: Enumerating a Grid in Spiral Order. In: cmichel.io blog. September 7, 2016, accessed September 7, 2016 .