Контрольная работа: Полурешетки m-степеней
Введем обозначение: 
.
Ясно, что 
.
Утверждение 3.3: сØ и множество всех функций вида cn (x) и только они образуют множество минимальных в L элементов.
Доказательство.
Из утверждения 3.1. следует, что сØ – минимальный в L элемент.
Возьмем произвольную функцию cn (x).
Пусть 
.
Ясно, что 
{
}, кроме того α – всюду определенная функция, так как иначе 
, следовательно, 
.
Пусть теперь 
минимальный в L элемент, отличный от сØ и от всех сn , тогда 
определена в некоторой точке х0 ; пусть 
, имеем 
, где 
, то есть, 
. Получили противоречие. Ч.т.д. [1,2]
2. Практическая часть.
§1. Идеалы полурешетки m-степеней частично рекурсивных функций
Определение:
Идеалом полурешетки L назовем всякое подмножество I отличное от Ø, удовлетворяющее следующим условиям:
1. 
;
2. 
.
Идеал называется главным, если он содержит наибольший элемент.
Рассмотрим множество всех m-степеней частичных характеристических функций, то есть:
Н={
}.
Предположение 4.1:
Множество Н является главным идеалом полурешетки L.
Доказательство:
1. Берем две степени 
для некоторых р.п. множеств А и В. точной верхней гранью будет степень, содержащая функцию 
.
Определим множество А
В:
{
}.
Докажем, что 
.
Будем пользоваться определением 15 для доказательства данного равенства.
Рассмотрим 4 случая.
1) если x=2t, 
И если x=2t, 
2) Если x=2t, 
И если x=2t, 