Отношение строгого порядка

Отношение данного типа задает способ сравнения элементов на множестве Х таким образом, что все возможныепары элементов (х, х)не принадлежат отношению. Данные отношения обозначают символом « < », так как на числовых множествах строгий порядок может быть задан предикатом «х строго меньше у».

Для определения отношения строгого порядка достаточно проверить на парах элементов, составляющих его, справедливость только двух аксиом: 1) асимметричности и 2) транзитивности.

Замечание. Зачастую в число аксиом отношения строгого порядка включают аксиому антирефлексивности. Однако, как показано выше, справедливость данной аксиомы следует из выполнения асимметричности.

По аналогии с частичным (нестрогим) порядком, множества, на которых введено отношение строгого порядка, называют строго упорядоченными. Данный порядок на X называется линейным, если все пары элементов из X сравнимы.

Пример 5. Рассмотрим для множества Х = Е₂ ={0,1} булеан [Х] = {(Æ); (0); (1); (0;1)}. Через{х}_i будем обозначать подмножества Х в порядке их вхождения в [Х]. Введем на множестве[Х]отношения строгого и нестрогого порядка соответственно при помощи предикатов:

а) Р({х}_i , {х}_j) = «{х}_i Ì{х}_j (подмножество {х}_i строго входит в подмножество {х}_j )»;

б) Q({х}_i ,{х}_j) = «{х}_i Í{х}_j (подмножество {х}_i нестрого входит в подмножество {х}_j )».

Если отрицаниям данных предикатов придать естественный смысл обратного включения:

ØР({х}_i ,{х}_j) = «{х}_j Í {х}_i» и Ø Q ({х}_i,{х}_j) = «{х}_j Ì {х}_i»,

то оба отношения будут вводить на [Х]соответственно частичный и строгий порядок. Оба порядка не будут линейными, поскольку не позволяют сравнить между собой {х}₂ = (0)и {х}₃ = (1). Матрицы отношений будут следующими:

Замечание. Если в Примере 5 в качестве отрицаний предикатов, задающих отношения, принять:

Ø Р({х}_i ,{х}_j) = «{х}_j Í {х}_i или {х}_j не сравнимо с {х}_i»,

Ø Q ({х}_i,{х}_j) = «{х}_j Ì {х}_i или {х}_j не сравнимо с {х}_i»,

то данные отношения будут задавать полный порядок.