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

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

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

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

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

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

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

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

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

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

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

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