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

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

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

вует, когда \конечно.

В случае бесконечного S полурешетка L(S) не имеет наименьшего элемента, но имеет много минимальных. Для установления этого напомним следующее определение. Нумерация множества S называется однозначной, если νn ≠ νm для любых n ≠ m N.

Предложение 7. Если S – счетное множество, то существует точно континуум попарно не эквивалентных и даже попарно несравнимых однозначных нумераций множества S.

Пусть – группа всех перестановок множества N, - подгруппа общерекурсивных перестановок N. Хорошо известно, что счетна, а имеет мощность континуума, отсюда следует, что множество левых смежных классов также имеет мощность континуума. Пусть – некоторая фиксированная однозначная нумерация множества S. Тогда любая другая однозначная нумерация может быть однозначно представлена в виде , а класс нумераций, эквивалентных нумерации , состоит из всех нумераций вида , так что существует взаимно однозначное соответствие между классами эквивалентных однозначных нумераций множества S и смежными классами из . Так как неэквивалентные однозначные нумерации, очевидно, не сравнимы, то отсюда и следует заключение предложения.□

Следствие 1. Если S – счетное множество, L(S) имеет континуум минимальных нумераций.

Следствие 2. Если S – не более чем счетное множество, содержащее, по крайней мере, два элемента, L(S) имеет идеал, изоморфный полурешетке всех m – степеней собственных подмножеств N.

Это вытекает из предложения 5 и следствия 1.

Обратимся теперь к вопросу об изоморфизме полурешеток L(S), и L(), L*() для двух не более чем счетных множеств S и . Ясно, что если S и равномощны, то эти полурешетки соответственно изоморфны. Если S конечно, а бесконечно, то L(S) имеет наименьший элемент, а L() наименьшего элемента не имеет, следовательно, в этом случае L(S) и L() не изоморфны. Полурешетка имеет наименьший элемент. Рассмотрим, какие же минимальные (отличные от [o]) элементы она имеет. Каждому элементу sсоответствует одноэлементное множество L({s}). Нетрудно проверить, что соответствующий элемент будет минимальным, этот элемент будем обозначать . Пусть a – произвольный отличный от нуля элемент , тогда r(a)Ø. Пусть sr(a), тогда легко проверяется, что . Проведенные рассмотрения доказывают следующее

Предложение 8. Отображение устанавливает взаимно однозначное соответствие между элементами S и минимальными элементами .

Следствие. и L*() изоморфны тогда и только тогда, когда и равномощны.

Итак, неясным остается только вопрос, изоморфны ли полурешетки и L() для конечных множеств и , имеющих не менее двух элементов. Оказывается, что полурешетка для конечных , имеющих, по крайней мере, два элемента, обладает замечательным свойством универсальности, которое в качестве следствия влечет изоморфизм всех таких полурешеток. Переходим к точной формулировке этого результата.

Дистрибутивную полурешетку L назовем допустимой, если она имеет нуль и если всякий главный идеал L не более чем счетен. Заметим, что если конечно, то – допустимая полурешетка.

Теорема 1. Пусть – конечное множество, имеющее, по крайней мере, два элемента; пусть L – допустимая полурешетка мощности меньше континуума, – идеал L и – изоморфное вложение на идеал , тогда существует изоморфное вложение на идеал , которое продолжает (т.е. ).

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