Cantor Pairing Function Website Links For
Function 		 

Information About

Cantor Pairing Function
  CATEGORIES ABOUT PAIRING FUNCTION
   
set theory
   
APPAREL
BABY
BEAUTY
BOOKS
CAR TOYS
CELL PHONES
DVD'S
ELECTRONICS
GOURMET FOOD
GROCERIES
HEALTH & PERSONAL
HOME & GARDEN
JEWELRY
MUSIC
MUSIC INSTRUMENTS
OFFICE PRODUCTS
SOFTWARE
SPORTING GOODS
TOOLS & HARDWARE
TOYS
VIDEO GAMES
SHOPPING HOME
MORE SHOPPING...



Any pairing function can be used in Set Theory to prove that Integer s and Rational Number s have the same Cardinality as natural numbers. In Theoretical Computer Science they are used to encode a function defined on a vector of natural numbers ''f'':N''k'' → N into a new function ''g'':N → N.

Every pairing function is Primitive Recursive .


DEFINITION

A pairing function is a Bijective function
:\pi:\mathbb{N} imes \mathbb{N} o \mathbb{N}.


CANTOR PAIRING FUNCTION


The Cantor pairing function is a pairing function
:\pi:\mathbb{N} imes \mathbb{N} o \mathbb{N}
defined by
:\pi(k_1,k_2) := rac{1}{2}(k_1 + k_2)(k_1 + k_2 + 1)+k_2.

When we apply the pairing function to k_1 and k_2 we often denote the resulting number as \langle k_1, k_2 angle

This definition can be inductively generalized to the Cantor tuple function
:\pi^{(n)}:\mathbb{N}^n o \mathbb{N}
as
:\pi^{(n)}(k_1, \ldots, k_{n-1}, k_n) := \pi ( \pi^{(n-1)}(k_1, \ldots, k_{n-1}) , k_n)


Inverting the Cantor pairing function

Suppose we are given ''z'' with
: z = \langle x, y angle = rac{(x + y)(x + y + 1)}{2} + y

and we want to find ''x'' and ''y''. It is helpful to define some intermediate values in the calculation:
: w = x + y \!
: t = rac{w(w + 1)}{2} = rac{w^2 + w}{2}
: z = t + y \!

where ''t'' is the Triangle Number of ''w''. If we solve the quadratic equation
: w^2 + w - 2t = 0 \!

for ''w'' as a function of ''t'', we get
: w = rac{\sqrt{8t + 1} - 1}{2}

which is a strictly increasing and continuous function when ''t'' is non-negative real. Since
: t \leq z = t + y < t + (w + 1) = rac{(w + 1)^2 + (w + 1)}{2}

we get that
: w \leq rac{\sqrt{8z + 1} - 1}{2} < w + 1

and thus
: w = \left\lfloor rac{\sqrt{8z + 1} - 1}{2} ight floor .

So to calculate ''x'' and ''y'' from ''z'', we do:
: w = \left\lfloor rac{\sqrt{8z + 1} - 1}{2} ight floor
: t = rac{w^2 + w}{2}
: y = z - t \!
: x = w - y \!.

Since the Cantor pairing function is invertible, it must be one-to-one and onto.


REFERENCES