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

Небольшая модификация рассуждения позволяет до­казать усиление доказанной выше теоремы:

Теорема 12. Существует вычислимая функция, при­нимающая только значения 0 и 1 и не имеющая всюду определённого вычислимого продолжения.

<] Вместо функции а"(х) = й(х)-\-1 можно рассмотреть функцию

М, еслиф) = 0, v ;    \ 0, если ё(х) > 0

(имеется в виду, что й"(х) не определено, если й(х) не определено). Тогда любое всюду определённое продолже­ние функции ё" будет по-прежнему отличаться от ё всю­ду и потому не будет вычислимым. >

Этот результат можно перевести на язык перечисли­мых множеств. Говорят, что два непересекающихся мно­жества X и У отделяются множеством С, если множест­во С содержит одно из них и не пересекается с другим.

Теорема 13. Существуют два непересекающихся пе­речислимых множества X и У, которые не отделяются никаким разрешимым множеством.

<] В самом деле, пусть ё — вычислимая функция, при­нимающая только значения 0 и 1 и не имеющая всюду определённого вычислимого продолжения. Пусть X = = {х | ё(х) = 1} и У = {х | ё(х) = 0}. Легко видеть, что множества X и У перечислимы. Пусть они отделяются разрешимым множеством С; будем считать, что С со­держит X и не пересекается с У (если наоборот, перей­дём к дополнению). Тогда характеристическая функция множества С (равная 1 внутри С и 0 вне него) продол­жает ё. >

Заметим, что этот результат усиливает утверждение о существовании перечислимого неразрешимого множе­ства (если два множества не отделимы разрешимыми множествами, то ни одно из них не разрешимо).

24. Как описать построенные неречислимые неотделимые множества в терминах универсальной функции и(п,з;)1

25. Покажите, что существует счётное число непересека­ющихся иеречислимых множеств, никакие два из которых не­льзя отделить разрешимым множеством.