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

Ясно, что

- гомоморфизм полурешетки L( ) в полурешетку L( ). Покажем, что - изоморфизм. Для этого достаточно проверить, что если для ( ). Пусть и ( )= . Из последнего следует, что . Так как L*( ) – дистрибутивная полурешетка, то существуют c и d такие, что , и = . Так как , то ) = ; а так как , то ) = \ . Следовательно, Ø, = o и = . Получаем противоречие. Итак, - изоморфизм. Пусть b L( ), c L( ) и 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).□

Следствие. Если S – конечное множество, содержащее, по крайней мере, два элемента, то полурешетка L( S) континуальна.□

Предложение 6 показывает, что «естественное» вложение L(

) в L( ) (для ) существует, когда &bsol; конечно.