Теорема Майхилла об изоморфизме

В теории вычислимости теорема изоморфизма Майхилла , названная в честь Джона Майхилла , дает характеристику двум нумерациям , чтобы вызвать одно и то же понятие вычислимости на множестве. Она напоминает теорему Шредера-Бернштейна в теории множеств и была названа ее конструктивной версией. ^[1]

Теорема

Сокращение « много -один» из набора $A\subseteq \mathbb {N}$ в набор $B\subseteq \mathbb {N}$ — полная вычислимая функция $f:\mathbb {N} \to \mathbb {N}$ такой, что $\forall x\in \mathbb {N} ,x\in A\iff f(x)\in B$ . Сведение «один к одному» — это инъективная редукция, а вычислимый изоморфизм — это биективная редукция.

Теорема Майхилла об изоморфизме: два множества $A,B\subseteq \mathbb {N}$ вычислимо изоморфны тогда и только тогда, когда A одно-единственно сводимо к B и B одно-единственно сводимо к A .

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

Теорема Майхилла-Шепердсона

Теорема Майхилла-Шепердсона, ^[2] вытекающее из теоремы Райса-Шапиро , определяет вычислимые функционалы типа 2. Эти функционалы оперируют вычислимыми частичными функциями, возвращая числа в случае завершения. Примечательно, что они придерживаются определенного критерия эффективности и демонстрируют непрерывность как функционалы.

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

В частности, там говорится:

1) Пусть $\phi :\mathbb {F} (\mathbb {N} ^{k})$ $\rightarrow \mathbb {F} (\mathbb {N} ^{i})$ быть рекурсивной функцией. Тогда существует тотальная вычислимая функция $h_{\Phi }:\mathbb {N} \rightarrow \mathbb {N}$ такой, что $\forall e\in \mathbb {N} (\phi _{e}^{k})=\phi _{h_{(}\Phi )(e)}^{(i)}$

2) Пусть $h:\mathbb {N} \rightarrow \mathbb {N}$ быть полной вычислимой функцией и $h$ экстенсиональный.Тогда существует единственный рекурсивный функционал $\phi :\mathbb {F} (\mathbb {N} ^{k})$ $\rightarrow \mathbb {F} (\mathbb {N} ^{i})$ такой, что $\forall e\in \mathbb {N} (\phi _{e}^{k})=\phi _{h(e)}^{(i)}$

Схема доказательства

Позволять $A,B\subseteq \mathbb {N}$ быть двумя множествами и предположим, что существуют инъективные, тотально вычислимые функции $f,g:\mathbb {N} \to \mathbb {N}$ такой, что для всех $x\in \mathbb {N}$ , $x\in A\iff f(x)\in B$ и $x\in B\iff g(x)\in A$ . Мы хотим построить $h:\mathbb {N} \to \mathbb {N}$ тотально вычислима и биективна такая, что для всех $x\in \mathbb {N}$ , $x\in A\iff h(x)\in B$ .

Односторонняя цепочка, начинающаяся с первого экземпляра ℕ.

Односторонняя цепочка, начинающаяся во втором экземпляре ℕ.

Двусторонняя цепочка

Как и в большинстве доказательств теоремы Шредера-Бернштейна , мы используем анализ «цепочек», образованных последовательными применениями $f$ и $g$ . Неформально мы думаем о двух «копиях» $\mathbb {N}$ между которыми мы хотим построить биекцию, и рассматриваем целое число в первой копии, которую отправляет $f$ к целому числу во второй копии, которая, в свою очередь, отправляется $g$ на целое число в первой копии и т. д. (На картинках напротив эти копии синие и зеленые.) Потому что $f$ и $g$ инъективны, эти цепочки не «перекрываются» (слияния двух цепочек быть не может). В зависимости от того, что происходит при старте с какого-либо элемента и возвращении по цепочке, существует три возможных типа цепочек:

Односторонние цепочки, где в конечном итоге останавливаются на элементе, не имеющем прообраза. $f$ или $g$ .

Двусторонние цепочки, где это продолжается бесконечно, не возвращаясь назад.

Циклы, где в конечном итоге получается уже увиденный элемент.

Чтобы построить биекцию в контексте теоремы Шредера-Бернштейна, достаточно соединить элементы вдоль каждой цепи: в односторонней цепи используйте $f$ или $g$ в зависимости от цвета первого элемента и двусторонней цепочки или цикла можно использовать любой из них. Для теоремы Майхилла это не работает, поскольку построенная биекция не обязательно должна быть вычислимой.

Вместо этого мы строим биекцию путем последовательного спаривания элементов. На каждом этапе мы берем следующий непарный элемент из синей копии $\mathbb {N}$ и соединяем его с каким-нибудь непарным элементом зеленой копии, затем то же самое делаем со следующим непарным элементом из зеленой копии. Это гарантирует, что каждый элемент обеих копий в какой-то момент будет спарен.

Предположим, мы хотим соединить некоторый синий элемент (случай зеленого элемента симметричен). Идея состоит в том, чтобы применить $f$ чтобы получить следующий зеленый элемент в цепочке, и если этот элемент непарный, используйте его для сопряжения с нашим синим элементом. Если он парный, то примените $g$ затем $f$ чтобы перейти к следующему зеленому элементу в цепочке, и повторяйте, пока не будет найден непарный зеленый элемент.

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

См. также

Гипотеза Бермана-Хартманиса , аналогичное утверждение в теории сложности вычислений .

Ссылки

^ П. Одифредди, Классическая теория рекурсии: Теория функций и множеств натуральных чисел (стр.320). Исследования по логике и основам математики, том. 125 (1989), Эльзевир 0-444-87295-7.
^ Деккер, JCE (сентябрь 1957 г.). «Дж. Майхилл и Дж. К. Шепердсон. Эффективные операции над частично рекурсивными функциями. Журнал математической логики и основ математики, том 1 (1955), стр. 310–317» . Журнал символической логики . 22 (3): 310–317. дои : 10.2307/2963619 . ISSN 0022-4812 . JSTOR 2963619 . S2CID 124280881 .

Майхилл, Джон (1955), «Творческие множества», Журнал математической логики и основ математики , 1 (2): 97–108, doi : 10.1002/malq.19550010205 , MR 0071379 .
Роджерс, Хартли младший (1987), Теория рекурсивных функций и эффективная вычислимость (2-е изд.), Кембридж, Массачусетс: MIT Press, ISBN 0-262-68052-1 , МР 0886890 .
Соаре, Роберт И. (1987), Рекурсивно перечислимые множества и степени: исследование вычислимых функций и вычислимо порожденных множеств, Перспективы математической логики, Берлин-Гейдельберг: Springer-Verlag, ISBN 978-3-540-66681-3, MR 0882921

[Odifreddi89-1] П. Одифредди, Классическая теория рекурсии: Теория функций и множеств натуральных чисел (стр.320). Исследования по логике и основам математики, том. 125 (1989), Эльзевир 0-444-87295-7.

[2] Деккер, JCE (сентябрь 1957 г.). «Дж. Майхилл и Дж. К. Шепердсон. Эффективные операции над частично рекурсивными функциями. Журнал математической логики и основ математики, том 1 (1955), стр. 310–317» . Журнал символической логики . 22 (3): 310–317. дои : 10.2307/2963619 . ISSN 0022-4812 . JSTOR 2963619 . S2CID 124280881 .

[1]

[2]