На самом деле любая функция f, сводящая
, будет из . Действительно, если = , то из следует = . Из однозначности нумерации следует, что .□3.
и , следовательно, и .Функция
и сводит .Функция r сводит
Следствие. Существуют эквивалентные, но не изоморфные нумерации.
Действительно, пусть
– некоторая однозначная нумерация . Тогда . Но всякая нумерация, изоморфная однозначной, должна быть однозначной. Нумерация , очевидно, неоднозначная. Имеем .□4. Если
– две нумерации множества , – цилиндрическая нумерация, то из следует .Действительно, пусть
сводит . Предположим еще, что есть цилиндр: . Определим так:тогда
1 – сводит . Если – цилиндр, то, рассматривая , имеем , как выше. Но , по определению цилиндрической нумерации, следовательно, .□Следствие. Если
– две цилиндрические нумерации , то из следует .□Лемма 3. Пусть
– некоторая нумерация множества . Если существует двуместная общерекурсивная функция h такая, что , то – цилиндрическая нумерация.По свойству 3
и . Пусть f сводит , т.е. . Определим функцию так:Тогда
1 – сводит . По теореме 2 имеем .□Следствие. Пусть
– произвольная нумерация множества , тогда цилиндр является цилиндрической нумерацией.Действительно, функция
удовлетворяет условиям леммы.На нумерованном множестве
= ( , ) введем две новые «структуры», используя следующее понятие: подмножество называется вполне перечислимым (точнее, – вполне перечислимым), если рекурсивно перечислимо. Бинарное отношение, на , которое назовем – предпорядком, определим так: длядля любого вполне перечислимого подмножества
.Легко проверить, исходя из определения, что отношение
рефлексивно и транзитивно, т.е. действительно является предпорядком. Заметим, что справедливо следующееПредложение 9. Предпорядок
является частичным порядком (т.е. ) тогда и только тогда, когда нумерация является отделимой.Действительно, в соответствии с определением отделимой нумерации существует такая последовательность <
> рекурсивно перечислимых множеств, что 1) для любого , если и , то ; 2) если , то для некоторого, либо и , либо и . Проверим, что множества , являются вполне перечислимыми подмножествами . Действительно, и, если , то существует такое, что . Но тогда и . Итак, рекурсивно перечислимо, а вполне перечислимо. Пусть и пусть , таковы, что , ; так как , то . По свойству 2) найдется такое, что либо и , либо и ; тогда либо , либо . Следовательно, либо , либо и – частичный порядок.