Pairing function

In mathematics, a pairing function is a process to uniquely encode two natural numbers into a single natural number. Any pairing function can be used in set theory to prove that integers and rational numbers have the same cardinality as natural numbers. A pairing function is a bijection More generally, a pairing function on a set A is a function that maps each pair of elements from A into an element of A, such that any two pairs of elements of A are associated with different elements of A, or a bijection from to A. Hopcroft and Ullman (1979) define the following pairing function: , where . This is the same as the Cantor pairing function below, shifted to exclude 0 (i.e., , , and ). The Cantor pairing function is a primitive recursive pairing function defined by where . It can also be expressed as . It is also strictly monotonic w.r.t. each argument, that is, for all , if , then ; similarly, if , then . The statement that this is the only quadratic pairing function is known as the Fueter–Pólya theorem. Whether this is the only polynomial pairing function is still an open question. When we apply the pairing function to k1 and k2 we often denote the resulting number as ⟨k1, k2⟩. This definition can be inductively generalized to the for as with the base case defined above for a pair: Let be an arbitrary natural number. We will show that there exist unique values such that and hence that the function π(x, y) is invertible. It is helpful to define some intermediate values in the calculation: where t is the triangle number of w. If we solve the quadratic equation for w as a function of t, we get which is a strictly increasing and continuous function when t is non-negative real. Since we get that and thus where ⌊ ⌋ is the floor function. So to calculate x and y from z, we do: Since the Cantor pairing function is invertible, it must be one-to-one and onto. To calculate π(47, 32): 47 + 32 = 79, 79 + 1 = 80, 79 × 80 = 6320, 6320 ÷ 2 = 3160, 3160 + 32 = 3192, so π(47, 32) = 3192. To find x and y such that π(x, y) = 1432: 8 × 1432 = 11456, 11456 + 1 = 11457, = 107.