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

Проверка того, что это частичный порядок, очевидна. Операция является для этого порядка операцией взятия точной верхней грани.

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

Множество называется продуктивным, если существует рекурсивная функция , называемая продуктивной функцией для , такая, что

Ясно, что продуктивное множество не может быть р.п. Если бы то Ø, что невозможно.

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

Множество называется креативным, если оно р.п. и продуктивно.

Заметим, что креативные множества по теореме Поста не могут быть рекурсивными. Примером креативного множества будет

Действительно

откуда рекурсивная функция является продуктивной функцией для .

Имеет место следующее утверждение: если В - р.п. множество, А -креативно, то - креативно.[1,5]

§2 Простейшие свойства m – степеней

Ведем отношение частного порядка на множестве m – степеней:

Обозначим через L частично упорядоченное множество m – степеней.

Утверждение 2.1: множество L является верхней полурешеткой.

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

Рассмотрим , где

.

Докажем, что эта функция является точной верхней гранью для произвольных ЧРФ α и β.

Рассмотрим γ^’ :

для рекурсивных функций g, f.

Определим функцию .

Проверим следующие равенства: .

Пусть x=2t, тогда и .

Пусть x=2t+1, тогда и .

Таким образом, равенство справедливо.

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