ные одноместные функции 1 и 0. Эти функции примитивно рекурсивны. Поэтому множества 0 и Ж также примитивно рекурсивны.

Характеристической функцией для конечного множества чисел {й!, . . ., а„} {ui <Z <. . . : <. а) служит примитивно рекурсивная функция

sg {\x - ai\-\x - ai\-. . .-Ix - aj).

Поэтому каждое конечное множество натуральных чисел примитивно рекурсивно.

В п. 3.2 показано, что характеристические функции свойств «быть четным числом», «быть простым числом», «быть точным квадратом» примитивно рекурсивны. Поэтому примитивно рекурсивными являются и множества всех четных чисел, всех простых чисел, всех точных квадратов. Аналогичным путем легко убедиться, что примитивно рекурсивными будут совокупность степеней а", а, а, ... произвольного числа а и многие другие часто встречаюгциеся совокупности чисел.

Теорема I. Дополнение рекурсивного {примитивно рекурсивного) множества, а также объединение и пересечение любой конечной системы рекурсивных (примитивно рекурсивных) множеств суть множества рекурсивные {примитивно рекурсивные).

Й В самом деле, пусть (ж), . . ., fni) - характеристические функции множеств А, . . ., An. Тогда функции

fix) =sgA (ж), g (х) = /i {х)- . . . fn {х), h {х) = sg (/i (ж) -Ь . . . -Ь /„ [х)) будут характеристическими соответственно для дополнения множества Ау, объединения и пересечения множеств Ах, . . ., An- Если fx {х), . fn {х) частично рекурсивны или соответственно примитивно рекурсивны, то такими же будут и функции f (х), g (х), h (х).

Теорема 2. Если всюду определенная функция f {х) частично рекурсивна {при.митивно рекурсивна), то множество А решений уравнения

f{x) = 0

рекурсивно {примитивно рекурсивно).

Действительно, характеристической функцией для множества А служит функция sg / {х), рекурсивная или примитивно рекурсивная вместе с функцией / {х).

Совокупность всех значений, принимаемых некоторой примитивно рекурсивной функцией, в общем случае не будет ни примитивно рекурсивным, ни даже рекурсивным множеством. Эти совокупности будут изучены ниже под именем рекурсивно неречислимых множеств. Однако существует ряд простых признаков для того, чтобы совокупность значений примитивно рекурсивной (рекурсивной) функции была примитивно рекурсивной (рекурсивной). Один из них указывает

Теорема 2. Если примитивно рекурсивная {обще-рекурсивная) функция / {х) удовлетворяет условию

f{x)-x {х = 0, 1, 2, . . .),

в частности, если f {х) монотонно возрастает, то совокупность М всех значений этой функции есть множество примитивно рекурсивное {рекурсивное).

В самом деле, из неравенства f (у) у следует, что функция

gix)Ilsg\f{y) - x\

является характеристической для М.

4.2. Рекурсивно перечислимые множества. Эти множества играют фундаментальную роль в теории рекурсивных функций. Существует несколько равносильных определений указанных множеств. В качестве исходного мы возьмем следующее определение.

Множество чисел А называется рекурсивно перечислимым, если существует двуместная примитивно рекурсивная функция f {а, х) такая, что уравнение f {а, х) = Q имеет решение х тогда и только тогда, когда а А.

Далее (п. 6.1) будет показано, что в этом определении па самом деле в качестве функции / {а, х) можно брать произвольную частично рекурсивную функцию. Однако утот результат будет получен нами лишь в результате длинной цепочки теорем. А пока мы, строго придерживаясь указанного определения, выведем из него ряд следствий.

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

Согласно определению характеристическая функция / {х) произвольного примитивно рекурсивного множества Л является примитивно рекурсивной. Но тогда примитив-

но рекурсивное уравнение

/ (а) + а; = О

имеет решение х тогда и только тогда, когда а А.

Следствие 2. Пусть F {а, xi,. . ., а;„) - прими--тивт рекурсивная функция от переменных а, Ху, . . ., а;„. Множество тех значений параметра а, для которых уравнение

F [а, хг, . . Хп) = 0 (1)

имеет хотя бы одно решение х, . . ., а;„, является рекурсивно перечислимым.

Действительно, введем примитивно рекурсивную функцию

f{a,x) = F (а, с„1 (ж), . . ., с„„ (ж)),

где (ж) - канторовские функции из и. 3.3. Так как

/ (а, с (Ж1, . . ., Хп)) = F {а, ж . . ., ж„),

то совокупность значений параметра а, для которых разрешимо уравнение / (а, ж) = О, совпадает с аналогичной совокупностью для уравнения (1) и потому эта последняя совокупность рекурсивно неречислима.

Теорема 1. Непустое множество А тогда и только тогда рекурсивно перечислимо, когда оно совпадает с совокупностью всех значений некоторой примитивно рекурсивной функции.

Пусть / (ж) - примитивно рекурсивная функция, А - множество всех ее значений. Левая часть уравнения

i / (ж) - а I = О

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

Обратно, пусть множество J. непусто и рекурсивно неречислимо. Согласно определению это значит, что А есть совокупность тех значений параметра а, при которых разрешимо уравнение вида F {а, х) = О, где F {а, ж) - подхо-дяш;ая примитивно рекурсивная функция. Рассхютрпм примитивно рекурсивную функцию

f{t) = l{t)sgF{l{t), r{t)) + b-ssFmt), г it)), (2)

где I (t), г (t) - канторовские функции из и. 3.3, а Ь- какое-нибудь число пз А. Покажем, что А совпадает с совокупностью всех значений функции / (it).

пли соответственно уравнение,

fl {а, Жх) -f . .. -f /„ (а, ж„) = О,

будет объединение илп соответственно пересечение множеств Ai. Так как левые части уравнений (4), (5) примитивно рекурсивны, то согласно следствию 2 объединение п пересечение множеств Ai рекурсивно неречислимы.

По аналогии со свойствами рекурсивных множеств можно было бы нредноложпть, что дополнение рекурсивно перечислпмого множества есть рекурсивно перечпслимое Множество. Однако это неверно. В и. 6.3 будут построены рекурсивно перечислпмые множества, дополнения которых пе являются рекурсивно перечпслимыми. Более того.

В самом деле, если ири некотором t

F (1 it), г it)) = О, (3)

то I (t) 6 А, а из (2) имеем

f{t) = l it) 6 А.

Если же (3) неверно, то из (2) получаем f{t) = b(:A.

Таким образом, все значения функции / (it) входят в А.

Пусть теперь а А и, значит, F {а, ж) = О для подходящего ж. Полагая t = с {а, ж) и принимая во внимание, что I (с (а, ж)) = а, из (2) получим / (it) = а. Следовательно, А совпадаетс совокупностью значений функции / (it) и теорема 1 доказана.

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

Теорема 2. Сумма и пересечение конечного числа рекурсивно перечислимых множеств являются рекурсивно перечислимыми множествами.

Пусть Ai - множество тех значений параметра а, для которых существует решение ж уравнения

fi {а, ж) = О (s = 1, . . ., п),

где /; - некоторая примитивно рекурспвиая функция. Тогда совокупностью значений параметра а, при которых относительно Xi, . . ., Хп разрешимо уравнение

fl {а, Xj)- ... •/„ [а, Хп) = 0 (4)

Эта функция примитивно ношения

/ (с {Xi,

Хп)) = Р {Хъ

совокупность значений функции / совпадает с совокупностью всех значений функции F и потому эта совокупность рекурсивно перечислима.

4.3. Порожденные множества. Напомним некоторые понятия пз п. 1.3. Пусть 31 - произвольное множество каких-то элементов. Каждая (частичная) функция F {xi, . . ., Жп), определенная на Ж, со значениями, принадлежащими тому же множеству 3/, называется (частичной) операцией на 31. Подмножество А 1шожества 31 называется замкнутым относительно частичной операции F, если для каждых значений х, . . ., Хп, взятых из области определения F и принадлежащих А, значение F {х, . . . . ., Хг) также принадлежит А.

Предположим, что в множестве 31, снабженном некоторой системой операций Fi, выделена какая-то совокупность V его элементов. Совокупность F, являющаяся пересечением всех подмножеств множества Ж, замкнутых относительно операций Fi и содержащих V, называется совокупностью порожденной системой V при помощи операций F- В п. 1.3 было показано, что состоит из тех и только тех элементов Ж, которые являются значениями термов, записываемых при помощи символов заданных операций Fi и символов элементов системы F.

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

Теорема 1. Множество натуральных чисел F, порожденное рекурсивно перечислимой совокупностью V с помощью конечной системы примитивно рекурсивных функций Fi {xi, . . Xmi) (i = 1, . . ., s), является рекурсивно перечислимым.

Обозначим через v {х) примитивно рекурсивную функцию, множество значений которой совпадает с F*). Согласно сказанному порожденное мнон<ество F состоит из значений термов а (ui, . . ., ап), записываемых с помощью функциональных знаков Fi и произвольных чисел а, . . . . . ., из F. Так как V состоит из значений функции v{x), то F -из значений термов вида а {v {bi), . . ., v {b)), где b-x, . . ., bjn- произвольные натуральные числа. Термы последнего вида условимся называть у-термами.

Все у-термы мы теперь перенумеруем. Номером тердга V (6) назовем число З. Далее нумеруем индуктивно, восходя от бо.чее коротких термов к более длинным. Пусть тер.Ащ di, . . ., уже получили номера Cj, . . ., Сщ. Тогда номером терма Fi (ui, . . ., Vi) будем называть

число . . . pi, где символы р, Pi, р, • обозначают последовательные простые числа 2, 3, 5, . . .

Самые короткие у-терлш:-это термы вида v {Ъ). Их номера, как сказано, равны степеням числа 3. Номера остальных 1;-термов четны. Таким образом, не каждое натуральное число есть номер какого-то терма, но если натуральное число есть нодгер какого-нибудь у-терма, то этот терм однозначно восстанавливается пзтем разложений чисел на простые лгножители.

*) Д.чя пустого V утвэр/кдеипе очевидно.

именно этот случай следует считать типичным, так как справедлива

Теорема 3 (Пост). Если какое-нибудь множество А рекурсивно перечислимо и его дополнение А также рекурсивно перечислимо, то множества А и А рекурсивны.

Пусть мнон<ества А к А яв.ля1отся совокупностями тех значепнй параметра а, для которых разрешимы уравнение / (а, х) = О и соответственно уравнение g [а, х) = О, где f,g~ примитивно рекурсивные функции. Так как для любого а одно из указанных уравнений заведомо разрешимо, то функция

h (а) = (/ (а, X) g (а, ж) = 0) (6)

всюду определена и, следовательно, обш;ерекурсивна. Поэтому функция

F {а) = sg / {а, h (а))

также общерекурсивна. Из формулы (6) видно, что F (а)- характеристическая функция для А, и потому А ш А рекурсивны.

В дополнение к теореме 1 докажем еще, что совокупность значений, принимаемых произвольной многоместной примитивно рекурсивной функцией F {xi, . . ., Хп), является рекурсивно перечислимым множеством.

Рассмотрим одноместную функцию

f{x) = F {Спг (х), . . ., Спп (х)). (7)

рекурсивна. В силу 7 и соот-