Editing Pairing function (section)

=== Derivation ===
[[File:Diagonal argument.svg|thumb|right|170px|A diagonally incrementing "snaking" function, from same principles as Cantor's pairing function, is often used to demonstrate the countability of the rational numbers.]]

The graphical shape of Cantor's pairing function, a diagonal progression, is a standard trick in working with [[infinite sequence]]s and [[countability]].{{efn|The term "diagonal argument" is sometimes used to refer to this type of enumeration, but it is ''not'' directly related to [[Cantor's diagonal argument]].{{citation needed|date=August 2021}}}} The algebraic rules of this diagonal-shaped function can verify its validity for a range of polynomials, of which a quadratic will turn out to be the simplest, using the [[method of induction]]. Indeed, this same technique can also be followed to try and derive any number of other functions for any variety of schemes for enumerating the plane.

A pairing function can usually be defined inductively – that is, given the {{math|''n''}}th pair, what is the {{math|(''n''+1)}}th pair? The way Cantor's function progresses diagonally across the plane can be expressed as
:<math>\pi(x,y)+1 = \pi(x-1,y+1)</math>.

The function must also define what to do when it hits the boundaries of the 1st quadrant – Cantor's pairing function resets back to the x-axis to resume its diagonal progression one step further out, or algebraically:
:<math>\pi(0,k)+1 = \pi(k+1,0)</math>.

Also we need to define the starting point, what will be the initial step in our induction method: {{math|''π''(0, 0) {{=}} 0}}.

Assume that there is a quadratic 2-dimensional polynomial that can fit these conditions (if there were not, one could just repeat by trying a higher-degree polynomial). The general form is then
:<math>\pi(x,y) = ax^2+by^2+cxy+dx+ey+f</math>.

Plug in our initial and boundary conditions to get {{math|''f'' {{=}} 0}} and:
:<math>bk^2+ek+1 = a(k+1)^2+d(k+1)</math>,

so we can match our {{math|''k''}} terms to get
:{{math|''b'' {{=}} ''a''}}
:{{math|''d'' {{=}} 1-''a''}}
:{{math|''e'' {{=}} 1+''a''}}.

So every parameter can be written in terms of {{math|''a''}} except for {{math|''c''}}, and we have a final equation, our diagonal step, that will relate them:
:<math>\begin{align}
  \pi(x,y)+1 &= a(x^2+y^2) + cxy + (1-a)x + (1+a)y + 1 \\
    &= a((x-1)^2+(y+1)^2) + c(x-1)(y+1) + (1-a)(x-1) + (1+a)(y+1).
  \end{align}</math>

Expand and match terms again to get fixed values for {{math|''a''}} and {{math|''c''}}, and thus all parameters:
:{{math|''a'' {{=}} {{sfrac|1|2}} {{=}} ''b'' {{=}} ''d''}}
:{{math|''c'' {{=}} 1}}
:{{math|''e'' {{=}} {{sfrac|3|2}}}}
:{{math|''f'' {{=}} 0}}.

Therefore
:<math>\begin{align}
  \pi(x,y) &= \frac{1}{2}(x^2+y^2) + xy + \frac{1}{2}x + \frac{3}{2}y \\ 
    &= \frac{1}{2}(x+y)(x+y+1) + y,
  \end{align}</math>

is the Cantor pairing function, and we also demonstrated through the derivation that this satisfies all the conditions of induction.{{Citation needed|date=August 2021}}