3.3.2. Отношение нестрогого (частичного) порядка

При данном отношении справедливы аксиомы: 1) рефлексивности, 2) антисимметричности; 3) транзитивности.

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

Определение. Множества, на которых введено отношение нестрогого (частичного) порядка, называют частично упорядоченными. Частичный порядок на X называется линейным, если все пары элементов из X сравнимы, т.е. для любых х, у X можно выяснить (х  у) либо (у  х).

Пусть Х — частично упорядоченное множество. Наименьшим называют элемент аХ, который подчинен (не превосходит) всех остальных элементов X, т.е.х X (х  а). Наибольшим называют элемент аХ, которому подчинены все остальные элементы из X — х X (х  а). Обозначаются наименьший и наибольший элементы как minХ и mахХ.

У линейно упорядоченного множества любое подмножество также является линейно упорядоченным.

Пример 4. Рассмотрим в качестве исходного множество натуральных чисел N. Зададим на нем два варианта отношения нестрогого порядка с помощью предикатов:

1) Р(х, у) = «х  у» ,

2) Р(х, у) = «х делится без остатка на у».

Оба отношения удовлетворяют аксиомам рефлексивности, антисимметричности и транзитивности.

Первое отношение задает на N линейный порядок, поскольку оно определено для всех пар натуральных чисел. Наименьший элемент minХ= 1, наибольшего не существует.

Второе отношение не обеспечивает на N линейный порядок, поскольку существуют пары несравнимых натуральных чисел. Например, (2, 3), (4, 5) и т.д. Наименьшего и наибольшего элементов нет.

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

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

Для определения отношения строгого порядка достаточно проверить на парах элементов, составляющих его, справедливость только двух аксиом: 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). Матрицы отношений будут следующими:

		0	1	(0,1)
	1	1	1	1
0	0	1	-	1
1	0	-	1	1
(0,1)	0	0	0	1

		0	1	(0,1)
	0	1	1	1
0	0	0	-	1
1	0	-	0	1
(0,1)	0	0	0	0

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

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

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

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