Полурешетки m-степеней

§1 Основные определения

Определение 1: (интуитивное).

Арифметическая функция называется частично рекурсивной, если существует алгоритм для нахождения ее значений.

Определение 2:

Под начальными функциями будем понимать следующие функции:

1. функция следования S ;

2. функции выбора

,

3.

4. нулевая функция .

Определение 3: (оператор суперпозиции (подстановка)).

Говорят, что функция получена суперпозицией из функций и , если для всех значений выполняется равенство:

Определение 4: (оператор примитивной рекурсии ).

Говорят, что функция получена из двух функций и с помощью оператора примитивной рекурсии, если имеют место следующие равенства:

.

Это определение применимо и при n=0. Говорят, что функция получена из одноместной функции константы равной и функции , если при всех :

Определение 5: (-оператор или оператор минимизации).

Определим -оператор сначала для одноместных функций.

Будем говорить, что функция получена из частичной функции с помощью оператора, если,

_.

В этом случае -оператор называется оператором обращения и -наименьшее .

Теперь определим -оператор в общем виде:

Определение 6:

Функция называется частично рекурсивной функцией (ЧРФ) ,если она может быть получена из начальных функций с помощью конечного числа применений трех операторов: суперпозиции, примитивной рекурсии, -оператора.

Определение 7:

Если - ЧРФ и всюду определена, то она называется рекурсивной функцией.

Определение 8:

Множество - рекурсивно перечислимо (РП), в интуитивном смысле, если существует эффективная процедура, которая выписывает элементы этого множества. Каждый элемент на некотором шаге будет выписан.

Определение 9:

Характеристической функцией множества называется функция

Определение 10:

Множество называется рекурсивным, если характеристическая функция является рекурсивной.

Определение 11:

Функция m-сводима к функции (), в точности тогда, когда существует рекурсивная функция , такая, что

Функция называется сводящей функцией.

Введем отношение m-эквивалентности на множестве .

Определение 12:

Введем понятие m-степени функции .

Определение 13:

Введем понятие m-сводимости множеств.

Определение 14:

Множество m-сводимо к множеству (обозначение ), если существует рекурсивная функция такая, что В этом случае говорят, что m-сводимо к посредством .

Аналогично вводится понятие m-степени множества .

Определение 15:

Частичная характеристическая функция для множества -функция

Определение 16:

ЧРФ - универсальная для множества , если (-рекурсивная функция ) где - ЧРФ с геделевым номером .

Определение 17:

Если на множестве определено бинарное отношение , удовлетворяющее условиям:

1. (рефлексивность);

2. (антисимметричность);

3. (транзитивность),

то множество называется частично упорядоченным, а отношение называется частичным порядком на . Отношение , удовлетворяющее только свойствам 1,3, называется предпорядком на . Если частичный порядок на удовлетворяет условию

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

Определение 18:

Верхней (нижней) гранью подмножества называется такой элемент что () для любого . Элемент называется max (min) элементом , если () для всех

Если же () для любых ? ,то элемент называется наибольшим (наименьшим).

Определение 19.

Наименьшая (наибольшая) из верхних (нижних) граней множества называется точной верхней (нижней) гранью этого множества.

Определение 20.

Полурешеткой (точнее, верхней полурешеткой) назовем пару где - непустое множество, а -бинарная операция на , удовлетворяющая условиям: для любого

1.

2.

3.

Если - полурешетка, то зададим на частичный порядок следующим соотношением: для

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

Определение 21:

Множество называется продуктивным, если существует рекурсивная функция , называемая продуктивной функцией для , такая, что

Ясно, что продуктивное множество не может быть р.п. Если бы то Ш, что невозможно.

Определение 22:

Множество называется креативным, если оно р.п. и продуктивно.

Заметим, что креативные множества по теореме Поста не могут быть рекурсивными. Примером креативного множества будет

Действительно

откуда рекурсивная функция является продуктивной функцией для .

Имеет место следующее утверждение: если В - р.п. множество, А -креативно, то - креативно. [1,5]