Смекни!
smekni.com

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

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

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

3.

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

Функция

и сводит
.

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

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

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

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

4. Если

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

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

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

тогда

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

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

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

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

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

По свойству 3

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

Тогда

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

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

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

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

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

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

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

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

.

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

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

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

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

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

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