Cantorsche Paarungsfunktion

Die Cantorsche Paarungsfunktion (manchmal auch Nummerierungsfunktion) ist eine unter anderem in der theoretischen Informatik verwendete Abbildung, die auf dem Diagonalargument von Cantor basiert.

Mit ihr kann man ein beliebiges Paar natürlicher Zahlen durch eine einzige natürliche Zahl darstellen. Man nummeriert damit alle Zahlenpaare. Diese Nummerierung ist sogar eindeutig umkehrbar. Das heißt, man kann aus der Zahl das ursprüngliche Zahlenpaar wieder ermitteln. Mathematisch gesprochen heißt das: Die Cantorsche Paarungsfunktion ist eine bijektive totale Funktion .

Die Idee der diagonalen Abzählung der Menge aller Paare natürlicher Zahlen geht auf Georg Cantor zurück.Die Verallgemeinerung der Cantorschen Paarungsfunktion von Paaren auf Tupel wird als Cantorsche Tupelfunktion bezeichnet.