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 : N k → N {\displaystyle f\colon \mathbf {N} ^{k}\to \mathbf {N} } za pomocą funkcji jednej zmiennej g : N → N . {\displaystyle g\colon \mathbf {N} \to \mathbf {N} .}
Funkcją pary jest pierwotnie rekurencyjna bijekcja
π : N × N → N . {\displaystyle \pi \colon \mathbb {N} \times \mathbb {N} \to \mathbb {N} .} (Uwaga : tutaj N = { 0 , 1 , 2 , 3 , … } {\displaystyle \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ą
π : N × N → N {\displaystyle \pi \colon \mathbb {N} \times \mathbb {N} \to \mathbb {N} } daną wzorem
π ( k 1 , k 2 ) := 1 2 ( k 1 + k 2 ) ( k 1 + k 2 + 1 ) + k 2 . {\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 k 1 {\displaystyle k_{1}} i k 2 {\displaystyle k_{2}} często oznacza się jako ⟨ k 1 , k 2 ⟩ . {\displaystyle \langle k_{1},k_{2}\rangle .}
Definicja ta może być indukcyjnie rozszerzana do funkcji krotkowej Cantora
π ( n ) : N n → N {\displaystyle \pi ^{(n)}\colon \mathbb {N} ^{n}\to \mathbb {N} } następująco
π ( n ) ( k 1 , … , k n − 1 , k n ) := π ( π ( n − 1 ) ( k 1 , … , k n − 1 ) , k n ) . {\displaystyle \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 {\displaystyle z} jako
z = ⟨ x , y ⟩ = ( x + y ) ( x + y + 1 ) 2 + y {\displaystyle z=\langle x,y\rangle ={\frac {(x+y)(x+y+1)}{2}}+y} i powiedzmy, że chcemy znaleźć x {\displaystyle x} i y . {\displaystyle y.}
Zdefiniujmy pomocniczo:
w = x + y , {\displaystyle w=x+y,} t = w ( w + 1 ) 2 = w 2 + w 2 , {\displaystyle t={\frac {w(w+1)}{2}}={\frac {w^{2}+w}{2}},} z = t + y , {\displaystyle z=t+y,} gdzie t {\displaystyle t} jest w {\displaystyle w} -tą liczbą trójkątną .
Rozwiązując równanie:
w 2 + w − 2 t = 0 {\displaystyle w^{2}+w-2t=0} z w {\displaystyle w} jako funkcją parametru t , {\displaystyle t,} dostaniemy:
w = 8 t + 1 − 1 2 , {\displaystyle w={\frac {{\sqrt {8t+1}}-1}{2}},} co jest ściśle rosnące i ciągłe dla nieujemnego rzeczywistego t . {\displaystyle t.}
Skoro
t ≤ z = t + y < t + ( w + 1 ) = ( w + 1 ) 2 + ( w + 1 ) 2 , {\displaystyle t\leq z=t+y<t+(w+1)={\frac {(w+1)^{2}+(w+1)}{2}},} dostajemy
w ≤ 8 z + 1 − 1 2 < w + 1 , {\displaystyle w\leq {\frac {{\sqrt {8z+1}}-1}{2}}<w+1,} skąd
w = ⌊ 8 z + 1 − 1 2 ⌋ . {\displaystyle w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor .} Tak więc, aby wyznaczyć x {\displaystyle x} i y {\displaystyle y} z z , {\displaystyle z,} postępujemy następująco:
w = ⌊ 8 z + 1 − 1 2 ⌋ , {\displaystyle w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor ,} t = w 2 + w 2 , {\displaystyle t={\frac {w^{2}+w}{2}},} y = z − t , {\displaystyle y=z-t,} x = w − y . {\displaystyle x=w-y.} Skoro funkcja Cantora jest odwracalna, musi być różnowartościowa i na .
Bibliografia Steven Pigeon, „Pairing function” z serwisu MathWorld.