Мы хотим теперь построить вспомогательную функцию / (х) таким образом, чтобы / (?г) было значением у-терма: с номером п, если п является номером терма. С этой целью полагаем по определению / (0) = у (0) и далее

Fl if (ex (1, ?г + 1)),. . ., / (ex (mi, n + 1))), если ex(0, ?г4- 1)= 1,

F, if (ex (1, n + 1)),. . ., / (ex (m„ 7Z + 1))), если ex (0, re -- 1) - s, .i;(ex(l, ?г + 1)) для остальных п.

(1);

Здесь ех (i, re + 1) - показатель высшей степени числа J на которую делится ге + 1 (см. п. 3.2).

Согласно и. 3.1 указанное определение функции / {х) можно представить в следуюш;ей форме:

/ (0) = i; (0),

fin + i) = G in, / (ex (1, re + 1)), . . ., / (ex {t, n + 1))),

(2);

где t - max [т, . . ., mj и

G{n, xi,...,xt)v (ex (1, re + 1)) .sg Д I ex (0, n +. 1) - i + i

г=1 ;

+ S i (1, • • • , 2-„j.) sg 1 ex (0, n + 1) - i 1.1 Так как функции ex (i, n -f 1) удовлетворяют соотноше-]

ПИЯМ

ex (t, re + 1) < re,

TO равенства (2) представляют собой схему возвратной ре- курсии, описанную в п. 3.2. Исходные функцпп ех (i, п + + 1) и G (ге, 1, . . ., Xj) примитивно рекурсивны. Поэтому j и функция / {х) также примитивно рекурсивна.

Покажем, что / (ге) равно значению v-терма с ножром] ге, если п - вообще номер какого-то v-терма, и что / (ге)1 равно значению подходящего v-терма для любого ге.

Для ге = О, 1 это заведомо верно, так как пз (1) видно,; что / (0) = / (1) = V (0).

Пусть доказываемое утверждение истинно для каждого п, меньшего некоторого числа а + 1. Рассмотрим/ (а + 1). Могут представиться лишь следуюш;ие три случая.

а) Число а + 1 есть номер у-терма вида Ft (Лх, . . .

Согласно принятой нумерации термов имеем

где Й1, . находим

а + 1 = 2К • • • Рщ\ • , (imi - номера термов йу, . . ., йт- Из (1)

fia + i) = Fi if (аО, . . ., / (а™.)).

Так как Uj а, то по предположению / (яу) равно значению терма uj и, следовательно,

fia + i) = Fi (%, . . ., Лж).

Иначе говоря, в рассматриваемом случае / (а + 1) равно значению у-терма с номером а + 1.

б) Число а + 1 есть номер терма вида v (с) и потому а + 1 = 3 Из (1) находим

/ (а + 1) = г; (с),

т. е. снова получаем, что / (а + 1) равно значению v-терма с номерод! а + 1.

в) Число а + 1 не есть номер никакого у-терма. Пусть

ех (i, а + 1) = а, (i = О, 1, 2,. . .). По (1) получаем, что либо для некоторого i (1 f < s) / (а + 1) = Ft if (%), . . ., / (a„j)), (3)

либо же

/ (а + 1) = у iai). (4)

Так как Uj а, то / (а) равно значению какого-то у-терма aj (не обязательно с номером Uj). Но тогда в случае (3) / (а -г 1) равно значению у-терма Ft (di, . . . • • •, (tmj), а в случае (4) / (а -- 1) равно значению у-тер-

V (aJ.

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

значений функции / (?г). Так как эта функция примитивно рекурсивна, то множество F° рекурсивно перечислимо, что и требовалось.

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

Фиксируем некоторое п > 2. Через JV обозначим совокупность всех п-ок натуральных чисел. В п. 3.3 каждой ?г-ке натуральных чисел (ж, . . ., ж„> был поставлен в соответствие ее канторовский номер с (х, . . ., ж„), причем было показано, что это соответствие между Ж" и Ж взаимно однозначно. Ставя в соответствие каждому множеству А n-ov. чисел множество номеров ге-ок

из 4, мы распространяем канторовское соответствие между

и 2V" до взаимно однозначного канторовского соответствия между множествами чисел и множествами ?г-ок чисел. Отсюда возникает естественное

Определение. Множество А п-ок натуральных чисел называется примитивно рекурсивным, рекурсивным или рекурсивно перечислимым, если таковым является множество с{А) номеров всех п-ок из А.

Так как объединению и пересечению множеств ге-ок отвечают объединение и пересечение совокупностей номеров этих ?г-ок, то из теорем п. 4.1 и п. 4.2 непосредственно получаем

Следствие 1. Объединение и пересечение конечного числа рекурсивно перечислимых {рекурсивных, примитивно рекурсивных) множеств п-ок натуральных чисел являются рекурсивно перечислимыми {рекурсивными, примитивно рекурсивными) множествами.

Дополнение рекурсивного {примитивного рекурсивного) множества п-ок есть рекурсивное {при.читивно рекурсивное) множество.

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

Характеристической фзнкцией множества А п-ок натуральных чисел называется ?г-местная функция / {х, . . . . . ., Хп), равная 0.ля ?г-ок (ж, . . ., ж„>, входящих в А, и равная 1 для ?г-ок, не входящих в А. Если с {А) - множество номеров всех п-ок пз .4 и (ж) - характеристиче-

екая функция множества с {А), то из соотношений

g{x)-=f (С„1 (ж), . . ., Спп {Х)), g (с (Ж1, . . ., Хп)) = / {Хх, . . ., Хп)

(см. п. 3.3) и примитивной рекурсивности канторовских функций с, Cni следует, что множество п-ок тогда и только тогда рекурсивно {примитивно рекурсивно), когда частично рекурсивна {примитивно рекурсивна) его характеристическая функция.

Аналогичным образом доказывается и

Теорема 1. Если всюду определенная функция F {xi, . . ., ocj) частично рекурсивна {примитивно рекурсивна), то совокупность п-ок (ж, . . ., ж„)>, удовлетворяющих уравнению

F (жь . . ., ж„) = О, .

является рекурсивным {примитивно рекурсивным) множеством.

Если функция F {ху, . . ., Хп, Ух, • ., Ут) примитивно рекурсивна, то совокупность А тех п-ок <ai, . . ., а„)>, для которых уравнение

F {ах, . . ., an. Ух, . . ., Ут) = О (1)

имеет хотя бы одно решение (ух, • • Ут), является рекурсивно перечислимым множеством.

Первое утверждение очевидно (см. п. 4.1). Для доказательства второго утверждения вводим функцию

/ (а, y)=F (с„1 (я), . . .,Спп {а), Стх {у), . . ., Стт {у))-

Эта функция примитивно рекурсивна. Уравнение (1) разрешимо при заданных а„ тогда и только тогда, когда разрешимо относительно у уравнение

/ (й, У) = О, (2)

где а - номер ?г-кп <(ai, . . ., а„>. Но совокупность значений параметра а, для которых разрешидю уравнение (2), является рекурсивно перечислпмым множеством. Поэто-ly рекурсивно иеречислима и совокупность А.

Теорема 2. Для того чтобы непустая совокупность л-ок была рекурсивно перечислимой, необходимо и достаточно, чтобы она была совоку?1ностью всех п-ок вида

<fi {х), ...,и {х)У (л; = О, 1, . . .), (3)

(ж), . . ., /„ {х) - подход.чщ.ие примитивно рекурсивные функции.

в самом деле, если функции (х), ...,/„ (ж) ирш тивно рекурсивны, то совокупность номеров всех тг-вида (3) совпадает с совокупностью всех значений ирт тивно рекурсивной функции

f{x) = c iU (х), ...,/„ {X))

и потому совокупность ?г-ок вида (3) рекурсивно перечне лима.

Обратно, пусть с (А) - множество номеров /г-ок рек5 сивно перечислимой непустой совокупности. Согласно тео реме 1 из и. 4.2 с [А) есть совокупность значений некоторов примитивно рекурсивной функции / {х). Но в таком случ А состоит из ?г-ок вида

<С„1 (/ (X)), . . ., с„„ (/ (х))>,

что и требовалось.

Графиком функции F {х, . . х„) называется coBOKyi ность [п + 1)-ок вида (х, . . ., х, F (х, . . ., а;„)>, гд значение F (ж, . . ., ж„) должно быть определенным, сюда следует, что если функция F всюду определена, характеристической функцией ее графика будет функци

sg I а:„+1 - F (xi, . . ., х)]

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

Легко построить пример не всюду определенной фу1 ции, график которой примитивно рекурсивен. Более того возможно построить и всюду определенную не примит! но рекурсивную функцию, график которой примитивн рекурсивен. Это довольно тонкое построение будет выио! нено вн. 6.4, а сейчас мы докажем лишь следуюш;ее до вольно очевидное утверждение:

Теорема 3. Если график М всюду определенноъ функции F (ху, . . Xji) рекурсивно перечислим, то фут ция F общерекурсивна.

Согласно теореме 2 совокупность М состоит пз [п + 1) ок вида </i [t), . . .,fn {t), /„+1 (i)>, где U, . . ., /„+i - иод-1 ходяш;пе придштивно рекурсивные функции. Функция всюду определена. Поэтому для любых х, . . ., ; уравнение

I + • . . + \xn-fnit)\ = О

имеет хотя бы одно решение t, причем для каждого решения t этого уравнения имеем F {х, . . ., х„) = /„+i (t). Следовательно,

F [xi, . . > Хп) =

= Ul (1 1 - /l (О 1 + • • • + I n-fn it) I = 0))

П, значит, функция F [х, . . ., Xn) обш;ерекурсивна.

Б заключение мы хотим сформулировать для ?г-ок натуральных чисел ещ;е теорему о порожденных множест-вэ,х •

Согласно п. 1.2 /п-местной операцией (частичной) на множестве всех ге-ок называется отображение, которое последовательностям тг-ок <Ji, . . ., 5) ставит в соответствие определенные ?г-ки = F (Ji, . . .,?„)• Если

fi = <Xii, . . ., Xin) (i = i, . . ., m),

TO каждая координата yt п-кш = <i/i, . . ., г/„> будет функцией от координат ?г-ок f, . . ., тс:

Vi - fi {Хц, • • м Хщ, . . ., X

rail

, Хтп) (j = 1, . . ., П).

Обратно, задавая произвольно функции ft, мы сможем но ?г-кам . . ., 5 найти ?г-ку и тем самым восстановить операцию F. Если операция F частичная, то координатные функции fi также частичные и наоборот.

Помимо координатных функций ft с операцией F мы свяжем еще одну функцию /, которая будет называться представляющей функцией для F. Определяется она следующим образом.

Пзсть даны некоторые числа а, . . ., а- Берем ?г-ки ?1, • . ., номеров tti, . . ., Um, т. е. ?г-ки

?г = <«п1 (а;), • • с„„ (а,)),

п вычисляем номер а п-кп F (fi, . . ., Sm)- Далее по определению полагаед! / (%, . . ., а) = Обратно, если известна функция / (а, . . ., а), то очевидным путем восстанав.чпвается п операция F {Xi, . . ., 5то)/представляе-1ая функцией / {а, . . ., а„).

Определение. Операция F (fi, . . ., 5m). заданная на множестве Ж" всех п-ок натуральных чисел, называется частично рекурсивной, общерекурсивной или при-•штивно рекурсивной, если таковой является функция (1; . ., йщ), представляющая операцию F.