Funkcja pary

W matematyce funkcja pary jest przyporządkowaniem służącym 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:N^k → N za pomocą funkcji jednej zmiennej g:N → N.

Definicja

Funkcją pary jest pierwotnie rekurencyjna bijekcja

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

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

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 $\langle k_1, k_2 \rangle \,.$

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, \ldots, k_{n-1}, k_n) := \pi ( \pi^{(n-1)}(k_1, \ldots, k_{n-1}) , k_n) \,.$

Odwracanie funkcji pary Cantora

Niech dane będzie z jako

$z = \langle x, y \rangle = \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 \leq z = t + y < t + (w + 1) = \frac{(w + 1)^2 + (w + 1)}{2}$

dostajemy

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

skąd

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

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

$w = \left\lfloor \frac{\sqrt{8z + 1} - 1}{2} \right\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.