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

а) любое множество из S есть объединение возрастающей последовательности множеств из

;

б) любое множество из

содержится в некотором собственном подмножестве из .

Тогда существует однозначная вычислимая нумерация семейства

.□

Введем следующие определения. Множество М предельно для семейства множеств

, если для любого конечного подмножества M в существует М' такое, что М'. Семейство предельно для семейства , если любое множество из предельно для семейства .

Теорема 2. Пусть вычислимое семейство

содержит вычислимое подсемейство такое, что

а) если два множества из

имеют непустое пересечение, то одно из них содержится в другом;

б) частично упорядоченное множество <

, > не имеет максимальных элементов;

в) семейство

предельно для семейства .

Тогда существует однозначная вычислимая нумерация семейства

.□

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

не имеют однозначных нумераций, но имеют позитивные нумерации. Укажем простейший пример.

Пусть А – рекурсивно перечислимое нерекурсивное множество, полагаем

Нумерацию

определяем так:

Ясно, что

– вычислимая нумерация семейства . Можно заключить, что любая другая вычислимая нумерация семейства эквивалентна . Заметим теперь, что – неразрешимая нумерация. Последнее следует из эквивалентности .

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

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

Предложение 2. Пусть вычислимое семейство

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

Предложение 3. Если вычислимое семейство

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

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

У П, а также и у других семейств

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

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

Пусть

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

Пусть

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

Если

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