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} }
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 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}}
k
2
{\displaystyle k_{2}}
⟨
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
edytuj
Niech dane będzie
z
{\displaystyle z}
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}
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}
w
{\displaystyle w}
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}
t
,
{\displaystyle t,}
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}
y
{\displaystyle y}
z
,
{\displaystyle z,}
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 .
