Нуыерацпя -ф называется рекурсивно изоморфной нумерации Tj), если существует общерекурсивная функция / (а;), отображающая взаимно однозначно натуральный ряд N на себя и сводящая ф к ij).

Значение понятия изоморфизма нумераций можно пояснить следующим образом. Вводя нумерацию ф совокуи-ности ?7, мы, естественно, начинаем смотреть на номер х объекта фа; как на его координату в координатизации ф. Переход от нумерации ф к нумерации ij) означает, с этой точки зрения, переход от одной координатизации к другой. Какие же координатизации считать равноценными? С алгоритмической точки зрения наиболее «равноценными» следует считать изоморфные, так как в этом случае упомянутая выше функция / {х) дает алгоритм, позволяющий по совокупности всех номеров объекта в одной нумерации находить не один номер, а все номера того }ке объекта в другой нумерации.

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

Пусть семейство U состоит из всех натуральных чисел. Тождественное отображение 17 на 17 обозначим через ф. С другой стороны, пусть функция g [х) осуществляет взаимно однозначное отображение натурального ряда на себя, но не является рекурсивной. Формулой ijja; = g [х) вводим нумерацшо г)) той же совокупности U. Нумерации Ф и Tj) как нумерации одного и того же множества не изоморфны. Действительно, изоморфизм ф и ij) равносилен существованию общерекурсивной функции / {х), удовлетворяющей соотношению

фа; = (а;).

Из определения нумераций ф, ij) следует, что g (/ (х)) = х. Но это невозможно, так как g не рекурсивна, а / рекурсивна.

В то же время нумерованное множество (U, ф> изоморфно нумерованному множеству <?7, я];), так как заведомо выполняется соотношение фа; = фг/ фа; = ij)!/.

Рассмотрим еще однл нумерацию того же множества ?7, определенную формулами

X (0) = О, X + 1) = 9.

Это значит, что объект О имеет в нумерации i два но-.мера О и 1, а все остальные объекты имеют но одному номеру. Нумерации ф, % эквивалентны. Однако они не изоморфны, ибо соответствующие нумерационные классы у изоморфных нумераций имеют одинаковое количество чисел, тогда как все классы нумерации ф имеют но одному числу, а нумерация % имеет класс, состоящий из двух элементов.

Следующий способ образования из одного нумерованного множества другого часто оказывается полезным. Пусть задана совокупность объектов U, снабженная нумерацией ф. Определим на U какое-нибудь отношение эквивалентности р и рассмотрим систему 17/р всех классов р-эквивалентных друг другу объектов из U. Пусть ра - класс всех объектов из U, р-эквивалентных какому-либо объекту а. Вводим нумерацию фр системы 17/р, полагая для произвольного хЖ

фря; = рфз;. (2)

Из этой формулы непосредственно видно, что тождественная функция f (х) = X представляет гомоморфизм нумерованного множества (17, ф> на нумерованное множество <?7/р, фр>. Множество U/p называется фактормножеством от и но эквивалентности р, а нумерация фр я&зыв&ется факторнумерацией от ф по р. Из той же формулы (2) видно, что нумерационные классы чисел для фак-торнумерации фр являются объединениями соответствующих нумерационных классов для исходной нумерации ф.

Теорема! (о гомоморфизме). Пусть функция / (х) представляет гомоморфизм нумерованного множества (ТГ, (ру на нумерованное множество (V, ij)). Вводим на совокупности U эквивалентность р, называя объекты из U р-эквивалентными, еслиих гомоморфные образы в V совпадают, т. е. полагая

{щ)рШПх) =¥{у)- (3)

Тогда функция / (х) представляет изоморфизм фактормножества <и/р, фр> на <F, Tj)). В самом деле, из (3) следует

W {х)= М {у) = Ч>Р = Ч>РУ-

Обратная импликация также очевидна.

Образец гомоморфизма, представляемого функцией / {х) = X, дают нумерации Клини к и Поста я, так как

заведомо

ят = хп =4 ят = яп.

Упоминающееся в теореме 1 отношение р здесь означает: две функции р-эквивалентны, если совокупности значений этих функций равны.

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

Нумерации ф и ij) называются одноэквивалентными, если каждая из них односводима к другой.

Понятие односводимости представляет собой специализацию понятия сводимости. Поэтому из односводимости ф к \\) или одноэквивалентности ф и г)) вытекает соответственно сводимость или эквивалентность ф, я]). Обратное не всегда верно. Однако существуют простые условия, при которых верно и обратное. Для формулировки этих условий введем еще одно понятие.

Нумерацию ij) совокупности U назовем нумерацией с эффективно бесконечными классами, если существует двуместная общерекурсивная функция В (х, у), обладающая следующими свойствами:

а) (х, у) = \х;

б) уфг=В (х, у)фВ{х, Z).

Функция в (х, у) дает нам алгоритм, который по одному какому-нибудь номеру х объекта позволяет найти бесконечное число различных номеров В [х, 0), В [х, 1), . . . того же объекта.

Теорема 1. Если нумерация ф сводима к нумерации oj;, имеющей эффективно бесконечные классы, то ф односводима к

Пусть функция / {х) сводит ф к я!), и пусть функция В [х, у) обладает свойствами а), б) относительно нумерации г)). Функцшо g [х), односводящую ф к ij), можно постропть следующим образом.

Полагаем по определению g (0) = f (0) и далее, считая значения g (0), g (1), . . ., g (п) уже известными, полагаем h (п) = щ {В if (п + 1), t) (t {g (0), ...,g (n)}), (1) gin + i) = В if {n + 1), h in)). (2)

Из (1) следует, что g (п + i) {g (0), . . ., g (re)}, т. е. ЧТО функция g {х) принимает различные значения ири различных значениях аргумента, а из (2) и свойств функции В (х, у) имеем

"Pg (п) = / (п) = ц>п.

Остается проверить, что функция g общерекурсивна. С точки зрения теории алгоритмов это ясно, так как для вычисления значений функции g указан регулярный процесс. Однако для строгого доказательства этого факта надо показать, что функция g получается операторами подстановки, примитивной рекурсии и х-онератором из функций В, f ж других общерекурсивных функций. Необходимые вычисления не представляют собой трудности и мы пх здесь опустим (см. задачи 1, 2 к этому параграфу).

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

Теорема 1а. Пусть нумерация ф сводима к нумерации г)). Если при этом существует общерекурсивная функция Во (х, у), удовлетворяющая требованиям

а) фо {х, у) = фж;

б) у ф Z =Ф Во (х, у) ф Во {х, Z),

то нумерация ф односводима к нумерации ij).

Действительно, функцию g (х), односводящую ф к -ф, можно определить по тем же формулам (1), (2), заменив в них лишь подформулы В (f (п -i- i), t) ж В (f (п -\- i), li («)) соответственно выражениями 5о (п -\- 1, t) ж Во (п + + 1, Л (п)).

Ясно, что теорема 1 есть частный случай теоремы 1а: если функция В (х, у) для нумерации \\> известна и нумерация ф сводится функцией / (х) к нумерации ф, то функция

Во (х, y)=B{f [х), у)

обладает свойствами а), б) пз теоремы 1а.

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

Т е о р е м а 2 (об изоморфизме нумераций). Одно-квивалентные нумерации произвольной совокупности объектов изоморфны между собой.

Пусть ф, ij) -одноэквпвалентпые нумерации какой-нибудь совокупности объектов U. Обозначим через / [х) функцию, одно сводящую нумерацию ф к нумерации -ф, и через g (х) функцию, односводящую \р к ф. Нам надо указать алгоритм для вычисления значений новой функцип h (х), которая представляла бы изоморфизлс ф на if>. Для этого придется ввести несколько вспомогательных понятий и функций.

Финитным соответствием условимся называть каждую конечную последовательность

(хо, уо}, (ху,УхУ, . . ., (х, yjy (3)

нар натуральных чисел, удовлетворяющую условиям

Хг = xj 44 z/j = yj, = т)г/г (г, ; = О, 1, . . ., к). (4)

Номером финитного соответствия (3) назовем число

Pi ,

где ро = 2, = 3, . . . - последовательные простые числа, а [х, у] - номер пары (х, уУ, вычисляемый согласно и. 7.1.

С помощью заданных функций /, g мы хотим теперь. построить общерекурсивные функции S (т, п), Т (т, п), значения которых были бы равны номерам финитных соответствий

(хо, уоУ, (xi, УхУ, . . ., (х, уУ, (т, у+уУ (5)

и соответственно

<хо, УоУ, (ху, УхУ, . . ., (х, уу, (х+х, ту, (6)

где п - номер соответствия (3), m - произвольное число,, а Ук+1 - подходящие числа, зависящие от т, п. Соответствия (5) и (6) представляют собой расширения соответствия (3), которые вводят в игру произвольно заданное число т. Возможность таких расширений и доказывается посредством построений функций S {т, п)яТ (т, п).

Укажем сначала алгоритм для вычисления <S (m, п). Пусть заданы чпсло т и некоторое соответствие (3), номер - которого есть п. Нам надо указать, какое число иш выбираем в качестве уу. Этот выбор производится по-разному в каждод! из следующих трех возможных случаев.

а) Если т б {хо, . . ., Ху) и i - наименьшее число, для которого Xi = 7?г, ТО полагаем г/;г+] = г/;.

б) Если т {хо, . . .,хт;} и / [т) {г/о, . . ., уь), то полагаем = f (т).

в) Если т {хо, . . ., Xi-}, но / (??г) б {г/о, . уь}, то число у+у строим посредством следующего процесса. Берем наименьшее число iy, для которого / (?7г) = г/;„ и рассматриваем / (Xi,). Если / (а;;,) 6 {о, . . ., yi}, то берем наименьшее igi ДЛя которого / (.г,) = г/;,- и рассматриваем / (Xi,). Продолжая этот процесс, получим серию чисел г/,-,, г/;, . . . Мы хотим показать, что эта серия оборвется, т. е. что найдется число s, для которого / [xt) $ {г/о, . . ., у л).

Докажем, что числа г/, г/;,, . . . различны. Пусть для некоторого и числа у,, . . ., yi попарно различны и = y;,t-n- Если бы оказалось, что г/; = г/; (1 <

Zvu), то мы имели бы / (a;;J = / Так как функ-

ция / {х) при разных значениях аргумента принимает разные значения, то из последнего равенства следует Xi = = а;; и, значит, у - У1,, у вопреки иредиоложению.

Итак, все члены последовательности г/,-,, г/, . . . различны и все они содержатся в множестве {г/о, . . ., г/}. Поэтому последовательность будет иметь последний элемент г/j, и, таким образом,

/ (т) = у и, / (а;;,) = у и., . . ., / {Xi = у,

f {xt) € {Уо, ...,у,]. (7) По оиределению полагаем г/д. = / (Xi).

Пара (т, Ук+У построена. Надо показать, что последовательность (5) представляет собой финитное соответствие при условии, что финитным соответствием является последовательность (3). В случаях а) и б) это очевидно. В случае в) второе из требований (4) выполняется автоматически, так как ввиду цепочки равенств (7) последовательно получаем

rpni = !);(/ (т)) = ijjz/i, = фа;;, = ij)/ (х) = . . .

= tf {хО = Wi+i-Первое пз условий (4) в случае в) также выполнено, так как для i <: к + 1 имеем Xi Ф т, а из у- = у+у следовало бы соотношение / (х;) = г/; б {Уо, - Ук}, невозможное ввиду (7).

Меняя ролями /, Хо, . . ., х и g, уо, . ., Ук, анало-гпчиыд! путем по заданному соответствию (3) и числу т