Следствие 2. Каждое т-универсалъное множество креативно.

Действительно, к «г-универсальному множеству ш-сво-димо любое рекурсивно перечислимое множество, в том числе и креативное множество б, построенное выше. Ввиду следствия 1 отсюда вытекает креативность т-универ-сального множества.

Более тонко доказывается обраш;ение следствия 2:

Теорема 3 (М а й х и л [2]). Каждое креативное множество т-универ сально.

Пусть а - заданное креативное мнол<ество и / (а;) - продуктивная функция для а. Надо показать, что произвольное рекурсивно перечислимое множество [3 ««.-сводится к а. Рассмотрим трехместный предикат

Р {х,у,£)Фу &x=f {z).

Этот предикат, очевидно, рекурсивно перечислил!. Поэтому согласно теореме о неподвилшой точке для предика-, тов (п. 7.3) найдется обш;ерекурсивная функция g (у) такая, что

ye&x = f{g{y))xegyy (8)

Пусть у б Р. Тогда левая часть соотношения (8) ложна для каждого х и, следовательно, множество Лду пусто. Если же г/ б Р, то отношение х б равносильно равенству X = f (g (у)) н, следовательно, множество 3tg(i,) в этом случае состоит из единственного элемента / (g (у)): Докажем теперь, что функция / (g (х)) ш-сводит р к а. В самом деле,

/г б Р =Ф Я£(„) = 0 = .тг,,(„) cza=f{g (п)) б а. (9)

С другой стороны, согласно сказанному

я б Р =Ф лоо = {/ (g (и))}. (10)

Если бы при этом оказалось, что / {g (п)) б а, то мы имели бы

g(n) с= С =Ф / (g (/г)) б а - .-tg(„,, что противоречпво. Итак, / {g (н)) б а. Вместе с (9) это приводпт к требуемому соотношению

f{g («)) б а.

Теорема 3 доказана. Следствие 2 и теорема 3 показывают, что класс т-универсальных .множеств в точности сов падает с классом креативных .множеств.

§ 8. сводимость и Креативность множеств

В частности, отсюда вытекает, например, что множество 5 тех чисел х, для которых х б л, не только креативно, что было установлено выше путем непосредственных усмотрений, но и т-универсально, что прямо установить гораздо сложнее.

8.3. Простые множества. Как уже говорилось, при П0М01ЦИ понятия т-сводимости легко доказывается нере-курсивность большого числа мнолеств. Для этого берется какое-нибудь вспомогательное нерекурсивное множество Р и доказывается, что оно т-сводимо к исследуемому множеству а. Тогда а также будет нерекурсивным. Однако этот метод имеет следуюш;ий недостаток: если в качестве вспомогательного множества Р мы берем креативное множество, а исследуемое множество а рекурсивно перечислимо, то р будет ш-сводиться к а только в случае креативности а. Таким образом, если известный нам запас нерекурсивных множеств состоит лишь из креативных множеств, то при помогци метода ?п-сведения мы сможем пополнить этот запас только креативными же множествами. В частности, все нерекурсивные рекурсивно неречислимые множества, построенные нами до сих пор, креативны. Естественно возникает вопрос осуш;ествовании рекурсивно перечислимых множеств, которые не были бы креативными, но были бы нерекурсивными. Этим требованиям заведомо удовлетворяют так называемые простые множества, интересные и с других точек зрения.

Числовое множество а называется иммунным, если оно бесконечно и в то же время не содержит никаких бесконечных рекурсивно перечислимых подмножеств. Таким образом, иммунное множество не может быть ни рекурсивно перечислимым, ни продуктивным.

Числовое множество а называется простым, если оно само рекурсивно иеречислидю, а дополнение его иммунно. Отсюда сразу видно, что простое мнонество заведомо не рекурсивно и не креативно.

Понятия креативного и простого множества были введены Э. Постом. Ему же принадлежит и следуюш;ий пример простого множества.

Рассмотрим обш;ерекурспвную функцию D [п, х), jhu-версальную для одноместных примитивно рекурсивных функций. Эта функция была построена в п. 5.2. Обозначим через.б„ совокупность всех значений функцип Z) [п, х) при а; = О, 1, 2, . . . Множества б,г рекурсивно иере-чпслимы п каждое непустое рекурсивно иеречислимое

множество совпадает с некоторым бп- Положим / [х) = г {D {х, l{t)) = г (t) &г {t) > 2х)) = = r{iit{\D {X, I (t)) - г it) I + {{2х + i)r (t)) = 0)).

Таким образом, если значение / (х) определено, то это есть ЧИСЛО из ба, большее 2х. При этом, если в б; есть числа, большие 2х, ТО / (х) заведомо определено.

Р1з выражения (1) видно, что функция / (х) частично рекурсивна. Совокупность а всех значений, принимаемых функцией / (х), есть рекурсивно перечислимое множество. Мы хотим показать, что множество о просто.

Докажем сначала, что в его дополнении о не содержится ни одного бесконечного рекурсивно перечислимого множества. В самом деле, если некоторое j6„ бесконечно, то / (?г) определено и / (и) б бп, / (п) 6 а, откуда б„ С£ о.

Остается доказать, что множество а бесконечно. Для этого спросим себя, сколько чисел отрезка {О, 1, . . 2п} содержит множество о? Ясно, что число это не больше числа решений неравенства / (х) 2п. Но из этого неравенства вытекает х <. п. Поэтому на отрезке О, 1, . . ., 2?г лежит не более п чисел множества а и, стало быть, не менее п -\г i чисел лежит в о. Поскольку п произвольно, то о бесконечно и, следовательно, 0 просто.

8.4. Максимальные множества. Согласно определению дополнение простого множества хотя и бесконечно, но настолько «тесно», что не вмещает ни одного бесконечного рекурсивно перечислимого множества. Усиливая это свойство тесноты (названное в п. 8.3 иммунностью), приходим к следующему понятию сжатых множеств. Множество U называется сжатым, если

1) и бесконечно и

2) ни для какого рекурсивно перечислимого множества D пересечения 1> Г, и и Ь Г\и не могут быть одновременно бесконечными.

Условимся говорить, что множества А, В почти совпадают, если они отличаются друг от друга лишь конечным числом элементов, т. е. если ишожества

А-{АГ\ В), В-{АГ\В)

конечны. Тогда свойство 2) будет означать, что пересечение U с любым рекурсивно перечислимым }1шожеством либо конечно, либо почти совпадает с U.

Множество М называется .иакси.иа.1ьны.п, если оно салю рекурсивно перечисли.мо, а его дополнение сжато.

Пз этого определения непосредственно видно, что рекурсивно перечислимое .множество М, имеющее бесконечное допо.гнение, .мак-сима.гьно тогда и только тогда, когда каждое содержащее М рекурсивно перечис.гшюе множество либо почти совпадает с Л, либо почти совпадает со все.м натура.гъны.ч рядо.и.

Исии. ЧТО каждое максимальиое множество просто. Обратное „еверио: можио построить простые множества, не являющиеся макспмальныйш (см. задачу 19 в конце этого параграфа). Поэтому вопрос о существовании максимальных множеств имеет существенное значение для теории рекурсивно перечислимых ьшожеств.

Теорема 1 (Фридберг [1]). Максимальные рекурсивно перечислимые множества существуют.

Укажем эффективный процесс построения по шагам неубывающей цепочки конечных множеств

0 = М-1С М» С лг1 С . .. С М С . . .,

объединение которых М и окажется максимальным множеством. Введем ряд нужных понятий. Положим £)/ = {D (i, 0), . . . . ., D {i, t)}, где D (i, re) - универсальная рекурсивная функция длякласса одноместных примитивно рекурсивных функций. Очевидно, Х)? С 1> С . . . С Х>? С . . . и X>i = UDf является не-

иустым рекурсивно перечислимым множеством и всякое непустое рекурсивно перечислимое множество совпадает с некоторым I>j. Заметим, что согласно п. 5.1 1>о= -Dq = {0},

Далее, определим п-штат числа х на шаге t как конечную последовательность аа . . . а„ нулей и единиц такую, что

1, если xD и ii, О, если X фВ\ жлж i t.

где О < i < re.

Заметим, что для всякого ге>0 имеется всего 2 различных ?г-штатов. Упорядочим их, считая ге-штат аа-.. .Лп меньше ге-шта-та PoPi • • • Pni если существует i < ге такое, что при всех / < i имеем а,- = Pj, но at = О, а Pi = 1.

Отметим два очевидных свойства ге-штатов и их упорядочения:

(а) при фиксированных ге и г при < re-штат числа х на шаге «2 не меньше ге-штата числа х на шаге ti,

(б) если прп фиксированном шаге t, фиксированных х, у, т < п т-штат числа х больше т-штата числа у, то и ге-штат числа .г будет больше ге-штата числа у.

Наконец, нам потребуется список а, а, . всех натуральных

чпсел, т. е. а; = г, а также набор маркеров х , г > 0.

Перед шагом О каждый маркер

сопоставим числу г, jU" =0.

Описание процесса. Шаг t. К шагу t построено множество iU" и маркеры ге , ге = О, 1, . . ., сопоставлены соответственно числам af> в последовательности а,,, а, . . . На шаге t вычисляем элементы множеств ь\ для i < t. Далее ищем наименьшее m < г, а для него наименьшее ге, т <.n< t, такие, что на шаге t

Если таких чисел

нет, то все маркеры оставляем на прежних местах, т. е. а- - а-Ц, полагаем M = Ji~ и переходим к шагу «4-1.

в противном случае совершаем операции: 1) каждый маркер для т сопоставляем числу а\%п-т - полагаем а/"

2) все числа а для m < /с < ге освобождаем от маркеров и добавляем к т. е. 31 = 31 [j {aJ) m < А; < re};

3) переходим к следующему шагу t -\- i.

Эффективность процесса обеспечивает нам (в силу тезиса Чёрча) рекурсивную перечислимость множества 31 = \J 3lK Но построению состоит из чисел, потерявших маркеры, напротив, 31 - из чисел с маркерами (т. е. маркированных чисел).

Остается показать, что множество 31 обладает свойствами 1) и 2) из определения сжатого множества. . Лемма 1. Множество 31 бесконечно.

Достаточно показать, что положение каждого маркера

ста-

билизируется при растущем t. Так как D„ = = {0}, то маркер ни при каком t сдвигаться не будет. После того как положения

стабилизировались, маркер

маркеров

мо?кет перемещаться лишь к числам со все большими т-штатат.

Но т-штатов только конечное число. Поэтому положение т при

достаточно больших t также стабилизируется. Итак, маркированных чисел бесконечное множество и М бесконечно.

Лемма 2. Для всякого рекурсивно перечислимого множества либо D П 31 , либо £) П 31 конечно.

Если Х> = 0, то £) П -М" = 0. Если Оф 0,то D = D„ для некоторого п. Фиксируем ге.

Говорим, что число X останавливается в ге-штате а, если, начиная с некоторого шага t, ге-штат числа х есть всегда. По свойству (а) каждое х 31 при растущем t останавливается в некотором ге-штате. Так как .М"бесконечно, то существует п-штат, в котором останавливается бесконечно много элементов пз 31. Докажем, что не может быть более одного ге-штата с таким свойством. Допустим противное. Пусть а - напменьший из таких ге-штатов и р (а < р) - другой ге-штат, в котором останавливается бесконечно много элементов из 31. Тогда существуют числа а, Ь, т, р такие, что ге < m < р и

а, b - окончательные положения маркеров тар

но, а останавливается в ге-штате а, b - в ге-штате рТха Muuiaxuiuu большом шаге t выяснится, что ;г-штат числа а меньше ге-штата числа Ь. Тогда по свойству (б) и гег-штат числа а меньше т-штата числа Ъ. Поэтому маркер т до.чжен на каком-то шаге ty сдвинуться, что противоречит выбору" а.

Итак, почтп все чпсла из 31 останавливаются в одном и том же ге-штате аау . . . а„. Теперь D„ П 31 илп D f] 31 конечно в зависимости от того, будет ли а„ = О илп а„ == 1.

Такпм образом, 31 - сжатое множество и 31 - максимальное множество.

соответственна достаточно

Дополнения, примеры и задачи

1. Еслп а - числовое множество, то через / (а) будем обозначать множество значений функции / (х) прп а; 6 а. Если общерекурсивная фрткция / (х) осуществляет одно-однозначное отображе-uiie натурального ряда на свою часть, то из креативности (продуктивности) а вытекает креативность (продуктивность) / (а).

2. Если из продуктивного множества вычесть какое-нибудь содергкащееея в нем рекурсивно перечислимое ьшожество, то останется снова продуктивное множество. Если к креативному множеству добавить не пересекающееся с ним рекурсивно перечислимое множество, то получится креативное множество.

3. Совокупность пестовских номеров одноэлементного множества продуктивна. Совокупность пестовских номеров всех рекурсивно перечисленных множеств, отличных от множества {0}, также продуктивна.

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

5. Каждое бесконечное рекурсивно перечислимое множество содержит продуктивное подмножество и креативное подмножество.

6. Если иммунное множество а jre-сводится к множеству р, то f) не всегда иммунно. Аналогичное верно и для простых множеств.

7. Каждое бесконечное рекурсивно перечислимое множество содержит иьшунное подмножество.

8. Рекурсивно перечислимое ьшожество называется мезоич-пым, если оно ни рекурсивно, ни креативно, ни просто. Доказать существование мезоичных множеств (Д е к к е р 1]).

9. Каждое нерекурсивное рекурсивно перечислимое множество есть cjTiiMa двух непересекающихся перекурсивных рекурсивно неречислимых множеств (Фридберг [1]).

10. Частичной продуктивной функцией для множества а называется частично рекурсивная функция р (п) такая, что зг„ С

; а =Ф р (п) определено и р (п) а - л„.

Если а и.меет частичную продуктивную функцию р (ге), то а имеет и общерекурсивную продуктивную функцию, т. е. а продуктивно. Действительно, пусть б - область определенпя р (п). Предпкат у Ь & (х = р {у) \J х л,,) рекурсивно перечпслпм. Но теореме о представлении (п. 7.3) найдется общерекурсивная фупкция / (у) такая, что у Ь & {х = р (у) \/ х G л,,) Н- х G f( y). Отсюда следует: 1) ге е S =Ф = .„U{p («)}; 2) ге 6 я(„) = 0; 3) ге б =Ф р (/ (ге)) определена. Такпм образом, области ппределенпя р (х) п р (/ (х)) в cymie дают N. Берем общерекурсивную функцию g (х), значения которой частью совпадают с р (х), частью с /) (/ (i))(cM. п. 7.3, теорема 3). Так как р и pf частично продуктивны для а, то g будет искомой продуктивной функцией для а.

И. Подмножество р продуктшпого множества а называется продуктивным центро.м. а, если р = {р {х) Яж «} ДЛЯ подходящей частичной продуктивной фнкцпи р {х) для а. Показать, что если р - продзгктпвный центр продуктивного лшожества а, то о. обладает и такпм продуктивным центром у, что у С S п 6 - Y пескопечно. Показать, что каждое продуктивное шoжecтвo имеет любое конечное число попарно но пересекающихся продуктивных центров.