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

Следствие 1. Если и – конечные множества, имеющие, по крайней мере, два элемента, то полурешетки и L() изоморфны.

Следствие 2. Если idth=9 height=22 src="images/referats/3088/image115.png">– конечное множество, имеющее, по крайней мере, два элемента, то полурешетка изоморфна полурешетке всех m – степеней собственных подмножеств N.

Следствие 3. Если , то полурешетка и изоморфны.

Это также нетрудное следствие свойства универсальности, указанного в теореме.

Перейдем теперь к изучению более тонкого отношения сводимости между нумерациями. Пусть – непустые подмножества , 1 – сводится к (), если существует одно – однозначная общерекурсивная функция f (1 – сводящая функция) такая, что = . Класс всех одноместных одно – однозначных общерекурсивных функций обозначим . Нумерации назовем изоморфными (), если существует общерекурсивная перестановка f (т.е. и ) такая, что = . Отношение является транзитивным, а отношение является отношением эквивалентности.

Теорема 2. Пусть – две нумерации множества . Если и , то .

Пусть и 1 – сводят и соответственно, т.е. = и = . Определим теперь функции следующим образом:

Имеем и .

Положим , . Заметим, что для любого

Лемма 1. Если – конечное множество, то и – конечное множество, имеющее то же число элементов, и наоборот. В этом случае

Покажем сначала, что либо функция , либо она является строго периодической, т.е. существует z > 0 такое, что . Предположим, что . Тогда существуют такие, что . Но , а . Так как , имеем .

Итак, если – конечное множество, содержащее n + 1 элемент, то его элементы представляют собой значения функции от первых n +1 аргументов. Пусть

Тогда . Имеем

так как и . Эти элементы различны, а

Итак, если конечно, то конечно, и отображение осуществляется взаимно однозначное соответствие между и . Аналогично, отображение осуществляется взаимно однозначное соответствие между и . Если конечно, то и конечно. Но . Отсюда очевидно, что также конечно и , так что .

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