Полурешетки m-степеней (стр. 3 из 4)
Определение 22:
Множество
называется креативным, если оно р.п. и 
продуктивно.Заметим, что креативные множества по теореме Поста не могут быть рекурсивными. Примером креативного множества будет
Действительно
откуда рекурсивная функция
является продуктивной функцией для 
.Имеет место следующее утверждение: если
В - р.п. множество, А -креативно, то 
- креативно.[1,5]§2 Простейшие свойства m – степеней
Ведем отношение частного порядка на множестве m – степеней:
Обозначим через L частично упорядоченное множество m – степеней.
Утверждение 2.1: множество L является верхней полурешеткой.
Доказательство:
Рассмотрим
, где 
.Докажем, что эта функция является точной верхней гранью для произвольных ЧРФ α и β.
Рассмотрим γ’:
для рекурсивных функций g, f.Определим функцию
.Проверим следующие равенства:
.Пусть x=2t, тогда
и 
.Пусть x=2t+1, тогда
и 
.Таким образом, равенство
справедливо.Следовательно, функция
является точной верхней гранью для произвольных ЧРФ α и β, ч.т.д.Утверждение 2.2:
.Доказательство:
: Пусть 
, тогда 
посредством рекурсивной функции f, которая множество А m – сводит к В. 
: Аналогично 
, ч.т.д.Следствие: существует изоморфное вложение полурешетки m-степеней рекурсивно перечисляемых множеств в полурешетку m-степеней частичных характеристических функций:
.Утверждение 2.3:
.Доказательство:
Если
Ø, то утверждение справедливо.Пусть
Ø. Возьмем 
, откуда 
для некоторого 
; а так как 
для некоторой рекурсивной функции f, то 
и 
.Таким образом,
, ч.т.д.Следствие: функции, принадлежащие одной и той же m-степени, имеют одинаковую область значений.
Утверждение 2.4: Пусть f, g – рекурсивные функции, тогда
.Доказательство:
: Следует из следствия к 2.3. : Пусть 
: покажем, что 
, то есть 
.Строим
таким образом: допустим 
, начинаем последовательно вычислять g(0), g(1), …, пока не получим, что g(n)=i, а такое n обязательно появится, так как .Полагаем, что
, тогда очевидно, что .Аналогично строим функцию
, такую, что 
. Отсюда получим, что 
.Таким образом, так как
и 
, ч.т.д. [1]§3 Минимальные элементы верхней полурешетки m-степеней
Утверждение 3.1: Наименьшего элемента в L нет.
Доказательство:
Допустим противное, то есть пусть
- наименьший в L элемент. Тогда 
Ø), где сØ – нигде неопределенная функция.Следовательно,
Ø и 
(сØ).Возьмем всюду определенную функцию h. Ясно, что сØ≤mh.
С одной стороны,
(сØ) – наименьший элемент, то есть сØ≤mh; с другой стороны сØ≤mh.Получили противоречие, то есть в L наименьшего элемента нет. Ч.т.д.
Утверждение 3.2: m-степень, содержащая универсальную функцию, является наибольшей в L.
Доказательство:
Пусть Ψ – универсальная функция, а α – произвольная ЧРФ. Так как α – ЧРФ, то найдется такое число х0, что α=φ0.
Покажем, что
. В качестве сводящей возмем функцию f(x0,y). Тогда из определения Ψ вытекает, что 
, где 
, то есть .Таким образом,
- наибольшая в L. Ч.т.д.Введем обозначение:
.Ясно, что
.Утверждение 3.3: сØ и множество всех функций вида cn(x) и только они образуют множество минимальных в L элементов.
Доказательство.
Из утверждения 3.1. следует, что сØ – минимальный в L элемент.
Возьмем произвольную функцию cn(x).
Пусть
.Ясно, что
{ 
}, кроме того α – всюду определенная функция, так как иначе 
, следовательно, 
.Пусть теперь
минимальный в L элемент, отличный от сØ и от всех сn, тогда 
определена в некоторой точке х0; пусть 
, имеем 
, где 
, то есть, 
. Получили противоречие. Ч.т.д. [1,2]