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

В случае бесконечного 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(т.е. и ) такая, что = . Отношение является транзитивным, а отношение является отношением эквивалентности.