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

Функция, однозначно преобразующая два числа в одно число

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

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

Определение

Функция сопряжения является биекцией ^{[ требуется проверка ]}

${\displaystyle \pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} .}$^[1]

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

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

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

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

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

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

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

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

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

${\displaystyle \pi (k_{1},k_{2}):={\frac {1}{2}}(k_{1}+k_{2})(k_{1}+k_{2}+1)+k_{2}}$^{[1] [ требуется проверка ]}

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

Его также можно выразить как . ^[2] ${\displaystyle \pi (x,y):={\frac {x^{2}+x+2xy+3y+y^{2}}{2}}}$

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

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

Это определение можно индуктивно обобщить до функции кортежа Кантора ^{[ требуется ссылка ]}

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

для как ${\displaystyle n>2}$

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

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

Обращение функции спаривания Кантора

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

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

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

${\displaystyle w=x+y\!}$

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

${\displaystyle z=t+y\!}$

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

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

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

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

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

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

мы получаем это

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

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

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

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

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

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

${\displaystyle y=z-t\!}$

${\displaystyle x=w-y.\!}$

Поскольку функция спаривания Кантора обратима, она должна быть взаимно-однозначной и на . ^{[2] [ необходимы дополнительные ссылки ]}

Примеры

Чтобы вычислить π (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 ,

поэтому w = 53 ;

53 + 1 = 54 ,

53 × 54 = 2862 ,

2862 ÷ 2 = 1431 ,

поэтому t = 1431 ;

1432 − 1431 = 1 ,

поэтому у = 1 ;

53 − 1 = 52 ,

поэтому x = 52 ; таким образом, π (52, 1) = 1432. [ ^{необходима ссылка ]}

Вывод

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

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

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

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

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

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

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

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

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

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

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

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

б = а

д = 1- а

е = 1+ а .

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

${\displaystyle {\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⁠ = б = г

с = 1

е = ⁠3/2⁠

ф = 0 .

Поэтому

${\displaystyle {\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}}}$

— это функция спаривания Кантора, и мы также продемонстрировали с помощью вывода, что она удовлетворяет всем условиям индукции. ^{[ необходима цитата ]}

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

Функция представляет собой функцию сопряжения. ${\displaystyle P_{2}(x,y):=2^{x}(2y+1)-1}$

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

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

${\displaystyle \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 и j соответственно. ^{[ 1] [ требуется проверка} ] ${\displaystyle i_{0}}$ ${\displaystyle j_{0}}$

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

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

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

${\displaystyle \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 по глубине. ^{[2] [ необходимо разъяснение ]} Этот метод является простым применением идеи, встречающейся в большинстве учебников по теории множеств, ^[5] используемой для установления для любого бесконечного кардинала в ZFC . Определим на бинарном отношении ${\displaystyle \mathbb {N} }$ ${\displaystyle \kappa ^{2}=\kappa }$ ${\displaystyle \kappa }$ ${\displaystyle \kappa \times \kappa }$

${\displaystyle (\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}}}$

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

Примечания

1. Термин «диагональный аргумент» иногда используется для обозначения этого типа перечисления, но он не имеет прямого отношения к диагональному аргументу Кантора . ^{[ необходима ссылка ]}

Ссылки

1. Стивен Пиджен. "Функция сопряжения". MathWorld . Получено 16 августа 2021 г. .
2. Szudzik, Matthew (2006). "An Elegant Pairing Function" (PDF) . szudzik.com . Архивировано (PDF) из оригинала 25 ноября 2011 г. . Получено 16 августа 2021 г. .
3. Шудзик, Мэтью П. (01.06.2017). "Функция спаривания Розенберга-Стронга". arXiv : 1706.04129 [cs.DM].
4. Regan, Kenneth W. (1992-12-01). "Функции сопряжения минимальной сложности". Журнал компьютерных и системных наук . 45 (3): 285–295. doi : 10.1016/0022-0000(92)90027-G . ISSN  0022-0000.
5. См., например, Thomas, Jech (2006). Теория множеств: издание третьего тысячелетия . Springer Monographs in Mathematics. Springer-Verlag. стр. 30. doi :10.1007/3-540-44761-X. ISBN 3-540-44085-2.