Funkcja pary

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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:NkN za pomocą funkcji jednej zmiennej g:NN.

Definicja[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]