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

Ясно, что – вычислимая нумерация семейства . Можно заключить, что любая другая вычислимая нумерация семейства эквивалентна 5 height=22 src="images/referats/3088/image123.png">. Заметим теперь, что – неразрешимая нумерация. Последнее следует из эквивалентности .

Замечание. Естественная нумерация слов конечного алфавита определяет некоторую нумерацию свободной полугруппы с образующими из этого алфавита. Эта нумерация слов определяет (порождает) и нумерацию любой конечно определенной полугруппы, причем последняя, всегда будет позитивной.

Существует довольно много достаточных условий существования (хотя бы одной) позитивной нумерации. Приведем для примера следующие предложения.

Предложение 2. Пусть вычислимое семейство содержит вычислимое семейство конечных множеств такое, что S предельно для , тогда имеет позитивную нумерацию.□

Предложение 3. Если вычислимое семейство содержит наибольшее по включению множество, имеет позитивную нумерацию.

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

У П, а также и у других семейств может существовать и много минимальных непозитивных нумераций.

Нумерации множества и его подмножеств

Пусть – произвольное непустое не более чем счетное множество. Нумерацией множества назовем всякое отображение ν множества N всех натуральных чисел на множество . Пара = (S, ν), где ν – некоторая нумерация множества S, называется нумерованным множеством. Для дальнейшего будет удобно считать, что и пустое множество Ø обладает некоторой единственной «нумерацией» o, а «нумерованное» множество (Ø, o) будем обозначать О.

Пусть – два подмножества S и – нумерации множеств соответственно. Будем говорить, сводится к (), если = o (и тогда = Ø) или o, o и существует общерекурсивная функция f такая, что x = f(x) для любого , короче = . Такую функцию будем называть сводящей. Заметим, что из следует, что . Действительно, если = o, то , если же o и s, то x = s для некоторого xN, но x = f(x). Легко проверяется, что отношение сводимости является рефлексивным и транзитивным. Если , то нумерации и назовем эквивалентными (. Класс всех нумераций, эквивалентных ν, обозначим через [ν].

Если - нумерация , s, nN и n = s, то число n называется - номером элемента s. Сводимость нумерации к означает, что по любому - номеру любого элемента из можно эффективно найти некоторый - номер этого же элемента.

Множество всех нумераций множества S обозначим через H (S), а множество всех нумераций подмножества S (включая пустое) обозначим через H*(S). Определим отображение r множества H* (S) на Р(S) – множество всех подмножеств S – так: r(o)Ø; r(ν)ν(N) для νoH*(S). Отметим, что для любого подмножества и H*(S) = .

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