Funkcja pary

Funkcja pary – przyporządkowanie służące do jednoznacznego zakodowania pary liczb naturalnych za pomocą pojedynczej liczby naturalnej.

Każda funkcja pary może zostać użyta w teorii mnogości do dowodu, że zbiory liczb całkowitych oraz wymiernych maję tę samą moc co zbiór liczb naturalnych. W teorii rekursji służą one do kodowania funkcji więcej niż jednego argumentu naturalnego ${\displaystyle f\colon \mathbf {N} ^{k}\to \mathbf {N} }$ za pomocą funkcji jednej zmiennej ${\displaystyle g\colon \mathbf {N} \to \mathbf {N} .}$

Funkcją pary jest pierwotnie rekurencyjna bijekcja

${\displaystyle \pi \colon \mathbb {N} \times \mathbb {N} \to \mathbb {N} .}$

(Uwaga: tutaj ${\displaystyle \mathbb {N} =\{0,1,2,3,\dots \}}$)

Funkcja pary Cantora jest funkcją

${\displaystyle \pi \colon \mathbb {N} \times \mathbb {N} \to \mathbb {N} }$

daną wzorem

${\displaystyle \pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}.}$

Wartość otrzymaną przez zastosowanie tej funkcji do liczb ${\displaystyle k_{1}}$ i ${\displaystyle k_{2}}$ często oznacza się jako ${\displaystyle \langle k_{1},k_{2}\rangle .}$

Definicja ta może być indukcyjnie rozszerzana do funkcji krotkowej Cantora

${\displaystyle \pi ^{(n)}\colon \mathbb {N} ^{n}\to \mathbb {N} }$

następująco

${\displaystyle \pi ^{(n)}(k_{1},\dots ,k_{n-1},k_{n}):=\pi (\pi ^{(n-1)}(k_{1},\dots ,k_{n-1}),k_{n}).}$

Niech dane będzie ${\displaystyle z}$ jako

${\displaystyle z=\langle x,y\rangle ={\frac {(x+y)(x+y+1)}{2}}+y}$

i powiedzmy, że chcemy znaleźć ${\displaystyle x}$ i ${\displaystyle y.}$

Zdefiniujmy pomocniczo:

${\displaystyle w=x+y,}$

${\displaystyle t={\frac {w(w+1)}{2}}={\frac {w^{2}+w}{2}},}$

${\displaystyle z=t+y,}$

gdzie ${\displaystyle t}$ jest ${\displaystyle w}$-tą liczbą trójkątną.

Rozwiązując równanie:

${\displaystyle w^{2}+w-2t=0}$

z ${\displaystyle w}$ jako funkcją parametru ${\displaystyle t,}$ dostaniemy:

${\displaystyle w={\frac {{\sqrt {8t+1}}-1}{2}},}$

co jest ściśle rosnące i ciągłe dla nieujemnego rzeczywistego ${\displaystyle t.}$

Skoro

${\displaystyle t\leqslant z=t+y<t+(w+1)={\frac {(w+1)^{2}+(w+1)}{2}},}$

dostajemy

${\displaystyle w\leqslant {\frac {{\sqrt {8z+1}}-1}{2}}<w+1,}$

skąd

${\displaystyle w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor .}$

Tak więc, aby wyznaczyć ${\displaystyle x}$ i ${\displaystyle y}$ z ${\displaystyle z,}$ postępujemy następująco:

${\displaystyle w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor ,}$

${\displaystyle t={\frac {w^{2}+w}{2}},}$

${\displaystyle y=z-t,}$

${\displaystyle x=w-y.}$

Skoro funkcja Cantora jest odwracalna, musi być różnowartościowa i na.

• Steven Pigeon, „Pairing function” z serwisu MathWorld.