Cantorparingfunksjon

The Cantor pairing function is a computable bijection from the set of pairs of natural numbers to the set of natural numbers. It was invented by Georg Cantor. The function, often denoted by $\pi(k_1, k_2)$, takes two non-negative integers $k_1$ and $k_2$ and returns a unique non-negative integer. This means that every possible pair of natural numbers can be represented by a distinct natural number, and conversely, every natural number corresponds to exactly one pair of natural numbers.

The standard formula for the Cantor pairing function is $\pi(k_1, k_2) = \frac{1}{2}(k_1 + k_2)(k_1 + k_2 + 1) + k_2$. This formula ensures that the mapping is one-to-one and onto. For example, $\pi(0, 0) = 0$, $\pi(0, 1) = 1$, $\pi(1, 0) = 2$, $\pi(0, 2) = 3$, $\pi(1, 1) = 4$, and $\pi(2, 0) = 5$. The function is often used in computer science and set theory to demonstrate that the set of pairs of natural numbers has the same cardinality as the set of natural numbers itself, which is a countably infinite set.

The inverse functions, which recover the original pair from a given natural number, are also computable. Given a natural number $z$, one can find $k_1$ and $k_2$ such that $\pi(k_1, k_2) = z$. This property makes the Cantor pairing function useful for problems involving encoding and decoding pairs of numbers into a single number.