Контрольная работа: Полурешетки m-степеней

Доказательство:

: Пусть , тогда посредством рекурсивной функции 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. Ясно, что с_Ø ≤_m h.

С одной стороны, (с_Ø ) – наименьший элемент, то есть с_Ø ≤_m h; с другой стороны с_Ø ≤_m h.

Получили противоречие, то есть в L наименьшего элемента нет. Ч.т.д.

Утверждение 3.2: m-степень, содержащая универсальную функцию, является наибольшей в L.

Доказательство:

Пусть Ψ – универсальная функция, а α – произвольная ЧРФ. Так как α – ЧРФ, то найдется такое число х₀ , что α=φ₀ .

Покажем, что . В качестве сводящей возмем функцию f(x₀ ,y). Тогда из определения Ψ вытекает, что , где , то есть .