В случае бесконечного 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) Ø. Пусть s r( a), тогда легко проверяется, что . Проведенные рассмотрения доказывают следующееПредложение 8. Отображение
устанавливает взаимно однозначное соответствие между элементами S и минимальными элементами .Следствие.
и L*( ) изоморфны тогда и только тогда, когда и равномощны.Итак, неясным остается только вопрос, изоморфны ли полурешетки
и L( ) для конечных множеств и , имеющих не менее двух элементов. Оказывается, что полурешетка для конечных , имеющих, по крайней мере, два элемента, обладает замечательным свойством универсальности, которое в качестве следствия влечет изоморфизм всех таких полурешеток. Переходим к точной формулировке этого результата.Дистрибутивную полурешетку L назовем допустимой, если она имеет нуль и если всякий главный идеал L не более чем счетен. Заметим, что если
конечно, то – допустимая полурешетка.Теорема 1. Пусть
– конечное множество, имеющее, по крайней мере, два элемента; пусть L – допустимая полурешетка мощности меньше континуума, – идеал L и – изоморфное вложение на идеал , тогда существует изоморфное вложение на идеал , которое продолжает (т.е. ).Следствие 1. Если
и – конечные множества, имеющие, по крайней мере, два элемента, то полурешетки и L( ) изоморфны.Следствие 2. Если
– конечное множество, имеющее, по крайней мере, два элемента, то полурешетка изоморфна полурешетке всех m – степеней собственных подмножеств N.Следствие 3. Если
, то полурешетка и изоморфны.Это также нетрудное следствие свойства универсальности, указанного в теореме.
Перейдем теперь к изучению более тонкого отношения сводимости между нумерациями. Пусть
– непустые подмножества , 1 – сводится к ( ), если существует одно – однозначная общерекурсивная функция f (1 – сводящая функция) такая, что = . Класс всех одноместных одно – однозначных общерекурсивных функций обозначим . Нумерации назовем изоморфными ( ), если существует общерекурсивная перестановка f(т.е. и ) такая, что = . Отношение является транзитивным, а отношение является отношением эквивалентности.