Pairing Functions
A pairing function is a function that encodes two natural numbers into one natural number.
Formal Definition
f : ℕ × ℕ → ℕ
Properties
- Transformation of vectors into numbers, recursively
- Injectivity
- Surjectivity, and thus, bijectivity, when invertible
Some Pairing Functions
- Cantor pairing function
- Szudzik’s elegant pairing function
- Gödel numbering