m-сводимость и свойства перечислимых множеств

m-полнота и эффективная неперечислимость

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

  48. Покажите, что произвольное множество A является эффективно бесконечным тогда и только тогда, когда оно содержит бесконечное перечислимое множество (е бесконечно, но не является иммунным).

Сейчас нас будет интересовать эффективный вариант понятия неперечислимости. Что значит, что множество A неперечислимо? Это означает (трюизм), что A отличается от любого перечислимого множества. Естественно называть множество A эффективно неперечислимым, если по любому перечислимому множеству можно указать место, где оно отличается от A.

Более формально, зафиксируем некоторое главное универсальное перечислимое множество W (и тем самым нумерацию перечислимых множеств: число n мы считаем номером множества Wn ). Будем говорить, что множество A является эффективно неперечислимым, если существует такая всюду определенная вычислимая функция f, что $$f(z) \in A$$ $$\bigtriangleup$$ Wz при всех z. (Здесь $$\bigtriangleup$$ означает симметрическую разность; другими словами, f(z) является точкой, где A отличается от Wz.)

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

Свойство эффективной неперечислимости допускает простую характеризацию в терминах m -сводимости. Начнем с такого простого наблюдения.

Теорема 34. Если A <=m B и A эффективно неперечислимо, то и B эффективно неперечислимо.

Эта теорема является "эффективным вариантом" теоремы 31, часть (б). То же самое можно сказать и о ее доказательстве. Пусть мы хотим найти точку, в которой B отличается от некоторого перечислимого множества X. Рассмотрим функцию f, которая m -сводит A к B. Прообраз f-1(X) перечислимого множества X при вычислимом отображении будет перечислим, поэтому можно найти точку m, в которой он отличается от A. Тогда B отличается от X в точке f(m).

Чтобы сделать это рассуждение точным, нам нужно лишь доказать, что номер перечислимого множества f-1(X) может быть эффективно получен по номеру перечислимого множества X. Для этого мы должны воспользоваться тем, что нумерация является главной схема тут та же, что и при вычислении номера композиции двух вычислимых функций, заданных своими номерами (теорема 16). Проведем это рассуждение подробно.

Рассмотрим перечислимое множество

$$V = \{ \langle x,y\rangle \mid \langle x, f(y)\rangle \in W\}$$

(оно перечислимо, поскольку является прообразом перечислимого множества W при вычислимом отображении $$\langle x,y\rangle \hm\mapsto \langle x, f(y)\rangle$$ ). Легко видеть, что Vn = f-1(Wn). Так как множество W является главным универсальным множеством, то существует вычислимая всюду определенная функция s, для которой Ws(n)=Vn=f-1(Wn) при всех n. Другими словами, функция s по W -номеру любого перечислимого множества дает W -номер его прообраза при отображении f, что и требовалось.

Теорема 35. Существуют перечислимые множества с эффективно неперечислимыми дополнениями.

Вновь рассмотрим диагональное множество $$D\hm=\{n\mid \langle n,n\rangle \hm\in W\}$$. Его дополнение будет эффективно неперечислимым. В самом деле, множества Wn и D одинаково себя ведут в точке n, поэтому Wn отличается от дополнения к D в этой точке. Таким образом, дополнение к D эффективно неперечислимо, причем в качестве функции f из определения эффективной неперечислимости можно взять тождественную функцию.

Из двух предыдущих теорем очевидно следует такое утверждение:

Теорема 36. Всякое m -полное перечислимое множество имеет эффективно неперечислимое дополнение.

На самом деле верно и обратное. Чтобы убедиться в этом, докажем такой факт:

Теорема 37. Пусть K перечислимое множество, а A эффективно неперечислимо. Тогда N \ K <=m A (или, что эквивалентно, K <=m N \ A ).

На самом деле нам важно умение эффективно отличать A лишь от двух перечислимых множеств от пустого и от всего натурального ряда. Отличить A от пустого множества означает указать элемент в A ; отличить от всего натурального ряда означает указать элемент вне A. Именно эти две вещи используются при сведении. Более формально, рассмотрим множество V=K x N. Его сечения Vn либо пусты (при $$n \notin K$$ ), либо совпадают со всем натуральным рядом (при $$n \in K$$ ). Пользуясь тем, что множество W является главным, мы находим всюду определенную функцию s, для которой $$W_{s(n)}=\varnothing$$ при $$n \notin K$$ и Ws(n)=N при $$n \in K$$. Пусть f функция, обеспечивающая эффективную неперечислимость множества A. Тогда $$f(s(n)) \in A$$ при $$n \notin K$$ и $$f(s(n)) \notin A$$ при $$n \in K$$. Другими словами, композиция функций f и s сводит N \ K к множеству A, что и требовалось.

Отсюда очевидно вытекают такие утверждения:

Теорема 38. Перечислимое множество является m -полным тогда и только тогда, когда его дополнение эффективно неперечислимо.

Теорема 39. Множество эффективно неперечислимо тогда и только тогда, когда к нему m -сводится дополнение некоторого (вариант: любого) m -полного множества.

Отметим, что не всякое неперечислимое множество эффективно неперечислимо. Это видно, например, из такого факта:

Теорема 40. Любое эффективно неперечислимое множество содержит бесконечное перечислимое подмножество (е не является иммунным).

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

В этом рассуждении мы использовали такой факт: по конечному множеству, заданному списком его элементов, можно получить его номер (точнее, один из номеров) в главной нумерации перечислимых множеств. Почему это так? Пусть фиксирована некоторая вычислимая нумерация конечных множеств. Будем обозначать n -ое конечное множество в этой нумерации через Dn. Тогда Dn будет n -ым сечением перечислимого (и даже разрешимого) множества

$$D=\{ \langle n, x\rangle \mid x \in D_n\}.$$

Остается воспользоваться определением главной нумерации перечислимых множеств.

Простые множества, которые, как мы знаем, существуют (теорема 14), являются примерами перечислимых множеств, не являющихся m -полными. Именно так и возникло понятие простого множества: Пост искал пример перечислимого неразрешимого множества, которое не было бы m -полным.

Изоморфизм m-полных множеств

В этом разделе мы докажем, что все m -полные множества " устроены одинаково" и отличаются друг от друга только вычислимой перестановкой.

Теорема 41. Пусть A и B m -полные перечислимые множества. Тогда существует вычислимая перестановка (вычислимое взаимно однозначное соответствие) f : N -> N, при которой A переходит в B, то есть $$x \in A \Leftrightarrow f(x) \in B$$ при всех x.

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

Лемма. Пусть A m -полное перечислимое множество. Тогда существует способ по любому натуральному числу n алгоритмически указать сколько угодно других натуральных чисел, которые принадлежат или не принадлежат A одновременно с n.

Доказательство леммы. Как и раньше, у нас будут два способа получать новые числа, которые ведут себя по отношению к A так же, как и исходное. Один из них будет гарантированно давать новое число, если $$x \in A$$, другой если $$x \notin A$$. При этом мы можем применять оба, не зная, какой из случаев имеет место на самом деле (и можем так этого и не узнать).

Первый способ состоит в следующем. Пусть P перечислимое неразрешимое множество. Рассмотрим перечислимое множество пар A x P. Оно сводится к A, так как A является m -полным. (Вообще-то в определении сводимости шла речь о множествах натуральных чисел, а не пар, но, как всегда, это не играет роли пары можно вычислимо нумеровать.) Другими словами, существует вычислимая всюду определенная функция f двух натуральных аргументов с таким свойством:

$$f(n,m) \in A \Leftrightarrow (n \in A)\ и\ (m \in P).$$

В частности, при $$m \in P$$ числа n и f(n,m) одновременно принадлежат или не принадлежат A. Поэтому, расположив P в вычислимую последовательность p(0),p(1), ..., мы можем вычислять числа f(n,p(0)),f(n,p(1)), ... и получать новые числа, которые принадлежат или не принадлежат A одновременно с n.

Пусть $$n \in A$$. Покажем, что множество X получаемых таким образом чисел (все они в этом случае тоже принадлежат A ) будет бесконечно. В самом деле, $$f(n,m) \in X$$ при $$m \in P$$ (по построению X ) и $$f(n,m) \notin X$$ при $$m \notin P$$ (поскольку в этом случае $$f(n,m) \notin A$$, а $$X \subset A$$ ). Таким образом, функция m -> f(n,m) сводит неразрешимое множество P к множеству X, так что X неразрешимо и потому бесконечно.

Теперь опишем другой способ, который гарантирует успех, если $$n \notin A$$. Возьмем два перечислимых неотделимых множества P и Q. Рассмотрим перечислимое множество пар $$(A \times P) \cup (N \times Q)$$. Пусть функция f сводит его к A. Это означает, что $$f(n,m) \in A$$ тогда и только тогда, когда $$(n \in A\ и\ m \in P)$$ или $$m \in Q$$. Как и прежде, при $$m \in P$$ числа n и f(n,m) одновременно принадлежат или не принадлежат A, так что мы можем снова рассмотреть последовательность f(n,p(0)),f(n,p(1)),...; осталось лишь показать, что (если $$n \notin A$$ ) в этой последовательности бесконечно много различных членов.

Пусть это не так и множество X всех членов этой последовательности конечно. По нашему предположению X не пересекается с A. Заметим, что $$f(n,m) \in X$$ при $$m \in P$$ (по построению) и $$f(n,m) \notin X$$ при $$m \in Q$$ (так как в этом случае $$\langle n,m\rangle$$ принадлежит нашему перечислимому множеству пар и f(n,m) принадлежит A ). Таким образом, прообраз множества X при отображении m -> f(n,m) отделяет P от Q. Но этот прообраз разрешим ( X разрешимо, ибо конечно, а указанное отображение всюду определено и вычислимо). А по нашему предположению множества P и Q нельзя отделить разрешимым множеством.

Итак, мы привели два способа получать новые элементы, которые принадлежат или не принадлежат A одновременно с исходным. Применяя их параллельно, мы наверняка добьемся результата. Лемма доказана.

Пусть теперь A и B два m -полных перечислимых множества. Докажем, что они отличаются лишь вычислимой перестановкой натурального ряда. Будем строить эту перестановку по шагам. На k -ом шаге мы имеем взаимно однозначное соответствие

$$a_{1} \leftrightarrow b_{1}, a_{2} \leftrightarrow b_{2},\dots , a_{k} \leftrightarrow b_{k},$$

при котором $$a_{i} \in A \Leftrightarrow b_{i} \in B$$ при всех i. На четных шагах мы берем минимальное число, не входящее в левую часть этого соответствия. Используя факт m -сводимости A к B, мы находим ему компаньона. При этом доказанная нами лемма позволяет выбрать компаньона, не встречающегося среди уже имеющихся справа элементов. На нечетных шагах мы делаем то же самое, только справа налево.

В пределе этот процесс дает искомую вычислимую перестановку, связывающую A и B.

С точки зрения теории алгоритмов два множества, отличающиеся лишь вычислимой перестановкой, обладают одинаковыми свойствами. Поэтому доказанная теорема показывает, что по существу имеется лишь одно m -полное перечислимое множество (или, что то же, лишь одно перечислимое множество с эффективно неперечислимым дополнением).

Продуктивные множества

В этом разделе мы используем теорему о неподвижной точке для получения такого (неожиданного на первый взгляд) результата: определение эффективной неперечислимости множества A не изменится, если мы ограничимся лишь (перечислимыми) подмножествами множества A.

Зафиксируем некоторую главную нумерацию перечислимых множеств (множество с номером n мы обозначаем Wn ). Говорят, что множество A является продуктивным, если существует вычислимая (не обязательно всюду определенная) функция f с таким свойством: она применима к любому номеру n любого подмножества Wn множества A и дает элемент в их разности:

$$W_{n} \subset A \Rightarrow f(n) \in A \setminus W_{n}.$$

  49. Докажите, что продуктивное множество не может быть иммунным.

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

Теорема 42. Пусть A продуктивное множество, K произвольное перечислимое множество. Тогда дополнение к K m -сводится к A.

(Из этого следует, что A является эффективно неперечислимым, см. выше.)

Пусть f функция, которая существует по определению продуктивности (и дает элемент вне подмножества с указанным номером).

Мы построим всюду определенную вычислимую функцию s с такими свойствами:

$$x \notin K \Rightarrow W_{s(x)}=\varnothing ;$$

$$x \in K \Rightarrow W_{s(x)}=\{ f(s(x))\}$$.

(второе свойство подразумевает, что f(s(x)) определено при $$x \in K$$ ). Прежде чем делать это с помощью теоремы о неподвижной точке, заметим, что в первом случае f(s(x)) определено и принадлежит A: поскольку множество с номером s(x) пусто и является подмножеством A, число f(s(x)) должно быть элементом A. Напротив, во втором случае f(s(x)) не принадлежит A. В самом деле, если бы это было не так, то множество Ws(x) было бы подмножеством A, и потому число f(s(x)) должно было бы быть элементом A, не входящим в это подмножество а оно входит.

Поэтому если нам удастся построить такую функцию s, то функция x -> f(s(x)) будет m -сводить дополнение множества K к множеству A, как мы и обещали. Как же ее строить?

Если бы во втором свойстве (для $$x \in K$$ ) стояло не f(s(x)), а, скажем, просто f(x), никакой проблемы бы не было. Как обычно, мы рассмотрели бы перечислимое множество пар

$$V = \{ \langle x,y\rangle \mid \text{$x\in K$ и $y=f(x)$}\};$$

сечения этого множества имели бы требуемый вид и осталось бы только воспользоваться тем, что нумерация главная. Но в нашем случае, когда в правой части второго свойства стоит f(s(x)), так просто поступить нельзя: как в истории о курице и яйце, для построения V нам надо иметь s(x), а для построения s(x) надо иметь V.

Именно такого рода трудности позволяет преодолевать теорема о неподвижной точке. Построим всюду определенную вычислимую функцию двух аргументов h с такими свойствами:

$$x \notin K \Rightarrow W_{h(x,t)}=\varnothing ;$$

$$x \in K \Rightarrow W_{h(x,t)}=\{ f(t)\}$$.

(Подобные вещи мы делали многократно последний раз в предыдущем абзаце. Отметим, что f(t) может быть и не определено, тогда под {f(t)} мы понимаем пустое множество.) По теореме о неподвижной точке (для перечислимых множеств) при каждом x функция $$t\hm\mapsto h(x,t)$$ имеет неподвижную точку, и, как мы говорили в разделе о неподвижной точке с параметром, эту неподвижную точку можно выбрать вычислимо зависящей от x. Таким образом, существует всюду определенная вычислимая функция s, для которой

Ws(x)=Wh(x,s(x))

при всех x. Это равенство можно продолжить:

$$W_{s(x)}=W_{h(x,s(x))}= \left\{ \begin{aligned} \varnothing, \text{ если $x\notin K$,}\\ \{f(s(x))\}, \text{ если $x\in K$} \end{aligned} \right.$$

- это ровно то, чего мы и хотели. Заметим, что значение f(s(x)) определено при всех x (иначе $$W_{s(x)}=\varnothing$$, и f(s(x)) должно быть определено). Тем самым, теорема о неподвижной точке позволяет отыскать взаимно согласованные яйцо и курицу и завершает доказательство.

Перечислимые множества, дополнения которых продуктивны, называются креативными (creative; иногда это слово переводят как " творческие "). Название объясняется так: это множество (точнее, его дополнение) более изобретательно, чем любой алгоритмический процесс: если кто-то предлагает способ порождать некоторые элементы из дополнения, то в ответ можно указать элемент дополнения, который нельзя получить таким способом.

Как мы видим, творческие множества, перечислимые множества с эффективно неперечислимым дополнением и m -полные множества один и тот же класс, и любые два множества из этого класса в некотором смысле изоморфны (отличаются лишь вычислимой перестановкой).

Если множество продуктивно, то можно порождать его элементы следующим индуктивным процессом. На первом шаге имеется пустое множество. Применив к нему продуктивную функцию (е функцию, существующую по определению продуктивного множества), мы получим некоторый элемент. Он образует одноэлементное подмножество. Применив к этому подмножеству продуктивную функцию, получим другой элемент. К полученному двухэлементному подмножеству можно снова применить продуктивную функцию и так далее. Получится бесконечная вычислимая последовательность элементов продуктивного множества. (Это мы уже делали, когда доказывали, что эффективно неперечислимое множество содержит бесконечное перечислимое подмножество.) Но этот индуктивный процесс можно " трансфинитно " продолжить, по крайней мере еще немного: имея перечислимое подмножество нашего продуктивного множества (множество членов последовательности), можно найти еще один элемент продуктивного множества (так сказать, элемент номер $$\omega$$ ). Добавим его к последовательности, снова применим продуктивную функцию, получится $$(\omega +1)$$ -ый элемент и так далее, затем получится новая последовательность, $$(\omega *2)$$ -й элемент, $$(\omega *3)$$ -й,..., $$\omega ^{2}$$ -й элемент и т.д.

Но, конечно, получить таким образом алгоритм, перечисляющий продуктивное (и потому неперечислимое) множество, не удастся.

  50. Не используя теорему о неподвижной точке (и теорему 42), покажите, что для всякого продуктивного множества A существует всюду определенная вычислимая функция f, для которой $$W_{n} \subset A$$ влечет $$f(n) \in A \setminus W_{n}$$. (Указание: чередуйте Wn с пустым множеством, как это делается при доказательстве леммы к теореме 41.)

Пары неотделимых множеств

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

Пусть A и B два непересекающихся множества (натуральных чисел). Напомним, что они называются неотделимыми, если не существует разрешимого множества, содержащего одно из них и не пересекающегося с другим. Это определение можно переформулировать так: если Wx и Wy два непересекающихся перечислимых множества, содержащие A и B соответственно, то объединение $$W_{x} \cup W_{y}$$ содержит не все натуральные числа. (Нам будет удобно обозначать перечислимые множества через Wx и Wy, считая, что W главное универсальное множество.)

Теперь ясно, как можно сформулировать эффективный вариант этого определения. Будем говорить, что непересекающиеся множества A и B эффективно неотделимы, если существует вычислимая функция h с таким свойством: если $$A \subset W_{x}$$, $$B \subset W_{y}$$ и $$W_{x} \cap W_{y}=\varnothing$$, то h(x,y) определено и $$h(x,y) \notin W_{x} \cup W_{y}$$.

Определение неотделимости можно сформулировать чуть-чуть иначе: не существует вычислимой функции $$\varphi _{n}$$, которая была бы всюду определенной, во всех точках множества A равнялась бы нулю, а во всех точках множества B единице. (Будем считать, что $$\phi$$ главная универсальная функция.) Соответственно изменится и эффективный вариант: множества A и B сильно эффективно неотделимы, если существует всюду определенная вычислимая функция h, которая по любому n указывает точку h(n), в которой функция $$\varphi _{n}$$ " ошибается ". Ошибка возможна трех видов: либо $$\varphi _{n}(h(n))$$ не определено, либо $$h(n) \in A$$, но $$\varphi _{n}(h(n))$$ не равно нулю, либо $$h(n) \in B$$, но $$\varphi _{n}(h(n))$$ не равно единице.

  51. Покажите, что из сильной эффективной неотделимости вытекает эффективная неотделимость (что оправдывает используемую нами терминологию).

Обратное утверждение также верно, но доказывается несколько сложнее, и мы к нему еще вернемся.

Существуют ли сильно эффективно неотделимые перечислимые множества? Легко понять, что стандартная диагональная конструкция дает пару таких множеств, а именно множества $$\{ x | \varphi _{x}(x)=1\}$$ и $$\{ x | \varphi _{x}(x)=0\}$$, для которых в качестве функции h можно взять тождественную функцию.

  52. Проверьте это.

Продолжая нашу аналогию (между множествами и парами), определим понятие m -сводимости для пар. Здесь тоже будет два варианта. Пусть $$\langle A,B\rangle$$ и $$\langle C,D\rangle$$ две пары непересекающихся перечислимых множеств ( A не пересекается с B, а C с D ). Будем говорить, что вычислимая всюду определенная функция f m -сводит $$\langle A, B\rangle$$ к $$\langle C,D\rangle$$, если $$f(A) \subset C$$ и $$f(B) \subset D$$.

  53. (а) Покажите, что если f сводит $$\langle A,B\rangle$$ к $$\langle C,D\rangle$$ и C отделимо от D разрешимым множеством, то и A отделимо от B разрешимым множеством. (б) Покажите, что если f сводит $$\langle A,B\rangle$$ к $$\langle C,D\rangle$$ и пара $$\langle A,B\rangle$$ эффективно неотделима, то и пара $$\langle C,D\rangle$$ эффективно неотделима. (в) Покажите, что если f сводит $$\langle A,B\rangle$$ к $$\langle C,D\rangle$$ и пара $$\langle A,B\rangle$$ сильно эффективно неотделима, то и пара $$\langle C,D\rangle$$ сильно эффективно неотделима.

Определение сводимости можно усилить, потребовав дополнительно, чтобы при $$x \notin A \cup B$$ выполнялось $$f(x) \notin C \cup D$$ (другими словами, f должна сводить A к C и одновременно B к D ). В этом случае мы будем говорить, что f сильно сводит пару $$\langle A,B\rangle$$ к паре $$\langle C,D\rangle$$.

Теперь мы можем определить m -полноту и сильную m -полноту для пары непересекающихся перечислимых множеств, требуя m -сводимости (соответственно сильной m -сводимости) любой такой пары к данной.

  54. Покажите, что если пара является сильно эффективно неотделимой, то она является сильно m -полной. (Указание. Пусть пара $$\langle A,B\rangle$$ сильно эффективно неотделима, а $$\langle K,L\rangle$$ любая пара непересекающихся перечислимых множеств. По любому натуральному числу x можно построить вычислимую функцию $$\psi _{x}$$ с таким свойством: если $$x \in K$$, то $$\psi _{x}$$ всюду определена и отличается от единицы лишь в конечном числе точек, причем все эти точки принадлежат A ; если $$x \in L$$, то $$\psi _{x}$$ всюду определена и отличается от нуля лишь в конечном числе точек, причем все эти точки принадлежат B ; если $$x \notin K \cup L$$, то $$\psi _{x}$$ равна нулю на A и единице на B. Чтобы построить такую функцию, перечисляем K и L ; пока x не обнаружилось в одном из этих множеств, добавляем в график $$\psi _{x}$$ пары вида $$\langle a,0\rangle$$ и $$\langle b,1\rangle$$ ; когда x обнаруживается, перестраиваемся. Далее остается воспользоваться свойствами главной нумерации $$\phi$$ и сильной эффективной неотделимостью A и B.)

  55. Покажите, что всякая m -полная пара является сильно эффективно неотделимой. (Указание: сильно эффективно неотделимая пара существует и к ней сводится.)

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

  56. Пусть $$\langle A,B\rangle$$ эффективно неотделимая пара непересекающихся перечислимых множеств. Покажите, что она является сильно m -полной. (Указание. Пусть K и L произвольные непересекающиеся перечислимые множества. Пусть h функция из определения эффективной неотделимости (множеств A и B ). С помощью теоремы о неподвижной точке постройте всюду определенные вычислимые функции x(n) и y(n) с такими свойствами: (1) если $$n \in K$$, то Wx(n)=A, $$W_{y(n)}=B \cup \{ h(x(n),y(n))\}$$ ; (2) если $$n \in L$$, то $$W_{x(n)}=A \cup \{ h(x(n),y(n))\}$$, Wy(n)=B ; (3) если $$n \notin K \cup L$$, то Wx(n)=A, Wy(n)=B. Выведите отсюда, что при $$n \in K$$ значение h(x(n),y(n)) определено и принадлежит A, при $$n \in L$$ значение h(x(n),y(n)) определено и принадлежит B, а при $$n \notin K \cup L$$ значение h(x(n),y(n)) определено и лежит вне $$A \cup B$$.)

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

Более точно, пусть имеются непересекающиеся множества A и B. Назовем два числа $$\langle A,B\rangle$$ -эквивалентными в любом из следующих трех случаев: оба они принадлежат A, оба они принадлежат B или оба они не принадлежат $$A \cup B$$. (Таким образом, есть три класса эквивалентности множество A, множество B и остаток.)

  57. Пусть $$\langle A,B\rangle$$ сильно m -полная пара непересекающихся перечислимых множеств. Покажите, что по любому числу k можно алгоритмически получать сколь угодно много различных чисел, которые будут $$\langle A,B\rangle$$ -эквивалентны k. (Указание: действуйте по аналогии с доказательствами теоремы 22 и леммы к теореме 41.)

  58. Пусть $$\langle A_1,B_1\rangle$$ и $$\langle A_2, B_2\rangle$$ две сильно m -полные пары непересекающихся перечислимых множеств. Тогда они вычислимо изоморфны в следующем смысле: существует вычислимая перестановка (биекция) i : N -> N, при которой i(A1)=A2 и i(B1)=B2. (Указание: действуйте по аналогии с доказательствами теорем 23 и 41.)