ГЛ. rV. НУМЕРОВАННЫЕ СОВОКУПНОСТИ

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

7. Если семейство рекурсивно перечислимых множеств состоит лишь из бесконечных множеств и содер?кит все бесконечные рекурсивные множества, то оно не вычислимо (см. Деккер и Май-хил [1], Мальцев [3]).

8. Совокупность всех нерекурсивных рекурсивно иеречислимых множеств невычислима (Деккер и Майхил [1]).

9. Семейство рекурсивно перечислимых множеств называется вполне перечислимым, если совокупность всех постовских номеров всех лшожеств этого семейства является рекурсивно перечислимой. Аналогично, семейство частично рекурсивных функций называется вполне перечислимым, если совокупиость всех клиниевских номеров всех функций этого семейства рекурсивно неречислима.

Показать, что семейство всех надмножеств множеств какой-нибудь Y-иеречислимой системы конечных множеств является вполне перечислимым. Аналогично, семейство всех частично рекурсивных расширений функций у-неречислимой системы конечно определенных функций является вполне перечислимым (Райе [1]).

10. Каждое вполне перечислимое семейство множеств (функций) плюет вид, указанный в предыдзтцей задаче (см. Райе [1], Деккер и Майхил [1], Мальцев [3]).

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

С каждым числовым множеством а связана следующая проблема вхождения: найти алгоритм, позволяющий для произвольного числа х узнать, входит х в а или нет. Множества, для которых такой алгоритм существует, были названы в п. 2.3 рекурсивными. Один из обычных методов доказательства рекурсивности некоторого множества а состоит в том, что проблему вхождения для а подходящим образом «сводят» к проблеме вхождения для некоторого другого множества р, рекурсивность которого уже установлена. Если окажется, что проблема вхождения для множества а «сводится» к проблеме вхождения для множества р и при этом известно, что множество а нерекурсивно, то множество р также будет нерекурсивным. Термин «сводится» можно понимать в разных смыслах. Наиболее простое ионятие сводимости было введено Постом [3]. Это понятие и является предметом изучения в данном параграфе. Попутно возникают и изучаются понятия продуктивности и креативносЙ! множеств, тесно связанные с нтиерацией Поста рекурсивно перечислимых множеств.

8.1 Сводшюсть п «г.-эквивалентеость ] множеств. Числовое множество а называется »п-сбо9га4ыл{ к числово-

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

му множеству Р (символическое обозначение а,пР), если существует такая общерекурсивная функция / (ж),, что

ба]44/(ж)б р (1)

для всех значений х. Функция / (х) называется функцией, )П-сводящей а к р *).

Функция f (х) - X ш-сводит каждое множество к самому себе. Далее, если функция / «г-сводит множество ее к множеству р, а функция g иг-сводит р к мноеству у, то функция g (/ [х)) w-сводит а к у. Поэтому отношение ул-сводимости рефлексивно и транзитивно.

Теорема 1. Каждое рекурсивное множество а т-сводится к любому непустому мноокеству р, имеющему непустое дополнение. Если какое-нибудь множество у т-сводится к рекурсивному или рекурсивно перечислимому множеству Ь, то у рекурсивно или соответственно рекурсивно перечислимо.

В самом деле, берем какие-нибудь числаа G Р .ФР-Функция / [х), равная а на а и Ь вне а, очевидно, рекурсивна. Она ш-сводит а к р и потому первое утверждение теоремы истинно.

Чтобы доказать второе утверждение, обозначим через Х [х) характеристическую и через Хо [х) частичную характеристическую функцию множества б. Пусть общерекзф-сивная функция g [х) ?и-сводит y к б. Тогда % (g [х)) - характеристическая, а iS ()) ~ частичная характеристическая функции множества у. Если б рекурсивно, то функция %{х), а вместе с нею и функция % [g (х)) обще-рекурсивны. Аналогично, если б рекурсивно перечислимо, то функция Хо (х) частично рекурсивна. Но в таком случае и функция Хо (S {х}) частично рекурсивна, что и требовалось.

Множество р называется т-универсальнъгм, если выполнены еледуюпще два условия: 1) Р рекурсивно перечислимо; 2) каждое рекурсивно перечислимое множество т-сводится к р.

Иногда говорят, что проблема вхождения для множества а легче пробледш: вхождения для множества р, если а «г-сводитсяк р. Тогда можно сказать, что ш-универсальные множества - это рекурсивно неречислимые множест-

*) ?/;-сводимость часто называется также многосводимостью. Наряду с .чшогосводимостью, в п. 9.2 будет введена еще особая о5»осводимость.

ва, имеющие самую трудную проблему вхождения среди рекурсивно перечислимых множеств. Название «универсальные» происходит от следующего свойства этих множеств. Пусть / [х) - какая-нибудь (частичная) функция, а - числовое множество. Символом /" (а) обозначают прообраз множества а при отображении х- f [х) натурального ряда в себя, т. е. (а) - совокупность всех значений х, для которых/ [х) б сс. Определение »г-универ-сальных множеств теперь можно сформулировать следующим образом: множество р называется ш-унтерсалъним, если оно рекурсивно перечислимо и если каждое рекурсивно перечислимое множество а молено представить в виде /-1 (5), где f (х) - подходящая общерекурсивная функция.

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

Нам известно, что нерекурсивные рекурсивно неречислимые множества существуют. Они ш-сводятся к ш-универсальным множествам. Значит, в силу теоремы 1 все т-универсальные множества нерекурсивны.

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

Теорема 2. Совокупность со канторовских номеров тех пар <а, &>, для которых разрешимо уравнение К [а, х) = Ь, т. е. для которых Ъ G я,, является т-универ--сальным множеством.

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

Поэтому функция f [х) = с [а, х) »?-сводит я; к множеству со. С другой стороны, пз частичной рекурсивности функции К (а, х) вытекает, что множество тех пар, для которых уравнение К (а, х) = Ъ имеет решение, рекурсивно перечислимо. Следовательно, рекурсивно неречис-.лимо и множество со как совокупность канторовских номеров пар рекурсивно перечис.лпмого множества.

Множества а, 5 называются т-эквивалентными, если каждое из них иг-сводпмо к другому.

Из сказанного выше непосредственно вытекают следующие простые свойства »г-эквпвалентностп:

а) Если множество а рекурсивно или рекурсивно пере-числшчо, то рекурсивно или соответственно рекурсивно иеречислимо и каждое множество, ш-эквивалвнтиое а.

б) Все непустые отличные от Ж рекурсивные множества т-эквивалентны друг другу.

в) Если мноэюество а т-универсально, то каэ/сдое множество, т-эквивалентное а, такэ/се т-универсально. Все т-универсальные множества т-эквивалентны друг другу.

Так как отношение ш-эквивалентности транзитивно II симметрично, то все числовые мнон<ества распадаются на непересекающиеся классы эквивалентных друг другу множеств. Отношение ш-сводимости частично упорядочивает эти классы. Если отбросить пустое множество и мнояество Ж, сами по себе образующие т-классы, то среди остальных ш-классов рекурсивно перечислимых множеств наименьшим в смысле отношения будет класс ре-

курсивных, а наибольшим - класс w-универсальных множеств.

8.2. Продуктивные и креативные множества. Числовое множество а называется продуктивным, если существует такая общерекурсивная функция / (х), что для каяэдого п

ЛпС: «==>/(тг) 6 а - я„. (1)

Функция / [х) называется продуктивной для а.

Из этого определения непосредственно видно, что никакое продуктивное множество не может быть рекурсивно перечислимым. В частности, каждое продуктивное множество ненременно бесконечно.

Действительно, если бы продуктивное множество а совпало с каким-либо рекурсивно перечислимым множеством я,;, то из (1) получилось бы противоречивое утверждение

/ (л) б сс - а.

Один из простейших примеров продуктивных множеств представляет множество Ь всех тех чпсел х, для которых X 6 х- Действительно, согласно определеншо

716я,,/г[$б =4.3t„б, 7гфб7гбя„я„2б

п потому

я„с:бп.я„&7гбб.

Таким образом, б - нродуктпвное множество с продуктивной функцией / [х] = X.

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

Искомое подмножество можно построить следующим путем. Пусть «о - какой-либо постовский номер пустого множества и пусть / (х) - продуктивная функция для б. Так как я;а, Q б, то число / (яо) содержится в б. Ищем номер а-х множества {/ (an)}. Из (1) следует, что число / (я) содержится в б и отлично от / (до). Ищем номер а множества (/ (яо), / (fli)}. Число / («з) будет содержаться в б и будет отлично от f{ao) и / {а). Продолжая этот процесс, получим бесконечную последовательность

/ Ы, f К),../ ы,

числа которой различны и содержатся в б. Чтобы это наводящее рассуждение обратить в строгое доказательство, нам надо точнее определить, какой именно номер ai+i множества {/ (яо), . . ., / (а?)} мы выбираем. Пусть

х + -у = К{е, х,у) = К (к х], у).

Поэтому, полагая [е, / {х)] = g (х), имеем

%W = {/ Ш- (3) .

В п. 7.3 была построена примитивно рекурсивная функ- i ция и (т, п), для которой

Свойства (4) и (3) показывают, что в качестве а„+х можно взять и (а„, g (an)). Таким образом,

а (0) = До, а (тг -Ь 1) = U (я (п), g (а (п)))

и, следовательно, / {а(п)) есть общерекурсивная функция от п. Совокупность (2) всех значений этой функции рекурсивно неречислима, бесконечна п содер/кится в б.

Теорема 2. Если продуктивное множество а т-сводится к множеству р, то [5 также продуктивно.

Обозначим через / {х) функцию, сводящую а к р, и через "(а;) - продуктивную функцию для а. По условию

.г G а / (х) б р л; б Г (Р), (5)

т. е, а = (Р) п, знччит,

Q Р = Г (я„) с а. (6) j

Мы хотим теперь найти постовский номер множества /"1 (л„). Это множество есть совокупность тех значений х, для которых / [х) 6 Лп. Вводим предикат Р (х, у):

Р {х, у) fix)e я,,.

Согласно теореме о иредставлении (п. 7.3) существует примптивно рекурсивная функция h {у), для которой

1{х)ЯухЯн(у). (7)

Таким образом, множество /" (л:„) есть Яцп)-

Итак, из (6) и продуктивности функции g [х) получаем

я;„ Q Р =Ф Jtft(n) a=¥g{h [п)) б а - япу С другой стороны, из (7) и (5) имеем

g (h (П)) $ Jt„(a) fgh (п) $ Jt„, g{h in))eafgh{n).

Следовательно,

я„Р=» г(7г)бР -я„.

Это показывает, что множество Р продуктивно с продуктивной функцией / (g (h (п))).

Рекурсивно иеречислимое множество а, дополнение которого а = /V - а продуктивно, называется креативным *) множеством.

Выше было показано, что совокупность б тех х, для которых X ф Пх, является продуктивной. Ее дополнение б состоит из тех х, для которых х б я, т. е. из всевозможных X, для которых разрешимо уравнение К (х, t) = X.

Так как левая часть этого уравнения частично рекурсивна, то множество б рекурсивно перечпслимо и, следовательно, креативно.

Из теоремы 2 неносредственно вытекает такое важное

Следствие 1. Если креативное множество а т-сводится к какому-нибудь рекурсивно перечислимо.чу .множеству Р, то .множество Р креативно.

В самом деле, пз а mP вытекает а <; ,„Р. Нп а продуктивно. Поэтому в силу теоремы 2 множество р также продуктивно, а множество р креативно.

*) Иногда его называют творческим множеством.