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

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

Множество

- рекурсивно перечислимо (РП), в интуитивном смысле, если существует эффективная процедура, которая выписывает элементы этого множества. Каждый элемент на некотором шаге будет выписан.

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

Характеристической функцией множества

называется функция

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

Множество

называется рекурсивным, если характеристическая функция является рекурсивной.

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

Функция

m-сводима к функции ( ), в точности тогда, когда существует рекурсивная функция , такая, что

Функция

называется сводящей функцией.

Введем отношение m-эквивалентности на множестве

.

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

Введем понятие m-степени функции

.

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

Введем понятие m-сводимости множеств.

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

Множество

m-сводимо к множеству (обозначение ), если существует рекурсивная функция такая, что В этом случае говорят, что m-сводимо к посредством .

Аналогично вводится понятие m-степени множества

.

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

Частичная характеристическая функция для множества

-функция

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

ЧРФ – универсальная для множества

, если ( -рекурсивная функция ) где - ЧРФ с геделевым номером .

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

Если на множестве

определено бинарное отношение , удовлетворяющее условиям:

1.

(рефлексивность);

2.

(антисимметричность);

3.

(транзитивность),

то множество

называется частично упорядоченным, а отношение называется частичным порядком на . Отношение , удовлетворяющее только свойствам 1,3, называется предпорядком на . Если частичный порядок на удовлетворяет условию

4.

то называется линейным порядком (или просто порядком), а -линейно упорядоченным множеством или цепью.

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

Верхней (нижней) гранью подмножества

называется такой элемент что ( ) для любого . Элемент называется max (min) элементом , если ( ) для всех

Если же

( ) для любых ? ,то элемент называется наибольшим (наименьшим).

Определение 19.

Наименьшая (наибольшая) из верхних (нижних) граней множества

называется точной верхней (нижней) гранью этого множества.

Определение 20.

Полурешеткой (точнее, верхней полурешеткой) назовем пару

где - непустое множество, а -бинарная операция на , удовлетворяющая условиям: для любого

1.

2.

3.

Если

- полурешетка, то зададим на частичный порядок следующим соотношением: для

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

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

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

Множество

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

Ясно, что продуктивное множество

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