Definition
Pairing Function
A pairing function is a bijection
. That is, it encodes an ordered pair of natural numbers as a single natural number such that implies and . A common example is the Cantor pairing function:
Pairing functions are used in Gödel numbering and in proofs of countability (e.g. showing
is countable).