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

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

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

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

Действительно, функция удовлетворяет условиям леммы.

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

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

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

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

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

Наоборот, если – частичный порядок, то пусть – последовательность всех вполне перечислимых подмножеств (число их не более чем счетно); пусть , тогда без труда проверяется, что последовательность <> рекурсивно перечислимых множеств удовлетворяет определениям 1) и 2) отделимой нумерации.

Введем на топологию , задав ее базисом, состоящим из всех вполне перечислимых подмножеств (легко проверить, что пересечение двух вполне перечислимых подмножеств также вполне перечислимо).

Предложение 10. Топология является отделимой (т.е. (, ) – – пространство) тогда и только тогда, когда нумерация отделима.

Нумерованное множество = (, ) назовем отделимым, если выполнено одно из следующих трех эквивалентных условий:

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