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

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

= ( ) ( ) (2 ( ) .

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

= ( ) ( ) (2 ( ) .

Итак,

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

) f

) f .

Следовательно,

, ( ) и .□

Следствие. Если a

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

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

Предложение 3. Если

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

Действительно, если f

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

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

Рассмотрим пример, когда

. Для любого собственного подмножества М множества 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( \ ), тогда отображение для b L( ) (операция определена в L*( ) L( ) L( \ )) есть изоморфное отображение L( ) на некоторый идеал L( ).