Xreferat.com » Рефераты по математике » Полурешетки m-степеней

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

height="22" align="BOTTOM" border="0" />.

Пусть x=2t+1, тогда Полурешетки m-степеней и Полурешетки m-степеней.

Таким образом, равенство Полурешетки m-степеней справедливо.

Следовательно, функция Полурешетки m-степеней является точной верхней гранью для произвольных ЧРФ α и β, ч.т.д.

Утверждение 2.2: Полурешетки m-степеней.

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

Полурешетки m-степеней: Пусть Полурешетки m-степеней, тогда Полурешетки m-степеней посредством рекурсивной функции f, которая множество А m – сводит к В.

Полурешетки m-степеней : Аналогично Полурешетки m-степеней, ч.т.д.

Следствие: существует изоморфное вложение полурешетки m-степеней рекурсивно перечисляемых множеств в полурешетку m-степеней частичных характеристических функций: Полурешетки m-степеней.

Утверждение 2.3: Полурешетки m-степеней.

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

Если Полурешетки m-степенейШ, то утверждение справедливо.

Пусть Полурешетки m-степенейШ. Возьмем Полурешетки m-степеней, откуда Полурешетки m-степеней для некоторого Полурешетки m-степеней; а так как Полурешетки m-степеней для некоторой рекурсивной функции f, то Полурешетки m-степеней и Полурешетки m-степеней.

Таким образом, Полурешетки m-степеней, ч.т.д.

Следствие: функции, принадлежащие одной и той же m-степени, имеют одинаковую область значений.

Утверждение 2.4: Пусть f, g – рекурсивные функции, тогда Полурешетки m-степеней.

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

Полурешетки m-степеней: Следует из следствия к 2.3.

Полурешетки m-степеней: Пусть Полурешетки m-степеней: покажем, что Полурешетки m-степеней, то есть Полурешетки m-степеней.

Строим Полурешетки m-степеней таким образом: допустим Полурешетки m-степеней, начинаем последовательно вычислять g(0), g(1), …, пока не получим, что g(n)=i, а такое n обязательно появится, так как Полурешетки m-степеней.

Полагаем, что Полурешетки m-степеней, тогда очевидно, что Полурешетки m-степеней.

Аналогично строим функцию Полурешетки m-степеней, такую, что Полурешетки m-степеней. Отсюда получим, что Полурешетки m-степеней.

Таким образом, так как Полурешетки m-степеней и Полурешетки m-степеней, ч.т.д. [1]

§3 Минимальные элементы верхней полурешетки m-степеней


Утверждение 3.1: Наименьшего элемента в L нет.

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

Допустим противное, то есть пусть Полурешетки m-степеней - наименьший в L элемент. Тогда Полурешетки m-степенейШ), где сШ – нигде неопределенная функция.

Следовательно, Полурешетки m-степенейШ и Полурешетки m-степеней(сШ).

Возьмем всюду определенную функцию h. Ясно, что сШ≤mh.

С одной стороны, Полурешетки m-степеней(сШ) – наименьший элемент, то есть сШ≤mh; с другой стороны сШ≤mh.

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

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

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

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

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

Таким образом, Полурешетки m-степеней - наибольшая в L. Ч.т.д.

Введем обозначение: Полурешетки m-степеней.

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

Утверждение 3.3: сШ и множество всех функций вида cn(x) и только они образуют множество минимальных в L элементов.

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

Из утверждения 3.1. следует, что сШ – минимальный в L элемент.

Возьмем произвольную функцию cn(x).

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

Ясно, что Полурешетки m-степеней{Полурешетки m-степеней}, кроме того α – всюду определенная функция, так как иначе Полурешетки m-степеней, следовательно, Полурешетки m-степеней.

Пусть теперь Полурешетки m-степеней минимальный в L элемент, отличный от сШ и от всех сn, тогда Полурешетки m-степеней определена в некоторой точке х0; пусть Полурешетки m-степеней, имеем Полурешетки m-степеней, где Полурешетки m-степеней, то есть, Полурешетки m-степеней. Получили противоречие. Ч.т.д. [1,2]

2. Практическая часть.


§1. Идеалы полурешетки m-степеней частично рекурсивных функций


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

Идеалом полурешетки L назовем всякое подмножество I отличное от Ш, удовлетворяющее следующим условиям:


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

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


Идеал называется главным, если он содержит наибольший элемент.

Рассмотрим множество всех m-степеней частичных характеристических функций, то есть:


Н={Полурешетки m-степеней}.


Предположение 4.1:

Множество Н является главным идеалом полурешетки L.

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

Берем две степени Полурешетки m-степеней для некоторых р.п. множеств А и В. точной верхней гранью будет степень, содержащая функцию Полурешетки m-степеней.

Определим множество АПолурешетки m-степенейВ:


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

Докажем, что Полурешетки m-степеней.

Будем пользоваться определением 15 для доказательства данного равенства.

Рассмотрим 4 случая.


если x=2t, Полурешетки m-степеней

И если x=2t, Полурешетки m-степеней

Если x=2t, Полурешетки m-степеней

И если x=2t, Полурешетки m-степеней

Если x=2t+1, Полурешетки m-степеней

И если x=2t+1, Полурешетки m-степеней

Если x=2t+1, Полурешетки m-степеней

И если x=2t+1, Полурешетки m-степеней


Следовательно, равенство Полурешетки m-степеней справедливо во всех четырех случаях, т.к. обе его части равносильны в рассмотренных случаях.


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


Пусть Полурешетки m-степеней. По определению m-сводимости из Полурешетки m-степеней следует, что существует рекурсивная функция f такая, что: Полурешетки m-степеней, откуда Полурешетки m-степеней. Из утверждения 2.2 и того, что всякое р.п. множество m-сводимо к креативному следует, что: Полурешетки m-степеней - наибольший элемент в Н, где k – креативно.

Тогда Н – главный идеал полурешетки L. Ч.т.д.

Рассмотрим множество всех m-степеней рекурсивных функций, то есть:

М={Полурешетки m-степеней}.

Предположение 4.2: Данное множество М является главным идеалом полурешетки L.

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

Берем две степени рекурсивных функций, их точной верхней гранью будет Полурешетки m-степеней, где Полурешетки m-степеней также рекурсивная функция.

Если Полурешетки m-степеней, откуда существует рекурсивная функция h, такая, что Полурешетки m-степеней, где Полурешетки m-степеней также рекурсивная функция. Далее, Полурешетки m-степеней посредством f(x) для любой рекурсивной функции f(x), отсюда Полурешетки m-степеней - наибольший элемент в М.

М – главный идеал полурешетки L. Ч.т.д.

Литература


Дегтев А.Н. Сводимость частично-рекурсивных функций. – Сибирский математический журнал, 1975 т. 16, №5, с. 970-988.

Ершов Ю.Л. Теория нумераций. – М.: Наука, 1977.

Кагленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М.: Мир, 1983.

Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965.

Поляков Е.А., Розинас М.Г. Теория алгоритмов. – Иваново: ИвГУ, 1976.

Поляков Е.А., Маринина Н.В. Теория алгоритмов. – Шуя: ШГПУ, 2004.

Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. – М.: Мир, 1972.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: