8.1. Классы Е„ и П„

Мы уже говорили, что перечислимые множества мож­но эквивалентно определить как проекции разрешимых множеств: множество А С N перечислимо тогда и толь­ко тогда, когда существует разрешимое множество В С С Н х Н, проекцией которого оно является. Если отож­дествлять множества со свойствами, то можно сказать, что свойство А(х) натуральных чисел перечислимо тогда и только тогда, когда его можно представить в виде

А(х)     ЗуВ(х, у),

где В(х,у) — некоторое разрешимое свойство.

(В этом разделе мы предполагаем знакомство читате­ля с простейшими логическими обозначениями: квантор Зх читается как «существует х», квантор Уш читается как «для всех х», знак Л читается как «и» и называется конъюнкцией, знак V читается как «или» и называется дизъюнкцией, знак -> читается как «неверно, что» и на­зывается отрицанием. Как и раньше, знак -<=> означает равносильность.)

Возникает естественный вопрос: что можно сказать про другие наборы кванторов? Например, какие свой­ства представимы в виде

А(х)     ЗуЗхС(х, у, х),

где С — разрешимое свойство троек натуральных чи­сел? Легко сообразить, что это по-прежнему перечи­слимые множества. В самом деле, два подряд идущих квантора одного вида можно заменить одним, исполь­зовав вычислимую нумерацию пар (которую мы обозна­чаем квадратными скобками): свойство С, для которо­го С'(х, [у, г]) -<=> С(х,у,г), также разрешимо, и А(х) -<=> ЗшС'(х, ш).

Другой вопрос: какие свойства представимы в виде

А(х)     УуВ(х, у)

Классы En и Пп

где В(х,у) — некоторое разрешимое свойство? Ответ: те, отрицания которых перечислимы (как иногда гово­рят, коперечислимые). В самом деле, переходя к отрица­ниям, имеем

^А(х)     -ЫуВ(х, у)     Зу(^В(х, у)),

а разрешимые свойства остаются разрешимыми при пе­реходе к отрицаниям.

Дадим общее определение. Свойство А принадлежит классу £„, если его можно представить в виде

А(х)     Зг/цУг/гЗда • ■■В(х,уг,у2, ■ ..,уп)

(в правой части стоит п чередующихся кванторов) для некоторого разрешимого свойства В. Если в правой ча­сти поставить п чередующихся кванторов, начиная с квантора всеобщности V, то получится определение клас­са П„.

Отметим два свойства, которые мы по существу уже доказали:

Теорема 51. (а) Определение класса £„ [П„] не из­менится, если в правой части разрешить большее число кванторов и требовать, чтобы первый квантор был кван­тором существования [всеобщности] и число групп оди­наковых стоящих рядом кванторов равнялось п. (б) От­рицания свойств из класса £„ принадлежат классу II,,, и наоборот.

<] Для доказательства первого утверждения доста­точно соединять рядом стоящие одинаковые кванторы с помощью нумерации пар. Для доказательства второго надо проносить отрицание внутрь (меняя тип квантора), пока оно не окажется у разрешимого свойства (где оно роли не играет). >

Мы говорили о свойствах; на языке множеств можно сказать так: множества класса £„ получаются из раз­решимых с помощью последовательности операций «про­екция - дополнение - проекция - дополнение - ... - проек­ция», в которой всего п операций проекции. Каждая опе­рация проекции уменьшает размерность множества (чи­ело аргументов у свойства) на единицу, так что начинать надо с разрешимых подмножеств

Теорема 52. Пересечение и объединение двух мно­жеств из класса £„ принадлежит £„. Пересечение и объ­единение двух множеств из класса П„ принадлежит П„.

<] Удобно выразить это утверждение на логическом языке, сказав, что конъюнкция и дизъюнкция любых двух свойств из класса £„ лежат в том же классе (ана­логично для П„). На этом же языке удобно провести и доказательство: если, скажем,

А(х) 3yizB(x, у, z), С(х) -<=> 3iiivD(x, и, v),

то

А(х) Л С(х) <3 3y3uizVv[B(x, у, z) Л D(x, и, v)],

записанное в квадратных скобках свойство разрешимо и остаётся только соединить пары кванторов в один, как объяснялось выше. Аналогично можно действовать для классов £„ и П„ при произвольном п. >

Мы определяли классы £„ и П„ для множеств нату­ральных чисел; аналогичным образом это можно сделать и для множеств пар натуральных чисел, троек и вообще любых «конструктивных объектов». Заметим, что про­екция множества пар, принадлежащего классу £„, также принадлежит £„ (поскольку два квантора существования в начале можно объединить в один).

Добавляя фиктивные кванторы, легко убедиться, что каждый из двух классов £„ и П„ содержится в каждом из классов E„+i и П„+і. Можно написать ещё так:

S„ U 11,, С S„_|_i П 11.... | і.

Теорема 53. Классы £„ и П„ «наследственны вниз» от­носительно m-сводимости: если А <Ст В и В Є £„ [В Є Є П„], то и А Є £„ [А Є П„].

<] В самом деле, пусть А сводится к В с помощью всю­ду определённой вычислимой функции /, то есть х Є А

f(x) Є В. Пусть В принадлежит, например, классу £3,то есть

Зг/У'гЗиЩх, у, г, и),

где К — некоторое разрешимое свойство. Тогда

х <Е А<5 f(x) <Е В     3,у^73иК(Лх),у, х, и),

и осталось заметить, что Л(/(ш), у, г, и) (как свойство четвёрки (х,у, г, и'}) разрешимо. >

62. Докажите, что если множество А принадлежит клас­су 1]„, то множество А х А также принадлежит этому классу.

63. Докажите, что если множества А и В принадлежат классу 1]„, то их разность А \ В принадлежит классу Ип+1 П

П П„+1.