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 za pomocą funkcji jednej zmiennej
Definicja formalna Funkcją pary jest pierwotnie rekurencyjna bijekcja
(Uwaga: tutaj )
Funkcja pary Cantora thumb|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 Niech dane będzie jako
i powiedzmy, że chcemy znaleźć i
Zdefiniujmy pomocniczo:
gdzie jest -tą liczbą trójkątną.
Rozwiązując równanie:
z jako funkcją parametru dostaniemy:
co jest ściśle rosnące i ciągłe dla nieujemnego rzeczywistego
Skoro
dostajemy
skąd
Tak więc, aby wyznaczyć i z postępujemy następująco:
Skoro funkcja Cantora jest odwracalna, musi być różnowartościowa i na.
Bibliografia Steven Pigeon, „Pairing function” z serwisu MathWorld.
Kategoria:Teoria mnogości Kategoria:Działania dwuargumentowe