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

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

Теорема

Редукция множества ко множеству — это полная вычислимая функция , такая что . Редукция множества ко множеству — это инъективная редукция, а вычислимый изоморфизм — это биективная редукция. А ⊆ Н {\displaystyle A\subseteq \mathbb {N} } Б ⊆ Н {\displaystyle B\subseteq \mathbb {N} } ф : Н → Н {\displaystyle f:\mathbb {N} \to \mathbb {N} } ∀ х ∈ Н , х ∈ А ⟺ ф ( х ) ∈ Б {\displaystyle \forall x\in \mathbb {N} ,x\in A\ifl f(x)\in B}

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

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

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

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

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

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

1) Пусть — рекурсивная функция. Тогда существует полная вычислимая функция такая, что ϕ : Ф ( Н к ) {\displaystyle \phi :\mathbb {F} (\mathbb {N} ^{k})} → Ф ( Н я ) {\displaystyle \rightarrow \mathbb {F} (\mathbb {N} ^{i})} h Φ : N → N {\displaystyle h_{\Phi }:\mathbb {N} \rightarrow \mathbb {N} } ∀ e ∈ N ( ϕ e k ) = ϕ h ( Φ ) ( e ) ( i ) {\displaystyle \forall e\in \mathbb {N} (\phi _{e}^{k})=\phi _{h_{(}\Phi )(e)}^{(i)}}

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

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

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

На рисунке показана последовательность элементов, поочередно синего и зеленого. Есть стрелка от первого ко второму элементу, обозначенному как "f", затем от второго к третьему, обозначенному как "g", затем снова "f" и так далее.
Односторонняя цепь, начинающаяся в первой копии ℕ
Аналогично предыдущей картинке, за исключением того, что цвета инвертированы, как и «f» и «g».
Односторонняя цепь, начинающаяся во второй копии ℕ
Изображение последовательности элементов, бесконечно простирающихся в обоих направлениях. Элементы попеременно синие и зеленые, а стрелки от одного к другому попеременно обозначены как "f" и "g".
Двусторонняя цепь
Цикл элементов, с многоточием, показывающим, что их может быть произвольное количество. Элементы попеременно синие и зеленые, а стрелки от одного к другому попеременно обозначены как "f" и "g".
Цикл

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

  • Односторонние цепи, в которых в конечном итоге останавливаются на элементе, не имеющем прообраза по или . f {\displaystyle f} g {\displaystyle g}
  • Двусторонние цепи, в которых это продолжается бесконечно без возврата в исходное состояние.
  • Циклы, где в конечном итоге получается уже виденный элемент.

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

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

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

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

Смотрите также

Ссылки

  1. ^ P. Odifreddi, Классическая теория рекурсии: Теория функций и множеств натуральных чисел (стр. 320). Исследования по логике и основаниям математики, т. 125 (1989), Elsevier 0-444-87295-7.
  2. ^ Деккер, JCE (сентябрь 1957 г.). «Дж. Майхилл и Дж. К. Шепердсон. Эффективные операции над частично рекурсивными функциями. Zeitschrift für mathematische Logik und Grundlagen der Mathetnatik, том 1 (1955), стр. 310–317». Журнал символической логики . 22 (3): 310–317. дои : 10.2307/2963619. ISSN  0022-4812. JSTOR  2963619. S2CID  124280881.
  • Майхилл, Джон (1955), «Творческие множества», Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 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
Retrieved from "https://en.wikipedia.org/w/index.php?title=Myhill_isomorphism_theorem&oldid=1232109879"