Функция сопряжения

В математике функция спаривания — это процесс уникального кодирования двух натуральных чисел в одно натуральное число.

Любую функцию спаривания можно использовать в теории множеств, чтобы доказать, что целые и рациональные числа имеют ту же мощность , что и натуральные числа.

Определение

— Спаривающая функция это биекция

$\pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} .$

В более общем смысле, функция сопряжения на множестве A — это функция, которая отображает каждую пару элементов из A в элемент A , так что любые две пары элементов A связаны с разными элементами A, или биекция из $A^{2}$ к А. ​

Функция сопряжения Хопкрофта и Ульмана

Хопкрофт и Ульман (1979) определяют следующую функцию спаривания: $\langle i,j\rangle :={\frac {1}{2}}(i+j-2)(i+j-1)+i$, где $i,j\in \{1,2,3,\dots \}$. Это то же самое, что и функция спаривания Кантора, приведенная ниже, но сдвинутая для исключения 0 (т. е. $i=k_{2}+1$, $j=k_{1}+1$, и $\langle i,j\rangle -1=\pi (k_{2},k_{1})$).

Функция сопряжения Кантора

Функция спаривания Кантора присваивает одно натуральное число каждой паре натуральных чисел.

График функции спаривания Кантора

— Функция спаривания Кантора это примитивно-рекурсивная функция спаривания.

$\pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N}$

определяется

$\pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}$

где $k_{1},k_{2}\in \{0,1,2,3,\dots \}$.

Это также может быть выражено как $\pi (x,y):={\frac {x^{2}+x+2xy+3y+y^{2}}{2}}$.

Оно также строго монотонно по каждому аргументу, т. е. для всех $k_{1},k_{1}',k_{2},k_{2}'\in \mathbb {N}$, если $k_{1}<k_{1}'$, затем $\pi (k_{1},k_{2})<\pi (k_{1}',k_{2})$; аналогично, если $k_{2}<k_{2}'$, затем $\pi (k_{1},k_{2})<\pi (k_{1},k_{2}')$.

Утверждение о том, что это единственная квадратичная функция спаривания, известно как теорема Фютера – Полиа . Является ли это единственной полиномиальной спаривающей функцией, до сих пор остается открытым вопросом. Когда мы применяем функцию спаривания к k ₁ и k _2, мы часто обозначаем полученное число как ⟨ k ₁ , k ₂ ⟩ .

Это определение можно индуктивно обобщить на функцию кортежа Кантора.

$\pi ^{(n)}:\mathbb {N} ^{n}\to \mathbb {N}$

для $n>2$ как

$\pi ^{(n)}(k_{1},\ldots ,k_{n-1},k_{n}):=\pi (\pi ^{(n-1)}(k_{1},\ldots ,k_{n-1}),k_{n})$

с базовым случаем, определенным выше для пары: $\pi ^{(2)}(k_{1},k_{2}):=\pi (k_{1},k_{2}).$

Инвертирование функции сопряжения Кантора

Позволять $z\in \mathbb {N}$ быть произвольным натуральным числом. Покажем, что существуют уникальные значения $x,y\in \mathbb {N}$ такой, что

$z=\pi (x,y)={\frac {(x+y+1)(x+y)}{2}}+y$

и, следовательно, функция π(x, y) обратима. При расчете полезно определить некоторые промежуточные значения:

$w=x+y\!$

$t={\frac {1}{2}}w(w+1)={\frac {w^{2}+w}{2}}$

$z=t+y\!$

где t — треугольника w . номер Если мы решим квадратное уравнение

$w^{2}+w-2t=0\!$

для w как функции t мы получаем

$w={\frac {{\sqrt {8t+1}}-1}{2}}$

которая является строго возрастающей и непрерывной функцией, когда t неотрицательно. С

$t\leq z=t+y<t+(w+1)={\frac {(w+1)^{2}+(w+1)}{2}}$

мы поняли это

$w\leq {\frac {{\sqrt {8z+1}}-1}{2}}<w+1$

и таким образом

$w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor .$

где ⌊ ⌋ — функция пола .Итак, чтобы вычислить x и y по z , мы делаем:

$w=\left\lfloor {\frac {{\sqrt {8z+1}}-1}{2}}\right\rfloor$

$t={\frac {w^{2}+w}{2}}$

$y=z-t\!$

$x=w-y.\!$

Поскольку функция спаривания Кантора обратима, она должна быть взаимно однозначной и на .

Примеры

Чтобы вычислить π (47, 32) :

47 + 32 = 79 ,

79 + 1 = 80 ,

79 × 80 = 6320 ,

6320 ÷ 2 = 3160 ,

3160 + 32 = 3192 ,

итак π (47, 32) = 3192 .

Чтобы найти x и y такие, что π ( x , y ) = 1432 :

8 × 1432 = 11456 ,

11456 + 1 = 11457 ,

√ 11457 = 107.037 ,

107.037 − 1 = 106.037 ,

106.037 ÷ 2 = 53.019 ,

⌊53.019⌋ = 53 ,

итак, ш = 53 ;

53 + 1 = 54 ,

53 × 54 = 2862 ,

2862 ÷ 2 = 1431 ,

итак т = 1431 ;

1432 − 1431 = 1 ,

итак, у = 1 ;

53 − 1 = 52 ,

итак х = 52 ; таким образом, π (52, 1) = 1432 .

Вывод

«Змееподобная» функция с диагональным приращением, основанная на тех же принципах, что и функция спаривания Кантора, часто используется для демонстрации счетности рациональных чисел.

Графическая форма спаривающей функции Кантора — диагональная прогрессия — стандартный приём при работе с бесконечными последовательностями и счётностью . проверить ее справедливость для ряда многочленов, из которых наиболее простым окажется квадратичный Алгебраические правила этой диагональной функции позволяют методом индукции . Действительно, эту же технику можно использовать, чтобы попытаться вывести любое количество других функций для любого разнообразия схем перечисления плоскости.

Функцию спаривания обычно можно определить индуктивно – то есть, учитывая n -ю пару, какова ( n +1) -я пара? То, как функция Кантора движется по диагонали через плоскость, можно выразить как

$\pi (x,y)+1=\pi (x-1,y+1)$.

Функция также должна определить, что делать, когда она достигает границ 1-го квадранта — функция спаривания Кантора возвращается к оси X, чтобы возобновить диагональное продвижение на один шаг вперед, или алгебраически:

$\pi (0,k)+1=\pi (k+1,0)$.

Также нам нужно определить отправную точку, которая будет начальным шагом в нашем методе индукции: π (0, 0) = 0 .

Предположим, что существует квадратичный двумерный полином, который может соответствовать этим условиям (если бы это было не так, можно было бы просто повторить, попробовав полином более высокой степени). Общая форма тогда

$\pi (x,y)=ax^{2}+by^{2}+cxy+dx+ey+f$.

Подставьте наши начальные и граничные условия, чтобы получить f = 0 и:

$bk^{2}+ek+1=a(k+1)^{2}+d(k+1)$,

поэтому мы можем сопоставить наши k членов, чтобы получить

б = а

д = 1- а

е = 1+ а .

Таким образом, каждый параметр может быть записан через a, за исключением c , и у нас есть последнее уравнение, наш диагональный шаг, который свяжет их:

${\begin{aligned}\pi (x,y)+1&=a(x^{2}+y^{2})+cxy+(1-a)x+(1+a)y+1\\&=a((x-1)^{2}+(y+1)^{2})+c(x-1)(y+1)+(1-a)(x-1)+(1+a)(y+1).\end{aligned}}$

Снова разверните и сопоставьте термины, чтобы получить фиксированные значения для a и c и, следовательно, для всех параметров:

а = ⁠ 1 / 2 ⁠ = б = d

с = 1

и = ⁠ 3 / 2 ⁠

ж знак равно 0 .

Поэтому

${\begin{aligned}\pi (x,y)&={\frac {1}{2}}(x^{2}+y^{2})+xy+{\frac {1}{2}}x+{\frac {3}{2}}y\\&={\frac {1}{2}}(x+y)(x+y+1)+y,\end{aligned}}$

— спаривающая функция Кантора, и с помощью вывода мы также показали, что она удовлетворяет всем условиям индукции.

Другие функции сопряжения

Функция $P_{2}(x,y):=2^{x}(2y+1)-1$ это функция сопряжения.

В 1990 году Риган предложил первую известную функцию спаривания, которая вычислима за линейное время и с постоянным пространством (поскольку ранее известные примеры могут быть вычислены только за линейное время тогда и только тогда, когда умножение тоже может быть выполнено , что сомнительно). Фактически, и эту функцию спаривания, и ее обратную функцию можно вычислить с помощью преобразователей с конечным состоянием, которые работают в реальном времени. В той же статье автор предложил еще две монотонные функции спаривания, которые можно вычислить онлайн за линейное время и в логарифмическом пространстве ; первое также можно вычислить в автономном режиме с нулевым пространством.

В 2001 году Пиджен предложил функцию сопряжения, основанную на чередовании битов , рекурсивно определенную как:

$\langle i,j\rangle _{P}={\begin{cases}T&{\text{if}}\ i=j=0;\\\langle \lfloor i/2\rfloor ,\lfloor j/2\rfloor \rangle _{P}:i_{0}:j_{0}&{\text{otherwise,}}\end{cases}}$

где $i_{0}$ и $j_{0}$ являются младшими битами i j и соответственно .

В 2006 году Судзик предложил «более элегантную» функцию спаривания, определяемую выражением:

$\operatorname {ElegantPair} [x,y]:={\begin{cases}y^{2}+x&{\text{if}}\ x<y,\\x^{2}+x+y&{\text{if}}\ x\geq y.\\\end{cases}}$

Которые можно распарить с помощью выражения:

$\operatorname {ElegantUnpair} [z]:={\begin{cases}\left\{z-\lfloor {\sqrt {z}}\rfloor ^{2},\lfloor {\sqrt {z}}\rfloor \right\}&{\text{if }}z-\lfloor {\sqrt {z}}\rfloor ^{2}<\lfloor {\sqrt {z}}\rfloor ,\\\left\{\lfloor {\sqrt {z}}\rfloor ,z-\lfloor {\sqrt {z}}\rfloor ^{2}-\lfloor {\sqrt {z}}\rfloor \right\}&{\text{if }}z-\lfloor {\sqrt {z}}\rfloor ^{2}\geq \lfloor {\sqrt {z}}\rfloor .\end{cases}}$

(Качественно, она присваивает последовательные числа парам по краям квадратов.) Эта функция спаривания упорядочивает выражения исчисления комбинатора SK по глубине. Этот метод является простым применением $\mathbb {N}$ идеи, встречающейся в большинстве учебников по теории множеств, используется для установления $\kappa ^{2}=\kappa$ для любого бесконечного кардинала $\kappa$ в ЗФК .Определить на $\kappa \times \kappa$ бинарное отношение

$(\alpha ,\beta )\preccurlyeq (\gamma ,\delta ){\text{ if either }}{\begin{cases}(\alpha ,\beta )=(\gamma ,\delta ),\\[4pt]\max(\alpha ,\beta )<\max(\gamma ,\delta ),\\[4pt]\max(\alpha ,\beta )=\max(\gamma ,\delta )\ {\text{and}}\ \alpha <\gamma ,{\text{ or}}\\[4pt]\max(\alpha ,\beta )=\max(\gamma ,\delta )\ {\text{and}}\ \alpha =\gamma \ {\text{and}}\ \beta <\delta .\end{cases}}$

$\preccurlyeq$ затем показано, что это упорядочение такое, что каждый элемент имеет ${}<\kappa$ предшественников, а это означает, что $\kappa ^{2}=\kappa$.Отсюда следует, что $(\mathbb {N} \times \mathbb {N} ,\preccurlyeq )$ изоморфен $(\mathbb {N} ,\leqslant )$ а приведенная выше функция сопряжения — это не что иное, как перечисление целочисленных пар в порядке возрастания. (См. также Обсуждение:Теорема Тарского о выборе#Доказательство обратного .)