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

– общерекурсивная функция. Проверим, что = (). Пусть x таково, что f(x) четно, тогда

= ()() (2().

Пусть х таково, что f(x) нечетно, тогда

= ()() (2().

Итак, = ()и . Покажем теперь, что и . Пусть , тогда

) f

) f.

Следовательно, , ()и .□

Следствие. Если aL*(S) (L(S)), то полурешетка является дистрибутивной полурешеткой.□

Сводимость нумераций довольно близка понятию m – сводимости. Сейчас укажем простейшую связь.

Предложение 3. Если H*(S), , - нумерация множества , то для любого .

Действительно, если f Ơ – сводящая функция, т.е. = , то легко видеть, что функция f m – сводит .□

Необходимое условие сводимости нумераций, указанное в этом предложении, конечно, не является достаточным, однако существует частный случай, когда это так.

Рассмотрим пример, когда . Для любого собственного подмножества М множества N определим нумерацию множества S так:

Нумерация является просто характеристической функцией множества М. Нумерованное множество ({0,1},) будем обозначать .

Нетрудно проверить, что для имеем тогда и только тогда, когда . Отсюда вытекает следующее

Предложение 4. Верхняя полурешетка L({0,1}) классов эквивалентных нумераций множества {0,1} изоморфна верхней полурешетке всех m – степеней собственных подмножеств N.□

Следствие. Полурешетка классов эквивалентных нумераций двухэлементного множества имеет мощность континуума.

Действительно, собственных подмножеств N континуум, а каждая m – степень состоит не более чем из счетного семейства множеств.□

Отметим, что если S одноэлементно, то S имеет только одну нумерацию и, следовательно, в этом случае L(S) одноэлементна.

Если , то, очевидно, H*()H*(), L*()L*() и L*() является идеалом полурешетки L*(). Можно ли так же естественно вложить L() в L()? Ответ, вообще говоря, будет отрицательным в смысле «естественности», но некоторые изоморфные вложения L() в L() в качестве идеала будут построены. Конечно, нетривиальным случаем является только случай, когда – собственное подмножество .

Предложение 5. Пусть – собственное подмножество , а – минимальный элемент в L(\), тогда отображение для bL() (операция определена в L*()L()L(\)) есть изоморфное отображение L() на некоторый идеал L().

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