Funkcja pary

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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

Definicja formalna[edytuj]

Funkcją pary jest pierwotnie rekurencyjna bijekcja

(Uwaga: tutaj )

Funkcja pary Cantora[edytuj]

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

Funkcja pary Cantora jest funkcją

daną wzorem

Wartość otrzymaną przez zastosowanie tej funkcji do liczb i często oznacza się jako

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

następująco

Odwracanie funkcji pary Cantora[edytuj]

Niech dane będzie z jako

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

Zdefiniujmy pomocniczo:

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

Rozwiązując równanie:

z w jako funkcją parametru t, dostaniemy:

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

Skoro

dostajemy

skąd

.

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

.

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

Bibliografia[edytuj]