Editing Pairing function (section)

== Other pairing functions ==
The function <math>P_2(x, y):= 2^x(2y + 1) - 1</math> is a pairing function.

In 1990, Regan proposed the first known pairing function that is computable in [[linear time]] and with constant space (as the previously known examples can only be computed in linear time if [[Fast multiplication|multiplication can be too]], which is doubtful). In fact, both this pairing function and its inverse can be computed with finite-state transducers that run in real time.{{Clarify|date=August 2021}} In the same paper, the author proposed two more monotone pairing functions that can be [[Online algorithm|computed online]] in linear time and with [[logarithmic space]]; the first can also be computed offline with zero space.{{sfn|Regan|1992}}{{Clarify|reason=What is "zero space"?|date=August 2021}}

In 2001, Pigeon proposed a pairing function based on [[bit-interleaving]], defined recursively as:

:<math>\langle i,j\rangle_{P}=\begin{cases}
T & \text{if}\ i=j=0;\\
\langle\lfloor i/2\rfloor,\lfloor j/2\rfloor\rangle_{P}:i_0:j_0&\text{otherwise,}
\end{cases}</math>

where <math>i_0</math> and <math>j_0</math> are the [[Least Significant Bit|least significant bits]] of ''i'' and ''j'' respectively.{{sfn|Pigeon|loc=Equation 12}}{{bsn|date=November 2024}}

In 2006, Szudzik proposed a "more elegant" pairing function defined by the expression:
:<math>\operatorname{ElegantPair}[x, y] := \begin{cases}
y^2 + x&\text{if}\ x < y,\\
x^2 + x + y&\text{if}\ x \ge y.\\
\end{cases}</math>
Which can be unpaired using the expression:
:<math>\operatorname{ElegantUnpair}[z] := \begin{cases}
\left\{ z - \lfloor\sqrt{z}\rfloor^2, \lfloor\sqrt{z}\rfloor \right\}
& \text{if }z - \lfloor\sqrt{z}\rfloor^2 < \lfloor\sqrt{z}\rfloor,
\\
\left\{ \lfloor\sqrt{z}\rfloor, z - \lfloor\sqrt{z}\rfloor^2 - \lfloor\sqrt{z}\rfloor \right\}
& \text{if }z - \lfloor\sqrt{z}\rfloor^2\geq\lfloor\sqrt{z}\rfloor.
\end{cases}</math>
(Qualitatively, it assigns consecutive numbers to pairs along the edges of squares.) This pairing function orders [[SK combinator calculus]] expressions by depth.{{sfn|Szudzik|2006}}{{Clarify|date=August 2021}}
This method is the mere application to <math>\N</math> of the idea, found in most textbooks on Set Theory,<ref>See for instance {{harvtxt|Jech|2006|p=30}}.</ref>
used to establish <math>\kappa^2=\kappa</math> for any infinite cardinal <math>\kappa</math> in [[Zermelo–Fraenkel set theory|ZFC]].
Define on <math>\kappa\times\kappa</math> the binary relation
:<math>(\alpha,\beta)\preccurlyeq(\gamma,\delta) \text{ if either } \begin{cases}
(\alpha,\beta) = (\gamma,\delta),\\[4pt]
\max(\alpha,\beta) < \max(\gamma,\delta),\\[4pt]
\max(\alpha,\beta) = \max(\gamma,\delta)\ \text{and}\ \alpha<\gamma,\text{ or}\\[4pt]
\max(\alpha,\beta) = \max(\gamma,\delta)\ \text{and}\ \alpha=\gamma\ \text{and}\ \beta<\delta.
\end{cases}</math>
<math>\preccurlyeq</math> is then shown to be a well-ordering such that every element has <math>{}<\kappa</math> predecessors, which implies that <math>\kappa^2=\kappa</math>.
It follows that <math>(\N\times\N,\preccurlyeq)</math> is isomorphic to <math>(\N,\leqslant)</math> and the pairing function above is nothing more than the enumeration of integer couples in increasing order.{{efn|See also [[Talk:Tarski's theorem about choice#Proof of the converse]].}}