
– общерекурсивная функция. Проверим, что

= (

)

. Пусть
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(

).