Pairing function
A pairing function in mathematics is a bijection from the Cartesian product \mathbb{N} \times \mathbb{N} to \mathbb{N}, providing a computable way to encode any pair of natural numbers (x, y) as a unique single natural number z, with an inverse that decodes z back to (x, y). This construction demonstrates that the set of pairs of natural numbers has the same cardinality as the natural numbers themselves.[1] The concept was introduced by Georg Cantor in 1878 as part of his work on the theory of infinite sets, where he used it to establish the countability of the rational numbers by first pairing natural numbers and then mapping positive rationals via reduced fractions.[2] Cantor's original pairing function is given by \pi(x, y) = \frac{1}{2}(x + y)(x + y + 1) + y, a quadratic polynomial that enumerates pairs along diagonals in the \mathbb{N} \times \mathbb{N} grid. Pairing functions exhibit key properties such as computability and polynomial growth, with many variants existing, including those based on n-adic valuations or characteristic functions, forming infinite families of bijections. They generalize to n-tupling functions, which bijectively encode n-tuples of natural numbers into a single natural number using higher-degree polynomials, as shown in extensions of Cantor's work.[2] Notable examples include the shifted Cantor function and Fueter's polynomial pairings, which maintain bijectivity while optimizing for specific computational needs.[2] These functions have broad applications in mathematics and computer science, including proving cardinality equalities in set theory—such as between natural numbers and rationals—and in computability theory for Gödel numbering, where they encode sequences of symbols (like logical formulas or Turing machine descriptions) into single integers for diagonalization arguments.[1][3] In proof theory and recursion theory, pairing enables the effective enumeration of recursive functions and ordinals, facilitating constructions in models of set theory.[4]Fundamentals
Definition
In mathematics, the natural numbers \mathbb{N} are typically the set of nonnegative integers \{0, 1, 2, \dots\} in the context of pairing functions, though some conventions start from 1; the bijection holds regardless, with minor index adjustments.[5] The Cartesian product \mathbb{N} \times \mathbb{N} consists of all ordered pairs (x, y) where x, y \in \mathbb{N}. A bijection is a function that is both injective (one-to-one, mapping distinct elements to distinct elements) and surjective (onto, covering every element in the codomain).[5] A pairing function \pi: \mathbb{N} \times \mathbb{N} \to \mathbb{N} is a bijection that uniquely encodes any ordered pair (x, y) of natural numbers into a single natural number z = \pi(x, y), with the property that the original pair can be recovered from z via an inverse function.[5] In general form, any function satisfying both injectivity and surjectivity for this mapping qualifies as a pairing function, enabling the demonstration that the cardinality of \mathbb{N} \times \mathbb{N} equals that of \mathbb{N}, both countably infinite.[5] The concept of using pairings to prove countability was first introduced by Georg Cantor in 1873 as part of his proof that the rational numbers \mathbb{Q} are countable, by constructing a bijection between \mathbb{Q} and \mathbb{N} via pairings of numerators and denominators in reduced fractions; the explicit polynomial formula appeared in his 1878 work.[6][2] This established the countability of countable unions of countable sets, a foundational result in set theory. The Cantor pairing function serves as the canonical example.[5]Properties
Pairing functions are defined as bijective mappings from the Cartesian product of the natural numbers with itself, \mathbb{N} \times \mathbb{N}, to the natural numbers \mathbb{N}, and thus exhibit both injectivity and surjectivity as fundamental properties.[7] Injectivity ensures that distinct pairs (x_1, y_1) and (x_2, y_2) map to distinct natural numbers, i.e., \pi(x_1, y_1) = \pi(x_2, y_2) implies (x_1, y_1) = (x_2, y_2), guaranteeing unique encoding without collisions. For the canonical Cantor pairing function, this can be established by noting that pairs are grouped by the sum k = x + y along antidiagonals, where the value \pi(x, y) = \frac{1}{2}(k)(k+1) + y is strictly increasing within each diagonal (for fixed k) and across diagonals (as the starting value of diagonal k+1 exceeds the ending value of diagonal k); thus, equal outputs force equal sums and positions within the sum, yielding equal pairs.[8] Surjectivity guarantees that every natural number z \in \mathbb{N} is the image of exactly one pair, often achieved through a diagonal enumeration that systematically covers all pairs without omission or repetition, akin to Cantor's diagonal argument for countability. To see this for the Cantor function, given z, identify the largest k such that the triangular number \frac{1}{2}k(k+1) \leq z; then set y = z - \frac{1}{2}k(k+1) and x = k - y, yielding \pi(x, y) = z.[8] This property, combined with injectivity, confirms the bijection essential for encoding purposes.[7] Pairing functions are computable and, more specifically, primitive recursive, meaning they can be constructed from basic functions (zero, successor, projection) via composition and primitive recursion, enabling efficient evaluation and inversion in formal systems of arithmetic.[9] This computability underpins their utility in computability theory, such as in Gödel numbering for encoding sequences.[10] The growth rate of a pairing function \pi(x, y) is asymptotically O((x + y)^2), as the output scales quadratically with the magnitude of the inputs due to the antidiagonal structure, providing a bound on the encoded value relative to the pair's "size."[7] This quadratic behavior balances compactness and computability, though variants may optimize for specific applications like spatial indexing.[7] While numerous pairing functions exist, they are unique up to equivalence under permutations of \mathbb{N}, meaning any two bijections \pi and \sigma satisfy \pi = \tau \circ \sigma for some permutation \tau: \mathbb{N} \to \mathbb{N}, preserving their structural role in enumerating pairs. The Fueter–Pólya theorem further specifies that the only quadratic polynomial pairing functions are the Cantor polynomial and its symmetric twin, highlighting a form of uniqueness among polynomial variants.[7][11]Cantor Pairing Function
Formula
The standard Cantor pairing function, defined for non-negative integers x, y \in \mathbb{N}_0 = \{0, 1, 2, \dots \}, is given by \pi(x, y) = \frac{(x + y)(x + y + 1)}{2} + y. [12][8] When natural numbers are indexed starting from 1, an adjusted form is used: \pi(x, y) = \frac{(x + y - 2)(x + y - 1)}{2} + x, for x, y \in \mathbb{N} = \{1, 2, 3, \dots \}.[5] Geometrically, the function enumerates ordered pairs (x, y) by traversing antidiagonals in the first quadrant of the plane, where each antidiagonal consists of points with constant sum k = x + y for k = 0, 1, 2, \dots, and within each antidiagonal, points are ordered by increasing y (or equivalently, decreasing x); the position of (x, y) is then the y-th point along the k-th antidiagonal, offset by the total number of prior points, which is the triangular number T_k = \frac{k(k+1)}{2}.[8] Bijectivity of \pi follows from its injectivity and surjectivity. For injectivity, if \pi(x, y) = \pi(x', y'), then \frac{(x + y)(x + y + 1)}{2} = \frac{(x' + y')(x' + y' + 1)}{2}, implying x + y = x' + y' =: k, and thus y = y' (hence x = x') since the offsets along the diagonal are distinct. For surjectivity, given any z \in \mathbb{N}_0, select the largest k such that T_k \leq z; set y = z - T_k and x = k - y, yielding \pi(x, y) = z.[8]Derivation
The derivation of the Cantor pairing function relies on a systematic enumeration of the pairs of nonnegative integers (x, y) \in \mathbb{N}_0 \times \mathbb{N}_0 by traversing the Cartesian plane along antidiagonals, where each antidiagonal consists of all pairs satisfying x + y = k for k = 0, 1, 2, \dots. This approach establishes a bijection with \mathbb{N}_0 by assigning natural numbers in a sequential order that covers every pair exactly once. For each fixed k, the antidiagonal contains exactly k + 1 pairs: (k, 0), (k-1, 1), \dots, (0, k). These are ordered within the antidiagonal by increasing the second coordinate y from 0 to k (equivalently, decreasing x from k to 0). The antidiagonals themselves are processed in order of increasing k, starting from k = 0.[8] The starting position of the antidiagonal for k in the overall enumeration is the total number of pairs from all previous antidiagonals, which is the sum of their sizes: \sum_{i=0}^{k-1} (i + 1) = \sum_{j=1}^{k} j = \frac{k(k + 1)}{2}. This is the k-th triangular number T_k. For a pair (x, y) with s = x + y = k, its position within the antidiagonal is the offset from the start, given by y, since the ordering begins at (k, 0) (offset 0) and proceeds to (k-1, 1) (offset 1), up to (0, k) (offset k). Combining these, the unique index assigned to (x, y) is the starting position of its antidiagonal plus the offset: \pi(x, y) = \frac{(x + y)(x + y + 1)}{2} + y. This formula yields a bijection \pi: \mathbb{N}_0 \times \mathbb{N}_0 \to \mathbb{N}_0.[8] This construction originated with Georg Cantor in 1878, as part of his work demonstrating the countability of the rationals via a similar diagonal enumeration of positive fractions.[1]Inversion
To invert the Cantor pairing function and recover the original pair (x, y) from a given z = \pi(x, y) = \frac{(x + y)(x + y + 1)}{2} + y, first solve for the sum w = x + y as the largest integer satisfying \frac{w(w + 1)}{2} \leq z < \frac{(w + 1)(w + 2)}{2}. This w is given by the formula w = \left\lfloor \frac{-1 + \sqrt{1 + 8z}}{2} \right\rfloor, which derives from solving the quadratic inequality for the triangular numbers underlying the pairing.[1] Once w is obtained, compute the offset y = z - \frac{w(w + 1)}{2} and then x = w - y.[1] The step-by-step algorithm proceeds as follows:- Approximate w using the quadratic formula above, typically via floating-point square root computation for large z.
- Verify and adjust w by checking that \frac{w(w + 1)}{2} \leq z < \frac{(w + 1)(w + 2)}{2}; if necessary, decrement w by 1 and recheck, as the approximation error is bounded.
- Compute the triangular number T_w = \frac{w(w + 1)}{2}.
- Set y = z - T_w.
- Set x = w - y.
Examples
To illustrate the Cantor pairing function, consider its application to small nonnegative integers, which enumerates pairs along antidiagonals in the grid of natural numbers, starting from the origin and moving northeast. The function maps each pair (x, y) to a unique z = π(x, y) = \frac{(x + y)(x + y + 1)}{2} + y.[14] The following table shows the pairing values for small x and y, highlighting the first few antidiagonals (constant x + y):| x \ y | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 2 | 5 | 9 |
| 1 | 1 | 4 | 8 | |
| 2 | 3 | 7 | ||
| 3 | 6 |
Arrows would connect 0 → 1 → 2 (skipping to next diagonal) → 3 → 4 → 5, and so on, filling the plane without gaps or overlaps.[14] Special cases along the axes simplify the formula. For x = 0, π(0, y) = \frac{y(y + 3)}{2}, as seen in values like π(0, 0) = 0, π(0, 1) = 2, π(0, 2) = 5. For y = 0, π(x, 0) = \frac{x(x + 1)}{2}, yielding π(0, 0) = 0, π(1, 0) = 1, π(2, 0) = 3, π(3, 0) = 6, which are the triangular numbers themselves. These follow from substituting into the general formula.[14]y\x 0 1 2 3 0 0 1 3 6 1 4 7 2 5 8 3 9y\x 0 1 2 3 0 0 1 3 6 1 4 7 2 5 8 3 9