Теорема 2. Пусть
– две нумерации множества . Если и , то .Пусть
и 1 – сводят и соответственно, т.е. = и = . Определим теперь функции следующим образом:Имеем
и .Положим
, . Заметим, что для любогоЛемма 1. Если
– конечное множество, то и – конечное множество, имеющее то же число элементов, и наоборот. В этом случаеПокажем сначала, что либо функция
, либо она является строго периодической, т.е. существует z > 0 такое, что . Предположим, что . Тогда существуют такие, что . Но , а . Так как , имеем .Итак, если
– конечное множество, содержащее n+ 1 элемент, то его элементы представляют собой значения функции от первых n +1 аргументов. ПустьТогда
. Имеемтак как
и . Эти элементы различны, аИтак, если
конечно, то конечно, и отображение осуществляется взаимно однозначное соответствие между и . Аналогично, отображение осуществляется взаимно однозначное соответствие между и . Если конечно, то и конечно. Но . Отсюда очевидно, что также конечно и , так что .Цилиндром нумерации ν: N → S называется нумерация с ( ν): N → S, определенная следующим образом:
Нумерация называется цилиндрической, если она изоморфна своему цилиндру.
Сформулируем ряд свойств введенных понятий.
1. Если
– две нумерации множества , – однозначная нумерация и , то . Если, кроме того, однозначна, то .Действительно, пусть f– функция, которая сводит
. Тогда и f принимает каждое натуральное число как значение, другими словами, . Функция и, очевидно, сводит . Если однозначны, то f – общерекурсивная перестановка натурального ряда.□С помощью приведенного рассуждения на самом деле доказывается и
Лемма 2. Пусть
– две нумерации множества . Если существует , сводящая , такая, что , то .□2. Если
– две нумерации множества , – однозначная нумерация, то из следует .