Editing Pairing function (section)

=== Inverting the Cantor pairing function ===
Let <math>z \in \mathbb{N}</math> be an arbitrary natural number. We will show that there exist unique values <math>x, y \in \mathbb{N}</math> such that

:<math> z = \pi(x, y) = \frac{(x + y + 1)(x + y)}{2} + y </math>

and hence that the function {{math|''π(x, y)''}} is invertible. It is helpful to define some intermediate values in the calculation: 
:<math> w = x + y \!</math>
:<math> t = \frac{1}{2}w(w + 1) = \frac{w^2 + w}{2} </math>
:<math> z = t + y \!</math>

where {{math|''t''}} is the [[triangular number|triangle number]] of {{math|''w''}}. If we solve the [[quadratic equation]] 
:<math> w^2 + w - 2t = 0 \!</math>

for {{math|''w''}} as a function of {{math|''t''}}, we get 
:<math> w = \frac{\sqrt{8t + 1} - 1}{2} </math>

which is a strictly increasing and continuous function when {{math|''t''}} is non-negative real. Since 
:<math> t \leq z = t + y < t + (w + 1) =  \frac{(w + 1)^2 + (w + 1)}{2} </math>

we get that 
:<math> w \leq \frac{\sqrt{8z + 1} - 1}{2} < w + 1 </math>

and thus 
:<math> w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor. </math>
where {{math|⌊ ⌋}} is the [[floor function]].
So to calculate {{math|''x''}} and {{math|''y''}} from {{math|''z''}}, we do:
:<math> w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\rfloor </math>
:<math> t = \frac{w^2 + w}{2} </math>
:<math> y = z - t \!</math>
:<math> x = w - y. \!</math>

Since the Cantor pairing function is invertible, it must be [[injective function|one-to-one]] and [[surjective function|onto]].{{sfn|Szudzik|2006}}{{Additional citation needed|date=August 2021}}