8.2. Универсальные множества в Е„ и П„

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

Теорема 54. Для любого п в классе £„ существует множество, универсальное для всех множеств класса £„. (Его дополнение будет универсальным в классе П„.)

Говоря об универсальном множестве из класса £„, мы имеем в виду множество пар натуральных чисел, которое принадлежит классу £„ и среди сечений которого встре­чаются все множества натуральных чисел, принадлежа­щие классу £„.

<] Для класса (перечислимых множеств) существо­вание универсального множества мы уже обсуждали. С его помощью можно построить универсальные множе­ства и для более высоких классов иерархии. (Начинать надо с первого уровня, так как на «нулевом» уровне не существует универсального разрешимого множества.)

По определению свойства класса Щ имеют вид 3(х) -<=> -<=> УуЗгК(х,у,г), где К — некоторое разрешимое свой­ство. Но их можно эквивалентно определить и как свой­ства вида 3(х) -<=> Уг/Р(ш, у), где Р — некоторое перечи­слимое свойство. Теперь уже видно, как построить уни­версальное множество класса Щ. Возьмём универсальноеперечислимое свойство и(п,х,у), из которого фиксаци­ей различных п получаются все перечислимые свойства пар натуральных чисел. Тогда из свойства Т(п, х) = = Уу11(п,х,у) при различных натуральных п получаются все Щ-свойства натуральных чисел. С другой стороны, само свойство Т по построению принадлежит классу Щ.

Дополнение к универсальному Щ-множеству будет, очевидно, универсальным Ег-множеством.

Аналогично можно действовать и для £3- и Щ-мно-жеств (удобнее сначала рассуждать о Ез-множествах, так как в них внутренний квантор является квантором существования и задаёт перечислимое множество), и во­обще для £„- и П„-множеств. >

Теорема 55. Универсальное Е„-множество не принад­лежит классу П„. Аналогичным образом, универсальное П„-множество не принадлежит классу £„.

<] Рассмотрим универсальное Е„-свойство Т(т, х). По определению это означает, что среди его сечений (полу­чающихся, если зафиксировать т) есть все Е„-свойства. Пусть Т принадлежит классу П„. Тогда его диагональ, свойство О(х) = Т(х,х), также принадлежит классу П„ (например, потому, что О <Ст Г), а её отрицание, свой­ство ^О(х), принадлежит классу £„. Но этого не может быть, так как отлично от всех сечений свойства Т (оно отличается от т-го сечения в точке т), а Т универ­сально. >

Из этой теоремы следует, в частности, что любой из классов £„ и П„ является собственным подмножеством любого из классов Е„+1 и П„+1. (Мы увидим вскоре, что даже объединение £„1Ш„ является собственным подмно­жеством пересечения Е„+1 П П„+1.)