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

На самом деле любая функция f, сводящая

, будет из . Действительно, если = , то из следует = . Из однозначности нумерации следует, что .□

3.

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

Функция

и сводит .

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

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

Действительно, пусть

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

4. Если

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

Действительно, пусть

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

тогда

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

Следствие. Если

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

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

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

По свойству 3

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

Тогда

1 – сводит . По теореме 2 имеем .□

Следствие. Пусть

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

Действительно, функция

удовлетворяет условиям леммы.

На нумерованном множестве

= ( , ) введем две новые «структуры», используя следующее понятие: подмножество называется вполне перечислимым (точнее, – вполне перечислимым), если рекурсивно перечислимо. Бинарное отношение, на , которое назовем – предпорядком, определим так: для

для любого вполне перечислимого подмножества

.

Легко проверить, исходя из определения, что отношение

рефлексивно и транзитивно, т.е. действительно является предпорядком. Заметим, что справедливо следующее

Предложение 9. Предпорядок

является частичным порядком (т.е. ) тогда и только тогда, когда нумерация является отделимой.

Действительно, в соответствии с определением отделимой нумерации существует такая последовательность <

> рекурсивно перечислимых множеств, что 1) для любого , если и , то ; 2) если , то для некоторого, либо и , либо и . Проверим, что множества , являются вполне перечислимыми подмножествами . Действительно, и, если , то существует такое, что . Но тогда и . Итак, рекурсивно перечислимо, а вполне перечислимо. Пусть и пусть , таковы, что , ; так как , то . По свойству 2) найдется такое, что либо и , либо и ; тогда либо , либо . Следовательно, либо , либо и – частичный порядок.