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

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

Любая функция сопряжения может использоваться в теория множеств чтобы доказать, что целые числа и рациональное число имеют то же самое мощность как натуральные числа. В теоретическая информатика они используются для кодирования функции, определенной на векторе натуральных чисел ${\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }$ в новую функцию ${\displaystyle g:\mathbb {N} \rightarrow \mathbb {N} }$.

Определение

А функция сопряжения вычислимый биекция

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

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

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

В Функция сопряжения Кантора это примитивно рекурсивный функция сопряжения

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

Утверждение, что это единственная квадратичная функция спаривания, известно как Теорема Фютера – Полиа. Вопрос о том, является ли это единственной функцией спаривания полиномов, все еще остается открытым. k₁ и k₂ мы часто обозначаем полученное число как ⟨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})}$

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

и, следовательно, что π обратимо. В расчетах полезно определить некоторые промежуточные значения:

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

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

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

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

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

за ш как функция т, мы получили

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

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

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

куда ⌊ ⌋ это функция пола. Итак, чтобы рассчитать Икс и у из 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.\!}$

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

Примеры

Вычислять π(47, 32):

47 + 32 = 79,

79 + 1 = 80,

79 × 80 = 6320,

6320 ÷ 2 = 3160,

3160 + 32 = 3192,

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

Найти Икс и у такой, что π(Икс, у) = 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.

Вывод

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

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

Функция спаривания обычно может быть определена индуктивно, то есть с учетом п-я пара, что это за (п+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}$.

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

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

чтобы мы могли соответствовать нашим k условия получить

б = а

d = 1-а

е = 1+а.

Таким образом, каждый параметр можно записать в виде а кроме 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}}}$

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

а = 1/2 = б = d

c = 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}}}$

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

Примечания

1. Термин «диагональный аргумент» иногда используется для обозначения этого типа перечисления, но это нет непосредственно связанный с Диагональный аргумент Кантора.

внешняя ссылка

• Стивен Голубь. «Функция сопряжения». MathWorld.
• Элегантная функция сопряжения