= Primitive recursive pairing function
{title2=$\langle x,y\rangle$}
A <primitive recursive pairing function> is a <pairing function> whose encoding <function> and both coordinate <functions> of its <inverse function> are <primitive recursive functions>. Thus the <bijection> can be used in either direction inside a construction by <primitive recursion> and <function composition in recursion theory>. A decoder that is merely a <computable function> would not establish this stronger closure property. Sutner's definition of a primitive recursive pairing system explicitly includes the decoding <functions>; his more general systems need only be <injective>, whereas a <pairing function> here is a <bijection>.https://www.cs.cmu.edu/~cdm/resources/02-coding.pdf[Klaus Sutner, Primitive Recursion, slide 9: primitive recursive encoding and unpairing functions]{ref}
The <Cantor pairing function> is a <primitive recursive pairing function>. For its encoding, construct the <triangular numbers> directly by <primitive recursion>:
$$
T(0)=0,\qquad T(s+1)=T(s)+s+1,\qquad \pi(x,y)=T(x+y)+y.
$$
Since <addition> is <primitive recursive>, so are $T$ and $\pi$ by <primitive recursion> and <function composition in recursion theory>. This establishes the claim without treating <division> by two as an unexplained primitive operation.
For decoding, use <bounded minimization> to define
$$
s(z)=\min\{t\in\mathbb N_0:t\leq z\ \text{and}\ z<T(t+1)\}.
$$
The bound is valid for every <natural number> $z$: $T(z+1)=(z+1)(z+2)/2>z$, so the candidate $t=z$ always succeeds. The search includes zero; when $z=0$, it immediately returns $s(0)=0$. If $s(z)>0$, the preceding candidate failed, which gives $T(s(z))\leq z$; when $s(z)=0$, that lower <inequality> follows from $T(0)=0$. Thus this search finds exactly the diagonal in the <Cantor pairing function> inverse, with
$$
T(s(z))\leq z<T(s(z)+1).
$$
The comparison is <primitive recursive>, and <bounded minimization> of a <primitive recursive> predicate is <primitive recursive>. Therefore $s$ is a <primitive recursive function>. Recover the coordinates by
$$
R(z)=z-T(s(z)),\qquad L(z)=s(z)-R(z).
$$
In constructions on the <natural numbers>, implement these <subtractions> using the <primitive recursive> operation $a\mathbin{\dot{-}}b=\max(a-b,0)$: apply the <predecessor function> $b$ times to $a$ by <primitive recursion>. On these inputs it agrees with ordinary <subtraction>, since the diagonal <inequalities> imply $0\leq R(z)\leq s(z)$. Consequently $L$ and $R$ are <primitive recursive functions>, and $\pi(L(z),R(z))=z$. Zimmermann proves the relevant closure under <bounded minimization> and the primitive recursive character of the Cantor encoding and coordinate decoding; his convention adds the first coordinate, so its coordinates are exchanged relative to $\pi$ here.https://tore.tuhh.de/bitstream/11420/1312/1/book.pdf[Karl-Heinz Zimmermann, Computability Theory, §2.3, Proposition 2.26 and Propositions 2.32–2.34, printed pages 18 and 21–22]{ref}
For a worked <bounded minimization>, take $z=18$. Candidates $t=0,1,2,3,4$ give $T(t+1)=1,3,6,10,15$, none exceeding $18$. Candidate $t=5$ gives $T(6)=21>18$, so $s(18)=5$, $R(18)=3$, and $L(18)=2$. The search bound was $18$; it terminates much earlier in this example. The bound proves membership in the <primitive recursive functions>; it is not a claim that scanning all candidates is the fastest implementation.
For each fixed $k\geq1$, define a <tuple> encoder by
$$
E_1(a_1)=a_1,\qquad E_{k+1}(a_1,\ldots,a_{k+1})=\pi(E_k(a_1,\ldots,a_k),a_{k+1}).
$$
Each $E_k$ and each coordinate decoder is <primitive recursive>, by finitely many applications of <function composition in recursion theory> to $\pi,L,R$. For the three-entry <tuple> encoded as $257$, applying $R$ returns $4$, applying $L$ returns $18$, and then $L(18)=2$, $R(18)=3$. The <tuple> length remains part of the agreed convention, as explained for a general <pairing function>.
This makes <primitive recursive pairing functions> useful for encoding several evolving values as one state in <primitive recursion>. For example, store consecutive <Fibonacci numbers> as $c(0)=\pi(0,1)$ and update by
$$
c(n+1)=\pi(R(c(n)),L(c(n))+R(c(n))).
$$
The codes start $2,4,8,18$, decoding to $(0,1),(1,1),(1,2),(2,3)$. Every step uses <primitive recursive> encoding, decoding and <addition>; a single numerical state therefore carries the two values needed for the next step. This is also the reason a suitable <Gödel numbering> should permit sufficiently simple decoding: representation should preserve the class of <functions> being studied.
Back to article page
