лишь из одного числа, не входящего в соответствующее «ь то

[g {х„ . . х„) ф и к и ОС,). . . (5)

Отсюда видно, что условие слабой креативности (5) совпадает с условием креативности (1), по при более жестких ограничительных требованиях, налагаемых на числа Ху, . . ., Хп. Поэтому креативные системы заведомо слабо креативны. Из теоремы 1 и нижеследующей теоремы 2 будет видно, что справедливо и обратное.

Теорема 2. Каждая слабо креативная п-ка мног жеств ау, . . ., а„ является т-универсалъной.

Пусть g [ху, . . ., Хп) - рекурсивная функция, удовлетворяющая для системы ау, условию (5). Нам надо показать, что любая система р, . . ., р„ рекурсивно перечислимых попарно не пересекающихся множеств т-сводится подходящей рекурсивной функцией h (х) к системе ау, . . ., а„. Функция h (х) строится так.

Сначала вместо ге-местной продуктивной функции вводим одноместную следующим образом. Согласно и. 7.3 для каждого i существует одноместная рекурсивная функция gi (х) такая, что

К{Х, t) = ite Лд.х). (6)

Полагаем по определению

Р{х) = g (gy (х), . . gn (х)).

Из свойства (5) функции g и формул (6) вытекает, что р (х) удовлетворяет следующему условию. Пусть для некоторого X

E{x,t) = iT-¥teyi{i = i,.. ., п), (7)

причем либо все множества у у, . . ., y„ пусты, либо все пусты, кроме некоторого множества yi, состоящего лишь из одного числа, и а. Г] yi = 0. Тогда

Согласно теореме о совместно.д! продолжении (и. 7.3) существует частично рекурсивная функция К {а, у, z, t) от переменных у, z, t, удов.летворяющая условиям

Л при GPi, бя, (i = l,.. ., п),

не определена для остальных у, z, t.

К {а, у, Z, t)

По теореме Майхила о неподвижной точке найдется рекурсивная функция / {у), для которой

Р (la, г/, / Ш) = л:,(у).

Это означает просто, что для каждого у множество Щ{у) СОСТОИТ лишь из одного числа р {{а, у, f {у)]).

Покажем теперь, что функция h [у) = р {[а, у, f (г/)]) ш-сводит систему р, . . ., р„ к а, . . ., сс,г. Прежде всего,

I/ € Pi и • • • и Р. (г/) € и • • и «„. (10)

Действительно, согласно (9) из у Рх U • • • U Рп вытекает, что К {[а, y,f {у)], t) не определено ни для каких t. Поэтому мнон{ества Yi, . . ., Уп, определенные по формулам (7), пусты и согласно (8) р {[а, у, f {у)]) «1 IJ • • • ... и «п.

С другой стороны, из (9) получаем, что при i/ б Рг функция К {[а, у, f {у)], t) имеет определенное значение лишь ]щя1 = р {[a,y,f{y)])-K значение это равно i. Следовательно, все множества Уу, . . ., Vn, найденные в этом случае по формулам (7), пусты, кроме множества yi, состоящего из числа р {[а, у, / {у)]). Если бы это число не входило в сс,, то согласно (8) мы имели бы соотношение

Р{[а, I/,/(£/)])€ и («;• и Yi), j=i

что невозможно, так как р ([а, у, f {у)]) G Yj. Следовательно,

г/6 Рг (г/) е ссг (t = 1, . . ., тг) и, значит, функция h (у) действительно т-сводит систему Pi, . . ., Рп к системе ау, . . ., а.

10.3. Рекурсивно неотделимые множества. Говорят, что числовое множество у отделяет множество а от множества р, если aQY и YnP=0- Множество а называется рекурсивно отделимым от множества р, если существует рекурсивное множество у, отделяющее а от р.

Если рекурсивное множество у отделяет множество а от множества Р, то дополнение v множества у рекурсивно отделяет р от а. Поэтому отношение рекурсивной отделимости симметрично и вместо того, чтобы говорить, что множество а рекурсивно отделимо от множества Р, часто говорят, что множества аир рекурсивно отделимы.

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

Каждое рекурсивное множество отделяет рекурсивно самого себя от любого другого не пересекающегося с ним множества. Поэтому рекурспвно неотделимыми могут быть лишь нерекурсивные множества.

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

Рассмотрим частично рекурсивную функцию Е (х), построенную в п. 6.3, которая принимает лишь значения О, 1 и не может быть доопределена до общерекурспвной функции. Обозначим через а совокупность решений уравнения Е (х) == О ш через р совокупность решений уравнения Е (х) = 1. Оба эти множества рекурсивно неречислимы и не пересекаются. Докажем, что а не отделимо рекурспвно от р. Пусть, напротив, какое-то рекурсивное мнон№-ство Y отделяет а от р.Тогда характеристическая функция множества у была бы рекурсивным доопределением функции Е, что противоречит установленной ранее рекурсивной недоонределимости этой функции.

Из определения рекурсивной неотделимости неносредственно вытекают следующие свойства рекурсивно неотделимых мно/кеств:

а) никакое перекурсивное множество не может быть рекурсивно отделимым от своего дополнения;

б) если множества а, Р рекурсивно неотделимы и ос Q «1, р с: Pj, nPi = 0> "го множества а, Р также рекурсивно неотделимы.

Более тонкое свойство рекурсивной отделимости указывает

Теорема 2. Если непересекаюциеся множества а, р имеют рекурсивно перечислимые дополнения, то а и рекурсивно отделимы.

Согласно теореме о совместном продолжении (и. 7.3) существует частично рекурсивная функцпя / (х), опреде-.ченная на объединенпп множеств а и р, принимающая лпшь значения 1, 2 п удов.четворяющая требованиям

/ (х) = lxe а, f{x) = 2=xe Р.

По условию а П Р = 0 и, значит, а IJ Р совпадает со всем натуральным рядом. Поэтому функцпя / (х) всюду определена. Обозначим через «1 и р множества тех х, для которых / (ж) = 1 и соответственно f (х) = 2. Из рекурспвностп функцпп / (х) следует, что и р рекурсивны, Из (1) вытекает, что ccj Q а, р Q р, т. е. «с

с: ai, Р Рь Значит, аир отделяются рекурсивными непересекающимися множествами ai, Pi.

Теорема 3. Никакая ш-универсалъная пара множеств а, Р не может быть отделимой.

В самом деле, согласно п. 10.2 каждая универсальная пара креативна и noTOAiy для множеств а, р существует рекурсивная «продуктивная» функция g (х, у), значения которой подчинены условию: если я f] = 0 < П П л = Р П = 0. то

(.j/)€«UPU«U (2)

Если бы множества а, Р были отделимы, то для подходящих X, у множества л, Щ, были бы взаимно донол-иительны и удовлетворяли бы условиям а S л, Р Q с Яу, т. е. а П л;,/ = р П = 0- Но тогда соотношение (2) было бы невозможно, так как функция g (х, у) должна иметь определенное значение, а справа стоит мно-и;ество, совпадающее со всем натуральным рядом.

Наряду с понятием неотделимости множества часто-бывает полезным и понятие эффективной неотделимости, определяемое следующим образо.л!.

Непересекающиеся множества а, Р называются эффективно неотделимыми, если существует рекурсивная функция q (х, у) такая, что

Лх- П я„ = 0 & л„ Э а & я„ э р =

=Ф q [х, I/) л« и (3)

Повторяя приведенные выше рассуждения, легко убеждаемся, что каждая эффективно неотделимая пара множеств неотделима в обычном смысле. Более того, если в определении креативной пары множеств опустить требование, чтобы множества пары были рекурсивно нере-чпслплшхш, то условие (3) будет следствием условия (1) из п. 10.2, посредством которого определялось понятие креативности. Таким образом, каждая креативная пара множеств эффективно неотделима. Однако верна п более общая

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

То, что креативная пара эффективно неотделима, уже было установлено. Поэто.му пусть а, Р - эффективно неотделимая пара рекурспвно перечислпмых множеств. Мы хотнм показать, что в этом слаепараа, Р креативна.

Так как аир рекурсивно перечислидш, то существуют числа а, Ь, для которых при любом х

« и Яж = la., х}, Р и = Л[Ь, х-.

Пусть Л!:, П Я( = П а = Я( П Р = 0- Тогда = Э а, л:[(,, .s] э р и л:[а, (] Я[ь, s] = 0. Следовательно, из (3) имеем

д{[а, t],[b, s])CaU3t,UPUrt,.

Это показывает, что пара множеств а, р креативна и имеет в качестве продуктивной функции функцию

р (s, t) = q ([а, t], [b, s]).

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

С;л едствие 1. Пусть множества а, р, образующие креативную пару, отделены рекурсивно перечислимыми множествами а, р, т.е. а Q а, р Q р, ttj fj Pi = 0-Тогда множества а, Pi также образуют креативную пару.

В самом деле, если функция q {х, у) удовлетворяет для множеств а, Р требованиям (3), то эта же функция будет удовлетворять требованиям (3) для множеств а, р. Следовательно, множества а, р эффективно неотделимы, а значит, они образуют креативную пару.

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

1. Теория то-универсальных п-ок множеств без труда переносится и на бесконечные системы множеств (К л и в [1] Мальцев [3]).

Вводятся следующие определения: последовательность множеств Ко, «1, . . . называется т-сводящейся к последовательности Ро> Pi, . . ., если для подходящей рекурсивной функции / {х

x&aif{x)ei (i = 0, 1, ...).

Последовательности называются т-эквивалентными, еслп каждая из них ;?1-сводится к другой. Если Л (х) - рекурсивная функция, то последовательность множеств (яц, я, . . .> называется р. п. последовательностью. Р. п. последовательность, состоящая из попарно не пересекающихся лгножеств, называется серией. Серия называется ?н-универсальной, еслп к ней /к-сводптся любая серия. С каждой серией o:i, 02, . . ., состоящей пз непустых множеств не псчерпывающих в совокупностп натурального ряда, ассоциируем нумерацию ф совокупности натуральных чисел, полагая по оппепе-ленпю "

фп = f -фф п б а; (п, г = О, 1, . . .),

где Ко = -ZV - («1 и «2 и • • •)• Изложенные в данном параграфе методам легко доказываются следующие утверждения:

а) серия w-унпверсальна тогда и только тогда, когда ассоциированная нумерация полна; б) все тм-универсальные серии изоморфны друг другу; в) если в полной нумерации «р для некоторой рекурсивной функции h (х) множества (fh (х) непусты и составляют серию, то эта серия т-универсальна.

2. Пусть и - совокупность с нумерацией ф и выделенным элементом о, называемым особым. Ведущей функцией нумерации ф называется часигчная одноместная функция / (х), определенная на множестве {U - о) и удовлетворяющая следующему требованию: f{x) = f (у) ФФ. фг = ф!/ для всех X, у из области определения/ Нумерация ф тогда и только тогда ассоциирована с некоторой серией, когда для ф существует частично рекурсивная ведущая функция. В терминах ведушдх функций можно сформулировать понятие креативности серии и доказать соответствующие теоремы (см. К л и в [1]).

3. Пусть существует частично рекурсивная функция / (х, у) такая, что из я,; Э а & rtj, Э Р & я. П Яу = 0 следует, что / {х, у) определена и / (х, у) [J % (а, Р фиксированы). Тогда а, Р эффективно-неотделимы (Мучник [1]).

4. Для любых X, у дшожества я,; - я,, и Яу - отделимы рекурсивно перечислидшми \множествами.

5. Рекурсивно неречислимые множества а, Р называются (Мучник [1]) сильно неотделимыми, если выполнены следующие Тусловия: а) а П Р = 0; б) дополнение множества а U Р бесконечно; в) для любого рекурсивно перечислимого я,: пз а П П % = 0 следует, что я - Р конечно (или пусто) и из р П я = = 0 следует, что я - а конечно. Доказать, что сильно неотдели-™е множества не отделимы рекурсивными множествами, но не могут быть "эффективно неотделимыми. Построить пример сильно неотде-ЛИ1ШХ множеств.

6. Понятия рекурсивной неотделимости и эффективной неотделимости можно распространить и на пары пересекаюпщхся ишожеств (МучнпкС[1], Смальян [1]). Множества а, р (возможно, пересекающиеся) называются рекурсивно неотделимыми, еслп не существует рекурсивных множеств ai. Pi, удовлетворяющих требованиям: «1 3 а. Pi 2 Р, cci П Pi = а П Р- Аналогично множества а, Р называются эффективно неотделимыми, еслп существует ре-курспвнаяфункция / (х, у) такая, что для всех х, у

я2°"=!/Р*ж П n,j=aC\f(x,y)n[J я,,.

Пара множеств а, Р называется продуктивной, еслп существует рекурсивная функция р (х, у), удовлетворяющая требованиям

лС,а&лС&яГ\ Яу = 0р(х,у)(а[])-, (я U я).

Показать, что из ш-сводимости эффективно неотделимой пары а, р к паре у, б вытекает эффективная неотделимость пары у, б (пары могут пересекаться!). Далее, если ,а, Р - продуктивная пара, то а, р эффективно неотделимы. Если пара рекурсивно неречислимых множеств а, р эффективно неотделима, то пара а, Р продуктивна.