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

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Pairing function" – news · newspapers · books · scholar · JSTOR (August 2021) (Learn how and when to remove this message)

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

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

Функция сопряжения является биекцией

${\displaystyle \pi :\mathbb {N} \times \mathbb {N} \to \mathbb {N} .}$^{[2] [3] [4]}

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

Вместо абстрагирования от области определения арность функции спаривания также может быть обобщена: существует n-арная обобщенная функция спаривания Кантора на . ^[3]${\displaystyle \mathbb {N} }$

Хопкрофт и Ульман (1979) определяют следующую функцию спаривания: , где . ^[7] Это то же самое, что и функция спаривания Кантора ниже, сдвинутая так, чтобы исключить 0 (т.е. , , и ). ^[8]${\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}}$

где . ^{[8] [ нужен лучший источник ]}${\displaystyle k_{1},k_{2}\in \{0,1,2,3,\dots \}}$

Его также можно выразить как . ^[5]${\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}')}$

Утверждение, что это единственная квадратичная функция спаривания, известно как теорема Фютера–Полиа . ^[9] Является ли это единственной полиномиальной функцией спаривания, все еще остается открытым вопросом. Когда мы применяем функцию спаривания к 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})}$

с базовым случаем, определенным выше для пары: ^[10]${\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.\!}$

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

Чтобы вычислить π (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. [ ^{необходима ссылка ]}

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

Функцию спаривания обычно можно определить индуктивно, то есть, если задана 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] [ необходимо разъяснение ]}

В 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 соответственно. ^[11] [ ^{нужен лучший источник ]}${\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 по глубине. ^{[5] [ необходимо разъяснение ]} Этот метод является простым применением идеи, встречающейся в большинстве учебников по теории множеств, ^[12] используемой для установления для любого бесконечного кардинала в 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 }$затем показано, что это вполне упорядоченное множество, в котором каждый элемент имеет предшественников, что подразумевает, что . Из этого следует, что изоморфно и функция спаривания выше есть не что иное, как перечисление пар целых чисел в порядке возрастания. ^[c]${\displaystyle {}<\kappa }$${\displaystyle \kappa ^{2}=\kappa }$${\displaystyle (\mathbb {N} \times \mathbb {N} ,\preccurlyeq )}$${\displaystyle (\mathbb {N} ,\leqslant )}$

• Стивен Пиджен. "Функция сопряжения". MathWorld .
• Лиси, Мери (2007). «Некоторые замечания о функции спаривания Кантора». Le Matematiche . LXII : 55–65 .
• Regan, Kenneth W. (декабрь 1992 г.). "Функции сопряжения минимальной сложности". Журнал компьютерных и системных наук . 45 (3): 285– 295. doi : 10.1016/0022-0000(92)90027-G . ISSN  0022-0000.{{cite journal}}: CS1 maint: date and year (link)
• Szudzik, Matthew (2006). "An Elegant Pairing Function" (PDF) . szudzik.com . Архивировано (PDF) из оригинала 25 ноября 2011 г. . Получено 16 августа 2021 г. .
• Szudzik, Matthew P. (1 июня 2017 г.). «Функция спаривания Розенберга-Стронга». arXiv : 1706.04129 [cs.DM].
• Jech, Thomas (2006). Теория множеств . Springer Monographs in Mathematics (The Third Millennium ed.). Springer-Verlag. doi :10.1007/3-540-44761-X. ISBN 3-540-44085-2.
• Хопкрофт, Джон Э.; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Эддисон-Уэсли. ISBN 0-201-02988-X.
• Стайн, Шерман К. (1999). Математика: Вселенная, созданная человеком (3-е изд.). Дувр. ISBN 9780486404509.