Теория нумераций

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

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

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

1. Если mg width=46 height=22 src="images/referats/3088/image340.png">– две нумерации множества , – однозначная нумерация и , то . Если, кроме того, однозначна, то .

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

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

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

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

На самом деле любая функция f, сводящая , будет из . Действительно, если = , то из следует = . Из однозначности нумерации следует, что .□

3. и , следовательно, и .

Функция и сводит .

Функция r сводит

Следствие. Существуют эквивалентные, но не изоморфные нумерации.

Действительно, пусть – некоторая однозначная нумерация . Тогда . Но всякая нумерация, изоморфная однозначной, должна быть однозначной. Нумерация , очевидно, неоднозначная. Имеем .□

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

Действительно, пусть сводит . Предположим еще, что есть цилиндр: . Определим так:

тогда 1 – сводит . Если – цилиндр, то, рассматривая , имеем , как выше. Но , по определению цилиндрической нумерации, следовательно, .□

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

Лемма 3. Пусть – некоторая нумерация множества . Если существует двуместная общерекурсивная функция h такая, что , то – цилиндрическая нумерация.

По свойству 3 и . Пусть f сводит , т.е. . Определим функцию так:

 Скачать реферат