8.3. Операция скачка

Мы хотим показать, что класс £„ совпадает с классом всех А-перечислимых множеств для некоторого множе­ства А (зависящего от п, естественно). Чтобы объяснить, что это за множество, нам понадобится так называемая операция скачка.

Пусть X — произвольное множество. Среди Х-пере­числимых множеств есть универсальное. Это множество будет т-полным в классе Х-перечислимых множеств в том смысле, что все другие Х-перечислимые множества к нему т-сводятся. Сводящая функция, как мы видели, имеет вид х I—У [п, х] (и вычислима безо всякого оракула, как того и требует определение т-сводимости). Будем обозначать через X1 любое т-полное множество в классе Х-перечислимых множеств. Можно сказать, что X' опре­делено с точностью до т-эквивалентности.

Более формально, будем говорить, что множества Р и <5 являются т-эквивалентными, если Р <Ст т <Ст $Ст Р. (Легко видеть, что это действительно отношение эквивалентности.) Класс эквивалентных множеств назы­вают т-степенью. Таким образом, можно сказать, что мы для каждого множества X определили некоторую т-степень X'.

Аналогичным образом определяют Т-степени (кото­рые называют также тьюринговыми степенями или сте­пенями неразрешимости) как классы Г-эквивалентных множеств; множества Р т называют Т-эквивалент-ными, или эквивалентными по Тьюрингу, если Р <Ст <5 и <5 Р, то есть если каждое из множеств разреши­мо относительно другого. Если множества Р т экви­валентны по Тьюрингу, то класс Р-вычислимых функ­ций совпадает с классом (^-вычислимых функций (а класс Р-перечислимых множеств совпадает с классом (5-пере-числимых множеств). Введя понятие Г-степени, можно сказать, что т-степень X' определяется Г-степенью мно­жества X и тем самым определено отображение мно­жества всех Г-степеней в множество всех т-степеней. Это отображение называют операцией скачка; множест­во (точнее, т-степень) X1 называют скачком множества (точнее, Г-степени) X.

64. Могут ли при этом отображении разные 7-степени пе­реходить в одну и ту же т-степень?

65. Докажите, что любые два т-полных в классе 1]„ мно­жества вычислимо изоморфны (отличаются вычислимой пе­рестановкой).

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

Обычно, впрочем, операцию скачка рассматривают на Г-степенях, считая её результатом Г-степень, содер­жащую X' (это законно, так как Г-классификация более грубая).

Нам понадобятся следующие Г-степени: 0 (степень, содержащая все разрешимые множества), 0' (её скачок, степень т-полного перечислимого неразрешимого мно­жества; мы её уже рассматривали), затем 0" (скачок сте­пени 0'), 0"' и так далее; вообще 0<"+1) = (О^))'.

Теорема 56. При любом п ^ 1 класс £„ совпадает с классом всех 0(™-1)-перечислимых множеств.

(Пока что мы знаем это при п = 1.)

<] Докажем сначала, что все £„-множества перечисли­мы относительно О'™-1). Это делается индукцией по п. При п = 1 это известно. Рассмотрим теперь произволь­ное множество X из £2. По определению,

х <Е X <5 ЗуУгЩх, у, х),

где К — разрешимое свойство. Свойство УгК(х,у,г) имеет перечислимое отрицание. Это отрицание разре­шимо относительно 0', так как т-сводится к т-пол­ному перечислимому множеству. Значит, и само свой­ство УгК(х,у,г) разрешимо относительно 0'. Поэтому его проекция, множество X, перечислимо относитель­но о'.

Аналогично можно рассуждать и для больших п. Если X принадлежит £3, то

ЗуЩх, у),

где К принадлежит Щ. Отрицание К принадлежит £2 (по доказанному), поэтому О'-перечислимо, поэтому □"-раз­решимо, поэтому само К тоже 0"-разрешимо, а его про­екция 0"-перечислима,

Первая половина теоремы доказана.

Для доказательства второй половины нам потребует­ся некоторое свойство классов £„ и П„. Рассмотрим ка­кую-нибудь вычислимую нумерацию всех конечных мно­жеств натуральных чисел. Обозначим через Dx конеч­ное множество номер х. Для произвольного множества А рассмотрим множество Subset ( А) всех конечных подмно­жеств А, точнее, множество всех их номеров:

х б Subset (А) о Dx С А.

Лемма 1. Если множество А принадлежит классу £„ [или П„], то множество Subset (А) также принадлежит классу £„ [соответственно П„].

(Утверждение этой леммы обобщает сформулирован­ное в задаче 62 утверждение о множестве А х А: теперь мы рассматриваем не пары, а произвольные кортежи.)

Доказательство леммы. Пусть множество А принад­лежит, например, классу £3:

х <Е А<5 3yiz3tR(x, у, z,t),

где R — разрешимое свойство. Тогда можно записать свойство {х\,..., хп} С А следующим образом:

3{yi,.. .,ynyi{z\,. ..,zn)3{t\,... ,tn)[R(x\,y\,z\,t\)/\...

... A R{xn, уп, /*п, tn)]

Эта формула использует кванторы по кортежам нату­ральных чисел (переменной длины), но их можно заме­нить на номера этих кортежей в какой-нибудь вычи­слимой нумерации. При этом стоящая под кванторами формула (она записана несколько условно: символиче­ская конъюнкция на самом деле имеет переменную дли­ну) является разрешимым свойством номеров кортежей, поэтому вся правая часть является £„-свойством.

(На самом деле мы допустили ещё одну вольность ре­чи: правая часть является не свойством конечного мно­жества {х\,...,хп}, а свойством кортежа (упорядочен­ной последовательности) (х\,..., хп). Но переход от но­мера множества к номеру какого-то кортежа, содержа­щего все его элементы, вычислим, так что проблемы тут нет.)

Лемма доказана.

67. Докажите, что если А принадлежит классу 1]„ [П„], то и множество Intersect^) номеров конечных множеств, пере­секающихся с А, принадлежит классу 1]„ [П„].

68. Пусть свойство Щз;, у) пар натуральных чисел принад­лежит классу Yi„. Покажите, что свойство

S(x) = (Чу < х) Щх, у)

принадлежит 1]„. (Ограниченный квантор (Vy ^ з;) читается как «для всех у, не превосходящих з;».)

Переходя к дополнениям, мы немедленно получаем та­кое утверждение:

Лемма 2. Если А принадлежит классу £„ [П„], то мно­жество Disjoint (А), состоящее из номеров конечных мно­жеств, не пересекающихся с А, принадлежит П„ [£„].

Доказательство леммы. Не пересекаться с А означа­ет быть подмножеством дополнения к А, и остаётся вос­пользоваться предыдущей леммой и тем, что дополнение к множеству из класса £„ [П„] лежит в классе II,,, [£„]. Лемма доказана.

Теперь мы можем перейти к доказательству того факта, что все множества, перечислимые относитель­но О'™-1), принадлежат классу £„. Это также доказыва­ется индукцией по п.

Начнём с первого нетривиального случая: почему множество, перечислимое относительно 0', лежит В £2? (Здесь можно было бы применить критерий О'-вычисли-мости, приведённый выше, но мы предпочитаем действо­вать по общей схеме, которая годится и для больших п.)

Итак, пусть некоторое множество А перечислимо от­носительно 0'. Тогда оно перечислимо относительно не­которого перечислимого множества В, то есть перечи­слимо относительно характеристической функции Ь мно­жества В. Согласно доказанному нами выше критерию (теорема 45, с. 79), это означает, что существует пере­числимое множество Q пар вида (x,t), где х — число, а

t — образец, для которого

х £ А -<=> 3t[((x,t) £ Q) и (6 продолжает t)].

Образец t представляет собой функцию, определённую на конечном множестве и принимающую значения 0 и 1. (Если у i есть какие-то другие значения, то он не может быть частью характеристической функции множества В и роли не играет.) Условие Л продолжает t» в терми­нах множества В звучит так: В содержит множество тех аргументов, на которых t принимает значение 1, и не пересекается с множеством тех аргументов, на которых t принимает значение 0. Поэтому вместо образцов мож­но говорить о парах конечных множеств; тогда вместо Q надо рассмотреть перечислимое множество Р троек ви­да (х, и, v) и написать так:

х £ А -<=> 3u3v[((x, и, v) £ Р) и (Du содержится в В)

и (Dv не пересекается с В)].

Теперь вместо <sDu содержится в В» напишем «и £ £ Subset (В) !>, а вместо <sDv не пересекается с В» на­пишем «v £ Disjoint(B)i>. Остаётся заметить, что все три свойства, соединённые союзом «и» в правой части, при­надлежат классу £2 и даже меньшим классам. Именно, первые два принадлежат классу , так как Р и В пе­речислимы (для второго свойства применяем лемму 1). Третье же принадлежит классу П\ по лемме 2. Поэто­му их конъюнкция принадлежит классу £2, и операция проекции (кванторы 3«3г>) не выводит за пределы этого класса. Случай п = 2 разобран.

Далее, если какое-то множество А перечислимо отно­сительно 0", то по определению это означает, что оно пе­речислимо относительно некоторого В, которое перечи­слимо относительно 0' и потому лежит в £2- После этого все рассуждения проходят точно так же со сдвигом на 1. Аналогично разбираются и все следующие значения п. >

Из доказанной теоремы немедленно вытекает такое следствие:

Теорема 57. Пересечение классов Еп П Пп совпадает с классом разрешимых относительно О^™-1) множеств.

<] В самом деле, релятивизованная теорема Поста (те­орема 2, с. 13) утверждает, что некоторое множество является Х-разрешимым тогда и только тогда, когда оно и его дополнение Х-перечислимы (здесь X — произволь­ный оракул). >

Теорема 58. Класс Е„1Ш„ является собственным под­множеством класса Е„+1 П П„+1.

<] Вспомним, что такое 0<"). Это — степень множе­ства X, являющегося т-полным в классе 0(™-1)-перечис-лимых множеств. Поскольку X является т-полным в ука­занном классе, оно не 0*-"_1)-разрешимо, то есть его до­полнение не является 0(™-1)-перечислимым.

Значит, по доказанной только что теореме X принад­лежит классу Е„, а его дополнение — нет. Напротив, до­полнение к X принадлежит П„, но не Е„. Рассмотрим те­перь «соединение» множества X с его дополнением, т. е. множество

{2п\пеХ}1){2п + 1\ п£ X}.

К этому множеству т-сводятся как X, так и его до­полнение, поэтому оно не может принадлежать ни Е„, ни П„. С другой стороны, оно, очевидно, разрешимо от­носительно X, поэтому по доказанной теореме принад­лежит и Е„+1, и П„+1. >