Полурешетки m-степеней
Содержание
Введение
Теоретическая часть
§1 Основные определения
§2 Простейшие свойства m – степеней
§3 Минимальные элементы верхней полурешетки m-степеней
2. Практическая часть
§1. Идеалы полурешетки m-степеней частично рекурсивных функций
Литература
Введение
Сейчас много внимания уделяется вопросам сводимости функций. Данная работа посвящена одной из разновидностей сводимости частично рекурсивной функции, а именно m-сводимости.
Для дальнейшего рассмотрения этого вопроса будем пользоваться общепринятыми понятиями и теоретико-множественными обозначениями.
Символы логических операций: отрицания, конъюнкции, дизъюнкции, импликации, и эквивалентности будем обозначать: , соответственно.
Кванторы общности и существования обозначают соответственно.
Совокупность всех целых неотрицательных чисел обозначим через N.
Под множеством будем понимать подмножество N.
Латинскими буквами A,B,C,… будем обозначать множества.
Объединение множества A и B обозначим через пересечения этих множеств - а разность , дополнение - .
Пусть 1*2*…*n 1,2,…,n11, 22,…,nn-декартово произведение множеств 1,2,…,n.
Определение: Функции называется арифметической, если ее аргументы пробегают натуральный ряд N, и сама функция принимает лишь натуральные значения.
Под n-местной частичной арифметической функцией будем понимать функцию, отображающую некоторое множество в N ,где -n-ая декартовая степень множества N.
Греческими строчными буквами будем обозначать частично рекурсивные функции (ЧРФ) : .
Всякий раз, когда число аргументов явно не указывается, речь идет об одноместных функциях. Обозначим через множество всех одноместных ЧРФ.
Запись означает, что функция для этой n-ки не определена, а запись означает, что функция для этой n-ки определена.
Множество называют областью значений функции , а множество область определения функции .
Определение: Частичную n-местную функцию назовем всюду определенной, если .
Всюду определенная функция будет обозначаться латинскими буквами: f,g,h,… . [5,6]
Теоретическая часть
§1 Основные определения
Определение 1: (интуитивное).
Арифметическая функция называется частично рекурсивной, если существует алгоритм для нахождения ее значений.
Определение 2:
Под начальными функциями будем понимать следующие функции:
функция следования S ;
функции выбора
,
нулевая функция .
Определение 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]
§2 Простейшие свойства m – степеней
Ведем отношение частного порядка на множестве m – степеней:
Обозначим через L частично упорядоченное множество m – степеней.
Утверждение 2.1: множество L является верхней полурешеткой.
Доказательство:
Рассмотрим , где
.
Докажем, что эта функция является точной верхней гранью для произвольных ЧРФ α и β.
Рассмотрим γ’:
для рекурсивных функций g, f.
Определим функцию .
Проверим следующие равенства: .
Пусть x=2t, тогда и