CantorPaarungsfunktion

The Cantor pairing function is a computable bijective (one-to-one and onto) function that maps two natural numbers, say $k$ and $m$, to a single natural number $C(k, m)$. It was introduced by Georg Cantor. The formula for the Cantor pairing function is $C(k, m) = \frac{1}{2}(k + m)(k + m + 1) + m$. This function is significant in set theory and computer science as it demonstrates that the set of all pairs of natural numbers is countable, meaning it can be put into a one-to-one correspondence with the set of natural numbers itself.

The Cantor pairing function has the property that for any two distinct pairs of natural numbers $(k, m)$ and $(k', m')$, $C(k, m) \neq C(k', m')$. Furthermore, for every natural number $n$, there exist unique natural numbers $k$ and $m$ such that $C(k, m) = n$. This bijectivity allows for the encoding of pairs of numbers into a single number, which is useful in various theoretical contexts. For example, it can be used to show that the set of all rational numbers is countable. The inverse of the Cantor pairing function, which maps a single natural number back to its original pair, can also be computed.