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 .
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 singledigit functions and you know that the results obtained apply to all (including multidigit) number functions.
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 .
^  . . . . . . . . . . . . . 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 . ~ xxxxxxxxxxxx. > = xxxxxxxxxxxx. >
als zweidimensionales Gitter 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
 ,
where one lets the natural numbers start at 0.
Short form:
encodes the pair
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 .
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
using the pairing function by:
and
The functions are called Cantor tuple functions.
Short form:
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 singledigit 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 :
Formal definition
Their inverse is written componentwise as , where:
by virtue of projection
 ,
which selects the th component from a tuple of length .
In the case of pairs (the case ), write and , so that the inverse of the pairing function can be written as.
With the auxiliary functions ( triangular number )
and
or (rounded triangle root )
you can and as follows for calculating:
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 ):
j
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:
Now you can use:
So this can be easily verified using the sketch above.
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:
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 :
procedure CantorPair(I : Integer; Var X,Y : Integer);
{ Gibt das ite 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.
Predictability
The Cantor pairing function is a total , bijective , calculable (even primitiverecursive ) 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 .
The following twodigit machine calculates the Cantor pairing function :
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.
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 onedigit functions of . For functions of , the computability follows through the application of the Cantor pairing function and its inverse function:
 is predictable
exactly when there is a calculable function with
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.
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.
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 .
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 :
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 :
 0 1 2 3 4 y
+>
0  1 3 5 7 .
1  2 6 10 14 .
2  4 12 20 28 .
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 .
The prime factorization gives a possibility to encode arbitrary finite tuples of natural numbers by natural numbers:
Example:
literature
 Klaus Weihrauch: Computability. Springer, Berlin a. a. 1987, ISBN 3540137211 ( 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 3540426248 , p. 263 f. (Springer textbook).
 Uwe Schöning : Theoretical Computer Science  in a nutshell. 4th edition. Corrected reprint. Spectrum, Heidelberg a. a. 2003, ISBN 3827410991 , p. 111 f. (University paperback).
Individual evidence
 ↑ Christoph Michel: Enumerating a Grid in Spiral Order. In: cmichel.io blog. September 7, 2016, accessed September 7, 2016 .