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

Ясно, что - гомоморфизм полурешетки L() в полурешетку L(). Покажем, что - изоморфизм. Для этого достаточно проверить, что если height=22 src="images/referats/3088/image259.png">для (). Пусть и ()=. Из последнего следует, что . Так как L*() – дистрибутивная полурешетка, то существуют c и d такие, что , и =. Так как , то ) =; а так как , то ) =\. Следовательно, Ø, = o и =. Получаем противоречие. Итак, - изоморфизм. Пусть bL(), cL() и c; тогда существуют такие, что и . Так как , а , то \. Но и \. Следовательно, \и L(\). Но так как а – минимальный элемент L(\) и , то . Покажем теперь, что L(). Для этого достаточно показать, что . Включение уже показано; из того, что \, а , следует, что \\) = . Следовательно, = , L(). Из следует, что и L(). Таким образом, L()) – идеал L().□

Для того чтобы применять предложение 5 для решения вопроса о вложении L() в L(), нужно выяснить вопрос о существовании минимальных элементов в полурешетках L(S).

Предложение 6. Если S конечно, то L(S) имеет наименьший элемент и является дистрибутивной полурешеткой.

Пусть и . Определим нумерацию этого множества так: , если m < n, и , если . Пусть – произвольная нумерация S и – некоторые – номера элементов соответственно. Определяя функцию f так, что f(i)для i < n и f(i)для , получаем и f Ơ. Следовательно, и [] – наименьший элемент L(S).□

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