Смекни!
smekni.com

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

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

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

Пусть

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

Имеем

и
.

Положим

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

Лемма 1. Если

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

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

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

Итак, если

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

Тогда

. Имеем

так как

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

Итак, если

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

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

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

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

1. Если

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

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

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

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

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

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

2. Если

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