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

В этой статье не процитировать какие - либо источники . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален . Поиск источников:  «Функция сопряжения»  -  новости  · газеты  · книги  · ученый  · JSTOR ( август 2020 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

Любую функцию спаривания можно использовать в теории множеств, чтобы доказать, что целые и рациональные числа имеют ту же мощность, что и натуральные числа. В теоретической информатике они используются для кодирования функции, определенной на векторе натуральных чисел, в новую функцию .${\ 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\!}$

для 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.\!}$

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

Примеры [ править ]

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

поэтому y = 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 условий, чтобы получить

б = а

d = 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= b = d

с = 1

е =3/2

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

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

Заметки [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

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