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 $f:{𝐍}^k\to 𝐍$ za pomocą funkcji jednej zmiennej $g:𝐍\to 𝐍.$

Definicja formalna

Funkcją pary jest pierwotnie rekurencyjna bijekcja

$\pi :\mathbb{N}\times \mathbb{N}\to \mathbb{N}.$

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

Funkcja pary Cantora

Funkcja pary Cantora przyporządkowuje liczbę naturalną dowolnej parze liczb naturalnych

Funkcja pary Cantora jest funkcją

$\pi :\mathbb{N}\times \mathbb{N}\to \mathbb{N}$

daną wzorem

$\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 $k_1$ i $k_2$ często oznacza się jako $⟨k_1,k_2⟩.$

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

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

następująco

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

Odwracanie funkcji pary Cantora

Niech dane będzie $z$ jako

$z=⟨x,y⟩=\frac{(x+y)(x+y+1)}{2}+y$

i powiedzmy, że chcemy znaleźć $x$ i $y.$

Zdefiniujmy pomocniczo:

$w=x+y,$

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

$z=t+y,$

gdzie $t$ jest $w$-tą liczbą trójkątną.

Rozwiązując równanie:

$w^2+w-2t=0$

z $w$ jako funkcją parametru $t,$ dostaniemy:

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

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

Skoro

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

dostajemy

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

skąd

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

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

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

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

$y=z-t,$

$x=w-y.$

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

Bibliografia

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