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

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

Пусть А ж В — два непересекающихся множества (на­туральных чисел). Напомним, что они называются неот­делимыми, если не существует разрешимого множества, содержащего одно из них и не пересекающегося с дру­гим. Это определение можно переформулировать так: ес­ли Шх ж ШГу — два непересекающихся перечислимых мно­жества, содержащие А ж В соответственно, то объедине­ние Шх и Шу содержит не все натуральные числа. (Нам будет удобно обозначать перечислимые множества че­рез Шх ж Шгу, считая, что IV — главное универсальное множество.)

Теперь ясно, как можно сформулировать эффектив­ный вариант этого определения. Будем говорить, что не-пересекающиеся множества А ж В эффективно неотде­лимы, если существует вычислимая функция К с таким свойством: если А С УУХ, В С и Шх П = 0, то Ь,(х,у) определено и Ь,(х,у) ^      и ДОу.

Определение неотделимости можно сформулировать чуть-чуть иначе: не существует вычислимой функции (рп, которая была бы всюду определённой, во всех точках множества А равнялась бы нулю, а во всех точках мно­жества В — единице. (Будем считать, что (р — глав­ная универсальная функция.) Соответственно изменится и эффективный вариант: множества А ж В сильно эффек­тивно неотделимы, если существует всюду определённая вычислимая функция К, которая по любому п указывает точку Ь,(п), в которой функция (рп «ошибается». Ошибка возможна трёх видов: либо у„(/г(п)) не определено, либо Ь,(п) £ А, но 1рп(Ь,(п)) не равно нулю, либо Ь,(п) £ В, но <£>„(/г(п)) не равно единице.

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

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

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

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

Продолжая нашу аналогию (между множествами и па­рами), определим понятие т-сводимости для пар. Здесь тоже будет два варианта. Пусть (А, В) ж (С, О) — две пары непересекающихся перечислимых множеств (А не пересекается с В, а С — с О). Будем говорить, что вычи­слимая всюду определённая функция / т-сводит (А, В) к {С, О), если        С С и 1(В) С О.

52. (а) Покажите, что если / сводит (А, В) к {С, О) и С отделимо от О разрешимым множеством, то и А отделимо от В разрешимым множеством, (б) Покажите, что если / сво­дит (А, В) к {С, U) и пара (А, В) эффективно неотделима, то и пара {С, U) эффективно неотделима, (в) Покажите, что ес­ли / сводит (А, В) к {С, U) и пара (А, В) сильно эффективно неотделима, то и пара {С, D) сильно эффективно неотделима.

Определение сводимости можно усилить, потребовав дополнительно, чтобы при X f A U В выполнялось f(x) (f (f С U D (другими словами, / должна сводить А к С и одновременно В к D). В этом случае мы будем говорить, что / сильно сводит пару (А, В) к паре (C,D).

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

53. Покажите, что если пара является сильно эффективно неотделимой, то она является сильно пг-нолной. (Указание. Пусть пара (А, В) сильно эффективно неотделима, а {К, L) — любая пара непересекающихся иеречислимых множеств. По любому натуральному числу х можно построить вычислимую функцию фх с таким свойством: если х £ К, то фх всюду определена и отличается от единицы лишь в конечном числе точек, причём все эти точки принадлежат А; если х £ L, то фх всюду определена и отличается от нуля лишь в конечном числе точек, причём все эти точки принадлежат В; если х £ К U L, то фх равна нулю на А и единице на В. Чтобы построить такую функцию, перечисляем К и L; пока х не обнаружилось в одном из этих множеств, добавляем в график фх нары вида (а, 0) и (Ь, 1); когда х обнаруживается, перестраиваемся. Далее остаётся воспользоваться свойствами главной нумерации <р и сильной эффективной неотделимостью А и В.)

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

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

55. Пусть (А, В) — эффективно неотделимая пара непе­ресекающихся множеств. Покажите, что она является сильно тга-иолной. (Указание. Пусть К и Ь— произвольные непересе­кающиеся перечислимые множества. Пусть Н — функция из определения эффективной неотделимости (множеств А и В). С помощью теоремы о неподвижной точке постройте всю­ду определённые вычислимые функции з;(п) и у(п) с таки­ми свойствами: (1) если п £ К, то ИЛ^я) = А, \¥у^ = В и иЩх(п), {/(«))}; (2) если п £ Ц то 1¥х(п) = АиЩх(п), {/(«))}, \¥я(„) = В; (3) если п £ КиЬ, то \¥х(„) = А, \¥я(„) = В. Выве­дите отсюда, что при п £ К значение к(з;(п), у(п)) определено и принадлежит А, при п £ Ь значение к(з;(п), у(п)) определе­но и принадлежит В, а при п £ К и Ь значение к(з;(п), у(п)) определено и лежит вне А и В.)

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

Более точно, пусть имеются непересекающиеся мно­жества А и В. Назовём два числа (А, _В)-эквивалентными в любом из следующих трёх случаев: оба они принадле­жат А, оба они принадлежат В или оба они не принадле­жат А и В. (Таким образом, есть три класса эквивалент­ности — множество А, множество В и остаток.)

56. Пусть (А, В) — сильно т-полная пара перечислимых множеств. Покажите, что по любому числу к можно алго­ритмически получать сколь угодно много различных чисел, которые будут (А, й)-эквивалентны к. (Указание: действуйте по аналогии с доказательствами теоремы 22 и леммы к тео­реме 41.)

57. Пусть {А\, В\) и (А-2, В-2) — две сильно т-иолные пары перечислимых множеств. Тогда они вычислимо изоморфны в следующем смысле: существует вычислимая перестановка (биекция) г: Щ —> К, при которой г(А\) = В\ и «"(Лг) = #2-(Указание: действуйте по аналогии с доказательствами тео­рем 23 и 41.)