Теория нумераций (стр. 9 из 22)

Теорема 2. Пусть

– две нумерации множества . Если и , то .

Пусть

и 1 – сводят и соответственно, т.е. = и = . Определим теперь функции следующим образом:

Имеем

и .

Положим

, . Заметим, что для любого

Лемма 1. Если

– конечное множество, то и – конечное множество, имеющее то же число элементов, и наоборот. В этом случае

Покажем сначала, что либо функция

, либо она является строго периодической, т.е. существует z > 0 такое, что . Предположим, что . Тогда существуют такие, что . Но , а . Так как , имеем .

Итак, если

– конечное множество, содержащее n+ 1 элемент, то его элементы представляют собой значения функции от первых n +1 аргументов. Пусть

Тогда

. Имеем

так как

и . Эти элементы различны, а

Итак, если

конечно, то конечно, и отображение осуществляется взаимно однозначное соответствие между и . Аналогично, отображение осуществляется взаимно однозначное соответствие между и . Если конечно, то и конечно. Но . Отсюда очевидно, что также конечно и , так что .

Цилиндром нумерации ν: N → S называется нумерация с ( ν): N → S, определенная следующим образом:

Нумерация называется цилиндрической, если она изоморфна своему цилиндру.

Сформулируем ряд свойств введенных понятий.

1. Если

– две нумерации множества , – однозначная нумерация и , то . Если, кроме того, однозначна, то .

Действительно, пусть f– функция, которая сводит

. Тогда и f принимает каждое натуральное число как значение, другими словами, . Функция и, очевидно, сводит . Если однозначны, то f – общерекурсивная перестановка натурального ряда.□

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

Лемма 2. Пусть

– две нумерации множества . Если существует , сводящая , такая, что , то .□

2. Если

– две нумерации множества , – однозначная нумерация, то из следует .