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

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

img width=13 height=22 src="images/referats/3088/image154.png">Р(S), которое также будем обозначать через r. Ясно, что r сохраняет отношение порядка (точнее: abL*(S)r(a). Как и выше для .

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

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

Предложение 1. Если H*(S), то тогда, когда .□

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

[]= [].□

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

aL(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; если Ø, то пусть Ơ такова, что ; , и пусть . Из определения видно, что . Поэтому достаточно показать, что . Рассмотрим случай Ø и Ø (другие случаи проще). Пусть таковы, что и для ; и для . Определим функцию так:

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