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

Множество всех нумераций множества S обозначим через H (S), а множество всех нумераций подмножества S (включая пустое) обозначим через H*(S). Определим отображение r множества H* (S) на Р(S) – множество всех подмножеств S – так: r( o)

Ø; r(ν ) ν( N) для ν o H*(S). Отметим, что для любого подмножества и H*(S) = .

Множество классов эквивалентных нумераций множества S (подмножеств S) обозначим через L (S) ( L*(S)). На этих множествах отношение сводимости индуцирует отношение частичного порядка, которое будем обозначать также

. Отображение r: H*(S) Р(S) индуцирует отображение L*(S) Р(S), которое также будем обозначать через r. Ясно, что r сохраняет отношение порядка (точнее: a b L*(S) r(a) . Как и выше для .

На множестве H*(S) определим операцию

прямой суммы нумераций.

Пусть

H*(S); если = o, то ; если = o, то ; пусть o o и , , тогда нумерация множества определяется так:

Предложение 1. Если

H*(S), то тогда, когда .□

Следствие. Частично упорядоченные множества L*(S) и L(S) являются верхними полурешетками, а для операции

точной верхней грани справедливо следующее соотношение: для H*(S)

[

] = [ ].□

Заметим, что L(S)

L*(S) является коидеалом, т.е. удовлетворяет условию

a

L(S) L*(S), a

Полезно заметить и то, что r( a

) = ( ) ) для любых a, b L*(S).

Предложение 2. Полурешетка L*(S) является дистрибутивной полурешеткой с нулем [ o].

Нужно доказать, что если

H*(S) и , то существуют такие H*(S), что и . Ясно, что если = o, то в качестве нужно также взять o. Пусть o и пусть f Ơ – функция, которая сводит к , т.е. = ) f. Определяем множества так: , . Множества рекурсивно перечислимы. Если Ø, то полагаем o; если Ø, то пусть Ơ такова, что ; , и пусть . Если = Ø, то полагаем o; если Ø, то пусть Ơ такова, что ; , и пусть . Из определения видно, что . Поэтому достаточно показать, что . Рассмотрим случай Ø и Ø (другие случаи проще). Пусть таковы, что и для ; и для . Определим функцию так: