Смекни!
smekni.com

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

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

множества S называется однозначной, если νn ≠ νmдля любых nm
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(т.е.
и
) такая, что
=
. Отношение
является транзитивным, а отношение
является отношением эквивалентности.