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

§ 10. Универсальные и креативные системы множеств

Понятия ш-универсальности и креативности, определенные в § 8 для отдельно взятых числовых множеств, естественно распространяются на пары, тройки, четверки, вообще ге-ки множеств. С каждой ге-кой множеств а,- . . . . . ., а„ однозначно связываем нумерацию семейства символических объектов а,,, а, . . а„, называя номерами : объекта все числа из а,- (г = 1, . . ., п). Эти нумерации оказываются полными тогда и только тогда, когда ге-ки множеств ш-универсальны. Общие теоремы § 9, примененные к рассматриваемым частным нумерациям, дают основные свойства »г-универсальных ге-ок множеств. В заключительной части рассматриваются понятия продуктивности и отделимости для пар множеств.

10.1. ш-универсальные системы множеств. По анало- ? гии с ш-сводимостью множеств, определенной в п. 8.1, говорят, чтопоследовательность множеств р, . . ., Р„ Ш-СВО-дится к последовательности множеств а, . . ., ос„, если существует такая рекурсивная функция / {х)\ что для всех X

а;б / (ж) 6 (j = 1, 2,. , ., п). (1)

Как и ранее, легко убеждаемся, что отношение ш-сводимости ге-ок множеств транзитивно.

Система множеств <aj, . . ., а„> называется т-универ-салъной /г-кой множеств, если выполнены следующие условия:

а) множества а, . . an попарно не имеют общих элементов;

б) каждое из множеств . . ., а„ рекурсивно пере- числимо;

в) каждая «-ка <Pi, . . ., р„> попарно не пересекаюпщх-

ся рекурспвно перечислпмых множеств гя-сводпма к п-ке аз, . . ., а„>.

Для ге = 1 это определение обращается в определение \ ш-универсального множества (п. 8.1). С другой стороны, в определении ш-унпверсальных ге-ок мнонхсств не требуется, чтобы множества Р,. . ., р„ бы.ли непустыми. Поэтому пз ш-универсальностп какой-нибудь спстелш мно- % жеств а, . . ., (Хп вытекает «t-унпверсальность каждой ее .

подсистемы а,,, «г,, . . ., «ги, в частности, ш-универсаль-ность каждого отдельного множества входящего в

??г-универсальную систему.

Обратное, конечно, неверно: далеко не каждая система, состоящая из п нонарно не нересекающихся т-универсаль-пых множеств, является мг-универсальной ге-кой мно-;кеств (см. п. 10.3).

Заметим еще, что объединение всех множеств иг-уни-версальной ге-ки не может совпадать с натуральным рядом. Действительно, противное означало бы, что ш-универ-сальное множество имеет рекурсивно иеречислимое дополнение и • • • и го быть не мо?кет, так как дополнение ш-универсального множества не рекурсивно.

Из определения т-уинверсальных систем множеств непосредственно вытекают следующие их свойства. Пусть <ai, . . ., a,i> - ж-универсальная система. Тогда

а) для любой частично рекурсивной функции f (х) .множества (aJ, . . ., (а) попарно не пересекаются и рекурсивно перечислимы;

б) для каждой системы Pj, . . ., Рп попарно не пересекающихся рекурсивно перечислимых мнооюеств существует рекурсивная функция f (х), для которой Pi = (а),. . .

. . ., Рп = /- Ы-

Обратное также верно: если система а, . . ., а„ каких-то множеств обладает свойствами а), б), то она лг-универсальна.

Свойство б) и послужило первоначальным поводом к введению названия «т-универсалъные» системы.

Пусть п - заданное положительное натуральное число. Обозначим через А совокупность каких-то вспомогательных фиксированных объектов «о, «1, . . ., cin- С каждой /1-кой а, . . ., ая попарно не нересекающихся и в сумме не исчерпывающих натурального ряда множеств свяжем теперь следующую нумерацию ф совокупности А:

а;, если а; б а,- (i = 1, .. ., п),

ао, если ,г ai U • • - U

Нумерацию ф п систему множеств а,. . ., а„ мы далее буде.м называть ассоциированными.

Сопоставляя определения сводимости нумераций (п. 9.2) и 1>г-сводимости ге-ок множеств, видим, что нумерация ф совокупности А тогда и только тогда сводима к нумерации ф той же совокупности, когда система мно-

жесте, ассоциированная с первой нумерацией, ш-сводима к системе множеств, ассоциированной с нумерацией ф.

Системы множеств (а, . . ., а„> и (у, . . ., р„> называются т-эквивалентными, если каждая из них «гсводима к другой. Из только что сделанного замечания о связи между т-сводимостью систем и сводимостью ассоциированных нумераций вытекает, что нумерации ф, ф cobokjtiho-сти А эквивалентны тогда и только тогда, когда jw-экви-валентны ассоциированные с ними системы множеств.

Нижеследующая теорема делает явным тесное родство между понятиями полноты нумерации и ш-универ-сальности системы множеств.

Теорема 1. Если ф - полная нумерация совокупности А, состоящей из п -\- 1 объекта, и множество Ф~аг номеров каждого неособого объекта (i = 1, . . ., ге) из А рекурсивно перечислимо, то ассоциированная система множеств ф~al, . . ., ф~а„ т-универсалъна.

Обратно, если система множеств а, . . ., апШ-универ-салъна,~то ассоциированная нумерация ф полна и совокупность номеров каждого неособого элемента этой нумерации является рекурсивно перечислимой.

Докажем первое утверждение. По условию множества Ф~а„ рекурсивно перечислимы и попарно не пересекаются. Пусть р, . . ., Рп - какая-либо другая система непересекающихся рекурсивно перечислимых множеств. Вводим вспомогательную частичную функцию

Е(х) \ " " (i = 1, .. м п),

{не определена для остальных х,

где Су, . . ., Сп - какие-то фиксированные числа из множеств ф~aj, . ф~an Согласной. 6.3 функция Е{х) частично рекурсивна. Поскольку нумерация ф полна, то найдется общерекурсивная функция / {х) такая, что

Г фСг = «п если а: б Pi,

-1 о = «о, если а; Pi и • • и Рп,

Ф 1,. .

то есть

X б р,- / (ж) б ф-а,- (г = 1, . . ., ге).

Значит, система Bj, . . ., р„ «г-сводится к системе {ф~«г} и система (р~ау,. . ., i~a„ нг-универсальна.

Докажем обратное. Пусть F {х) - произвольная частично рекурсивная функция. По условию, система мно-

жеств (%),. . ., F~ (а„) m-сводится некоторой рекурсивной функцией / [х) к системе а, . . ., а„, то есть

i?" (а;) б «г / {х) б «г (J = 1,. . ., ге).

Сравнивая это с формулами (2), определяющими ассоциированную нумерацию, видим, что .

ф/ {х), если а; б «1 (i = 1, . . ., ?г),

«о, если хау [J . . . U а„.

ф/ {х) =

и, следовательно, нумерация ф полна.

Теорема 2. Если в какой-нибудь совокупности U с полной нумерацией ф имеется конечная система Uy, . . . . . ., Un попарно не пересекающихся вполне перечислимых семейств объектов, то система множеств ТТ у, . . . . . ., ф~C„ является т-универсальной.

В самом деле, обозначим через % разбиение совокупности Una классы Uj, ..., 17„икласс17о = г7 - {Uy\J. . .\JUn) (см. п. 9.1). Факторнумерация фо = фД является полной нумерацией конечной совокзшности А = {Vо, Uy, . . . . . ., Un}, причем coBOKjTiHocTH номеров всех неособых элементов здесь рекурсивно перечислимы (так как они совпадают с множествами ф~?7{, i = 1 . . ., ге). Согласно теореме 1 отсюда вытекает, что система множеств (р~Щу,. . ., ф~?7„ ш-универсальна.

Теорема 2 дает возможность весьма просто находить конкретные ?п-универсальные системы множеств. Рассмотрим, например, нумерацию Клини к. Пусть Ui - семейство всех одноместных частично рекурсивных функций / (х), которые удовлетворяют условию / (0) = i. Семейства 17 вполне перечислимы и попарно не пересекаются. Обозначая через совокзшность всех клиниевских номеров функций из 17г, видим, что согласно теореме 2 система множеств ау, . . ., оСп является ш-универсальной для каждого значения ге = 1, 2,. . .

Системы множеств а, . . ., сСп и р, . . ., P„ называются рекурсивно изоморфными, если одна из них переводится в другую П0ДХ0ДЯПЦ1М рекурсивным взаимно однозначным отображением натурального ряда на себя, т. е. если одна из систем т-сводится к другой при помощи подходящей рекурсивной Фзгнкции, осуществляющей взаимно однозначное отображение натурального ряда на себя.

Теорема 3. Для каждого п;все т-универсальные п-ки множеств изоморфны друг другу (Мучник [2], С м а л ь я и [1]).

Действительно, из определения т-универсальности непосредственно следует, что все ш-универсальные ге-ки множеств ш-эквивалентны друг другу. Из ч»г-эквивалент-ности систем мнои-;еств следует эквивалентность ассоци- : ированных нумераций. Так как эти нумерации в рассмат- риваемом случае полны (теорема 1), то они будут и изо- морфньгаш (теорема 5, и. 9.3). Но тогда изоморфными будут и соответствующие ге-ки множеств.

10.2. Креативные системы множеств. Понятие креативности, определенное вн. 8.2 для отдельно взятых числовых множеств, распространяется на пары, тройки и т. д. множеств следующим образом.

Система ге числовых множеств . . ., а„ называется креативной п-кой множеств, если эти множества попарно не пересекаются, рекурсивно перечислимы и если существует такая рекурсивная функция р (х,. . ., Хп), что для каждой системы я,. . ., л. нонарно не пересекающихся рекурсивно иеречислимых множеств, удовлетворяющих условиям донолнительности [] = 0, , П П = 0) имеет место соотношение

р {хх, . . ., ж„) ф («1 и и • • • и («п и J. (1)

При ге = 1 это определение обращается в определение креативности множества а, введенное в п. 8.2. Теорема о совпадении классов креативных и ш-универсальных множеств также переносится на ш-универсальные п креативные ге-ки множеств. Однако, чтобы получить несколько более сильные результаты, мы разобьем теорему о совпадении классов креативных и универсальных 7г-ок на две части.

Теорема 1. Для каждой универсальной п-ки множеств существует такая рекурсивная функция g [х-х, . . ., Хп), что

g {Xl,. .., Хп) G и (л-ч П ai) и .П (stl-i П «О (2)

для всех х, . . ., Хп.

Если jtj;. П «г = 0 (i = 1, • п), то условие (2) переходит в условие креативности (1). Поэтому пз теоремы 1 следует, что все универсальные п-ки множеств являются креативными.

Для доказательства теоремы 1 выберем в каждом множестве «г какое-нибудь число с; (г = 1: . . ., ге). Рассмот-

§ 10. УНИВЕРСАЛЬНЫЕ СИСТЕМЫ МНОЖЕСТВ

рпм совместное продолжение / (xi, . . ., Хп, х) постоянных функций fi{x) = Ci{i = i, . . ., ге), определенное в тео-ре.ме о совместном продолжении (п. 7.3) и обладающее следующими свойствами:

а) функция / [хх, . . ., Хп, х) частично рекурсивна но совокупности всех своих аргументов;

б) для каждых фиксированных х, . . ., Хп область определения одноместной функции f {х, . . ., Хп, х) есть

я.., и • и

в) / {хх, . . ., Хп, х) может принплшть лишь значения

/ {Хх, . . ., Хп, Х) = Ci = X Ях (i = 1, . •, п).

Рассмотрим теперь нумерацию ф вспомогательной совокупности А ~ (Стд, «1,.... an}, ассоциированную с системой а, . . ., а„. Так как система а, . . ., а„ универсальна, то нумерация ф полна, и, следовательно, найдется рекурсивная функция g {хх, х, . . ., Хп) (п. 9.3, теорема 4), удовлетворяющая условию

фГ {Хх, . . ., Хп)= (pf {Хх, . . ., Хп, g {хх, . . ., Хп)), (3) если f {х, . . ., Хп, g) определено, т. е. еслп g {хх, . . ., а;„) 6 зТд;, и • • и

И условию

Ф {хх, . . ., Хп) = а„, (4)

если g [хх, . . ., Xn)Яx,\ . . . и Ях.

В случае (3) из свойства в) следует, что при подходящем /, 1 < / < п, имеем / {х-, . . ., Хп, g) = cj ш g {х, . . . . . ., Хп) в Равенство (3) дает ф = фc, откуда gaj ш потому g б Ях П aj-

В случае (4) ф = а, т. е. (? «1 U • • • U и потому gU (Ях. и <x,t), gen (л-. П «О-

Итак, в случаях (3) и (4) имеет место включение (2), т. е. включение (2) имеетsiecTO при любых х, . . ., Хп, что

ц требовалось.

Систему рекурспвно перечпслп.мых попарно не пересекающихся множеств а,1 условимся называть слабо креативной, еслп ciT4ecTByeT рекурсивная функция g {хх, . . .,Хп), обладающая следуюпщм свойством: еслп для некоторых Хх, . . ., Хп все множества Ях„ . . ., Ях пусты за пск.лючением, быть может, одного Ях. п это л,\-. состоит