3.3. Главные универсальные множества

По аналогии с функциями, перечислимое множест­во Ш С N х N называется главным универсальным пере­числимым множеством (для класса всех перечислимых подмножеств М), если для любого другого перечислимого множества V С N х N найдётся такая всюду определённая вычислимая функция в : N —У N, что

(п, х) 6 V     {в(п), ж) е Ш

для всех п и х. (Очевидно, что из этого свойства следует универсальность.)

Как и для функций, можно перейти к нумерациям. Ка­ждое множество II С N х N задаёт нумерацию некоторого семейства подмножеств натурального ряда: число п явля­ется номером п-го сечения 11п = {х | (п, х) £ и}. Перечи­слимое подмножество множества N х N задаёт нумерацию некоторого семейства перечислимых подмножеств нату­рального ряда; такие нумерации называют вычислимы­ми. Перечислимое множество Шг С N х N универсально, если и только если всякое перечислимое подмножество натурального ряда имеет ДО7"-номер; оно является глав­ным тогда и только тогда, когда любая вычислимая ну­мерация V (любого семейства перечислимых множеств) вычислимо сводится к И^-нумерации в том смысле, что Уп = (п) для некоторой вычислимой функции в и для всех п.

Теорема 18. Существует главное универсальное пере­числимое множество Ш С N х N.

<] Эта теорема является очевидным следствием тако­го утверждения:

Лемма. Область определения главной универсальной функции для класса вычислимых функций одного аргу­мента является главным универсальным множеством для класса перечислимых подмножеств N.

Доказательство леммы. Пусть и — главная уни­версальная функция, а IV — область её определения. Пусть V С N х N — произвольное перечислимое мно­жество. Рассмотрим вычислимую функцию С с обла­стью определения V. Поскольку функция II является главной, найдётся всюду определённая вычислимая функ­ция в: N —У Ш, для которой Сп = при всех п. Тогда равны и области определения функций Сп и то есть Уп = Ш^п). >

32. Постройте главное универсальное множество непо­средственно, используя универсальное подмножество № (но аналогии с выше приведённым построением главной универ­сальной функции).

Как и для функций, мы теперь можем доказывать, что различным операциям над множествами соответ­ствуют вычислимые преобразования номеров. Вот лишьодин пример такого рода:

Теорема 19. Пусть И7 С N х N — главное универ­сальное перечислимое множество. Тогда по И^-номерам двух перечислимых множеств можно алгоритмически по­лучить номер их пересечения: существует такая вычи­слимая всюду определённая функция двух аргументов в, что

И7,(т>„) = шт п шп

для любых двух т и п.

<] Рассмотрим множество V С Н х Н, определённое так:

{[т, п], х) 6 V     х 6 (Шт, П М^)

(здесь квадратные скобки обозначают номер пары) и применим к нему определение главного универсального множества. >

Как и для функций, понятие вычислимости последова­тельности перечислимых множеств может быть опреде­лено двояко: можно считать вычислимой последователь­ность Уо, У\,... сечений произвольного перечислимого множества V, а можно требовать, чтобы по г можно бы­ло алгоритмически указать один из номеров г-г о члена последовательности в главной нумерации. Эти определе­ния равносильны (доказательство полностью аналогично рассуждению для функций).