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

Таким образом, нумерация разрешима (позитивна, негативна) тогда и только тогда когда таковой является ее нумерационная эквивалентность.

Предложение 1

Нумерация бесконечного множества S является разрешимой тогда и только тогда когда она эквивалентна некоторой од

нозначной нумерации.

Предложение 2

Если – позитивное (негативное) отношение эквивалентности, то - нумерационная эквивалентность подходящей вычислимой нумерации

Предложение 3

Если - семейство попарно не пересекающихся непустых рекурсивно перечислимых множеств, а - вычислимая нумерация, то позитивна

Предложение 4

Если – семейство общерекурсивных функций, – вычислимая нумерация, то - негативная нумерация.

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

Предложение 5

Если S – бесконечное множество, – негативная нумерация S, то существует однозначная нумерация множества S такая что

Предложение 6

Пусть S – бесконечное множество, - позитивная нумерация множества S. Если существует однозначная нумерация множества S такая что , то – разрешимая нумерация.

Предложение 7

Пусть – позитивная нумерация S и , тогда

Следствие

Позитивные нумерации множества определяют минимальные элементы в L(S)

Минимальные нумерации

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

Нумерация ν: N → некоторого множества называется однозначной, если νn ≠ νm для n ≠ m N.

Интерес к изучению вопроса о существовании однозначных вычислимых нумераций у семейства объясняется такими обстоятельствами:

1. Всякая однозначная нумерация ν минимальна, т.е. [ν] – минимальный элемент в L°(S).

2. Если семейство S имеет хотя бы одну вычислимую однозначную нумерацию, то для любого R семейство \ {R} вычислимо (даже однозначно вычислимо, т.е. допускает однозначную вычислимую нумерацию).

Замечание: Отмеченное в 2 свойство является нетривиальным.

Справедливо следующее утверждение о семействе П.

Предложение 1. Семейство П обладает счетным семейством попарно неэквивалентных однозначных нумераций.□

Наиболее общими результатами о существовании однозначных вычислимых нумераций являются следующие две теоремы.

Теорема 1. Пусть вычислимое семейство содержит сильно перечислимое семейство конечных множеств такое, что

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

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

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

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

Теорема 2. Пусть вычислимое семейство содержит вычислимое подсемейство такое, что

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

б) частично упорядоченное множество < , > не имеет максимальных элементов;

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

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

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

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

Нумерацию определяем так:

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