Отношения порядка. Максимальные и минимальные, наибольший и наименьший элементы частично упорядоченного множества. Диаграммы Хассе. Линейно и вполне упорядоченные множества

Отношение называется предпорядком или квазипорядком, если Р рефлексивно и транзитивно.

Отношение называется частичным порядком, если Р рефлексивно, транзитивно и антисимметрично. Т.е. частичный порядок – это антисимметричный предпорядок.

Множество, с заданным на нём частичным порядком называется частично упорядоченным множеством (ЧУМ)

Пусть <A,≤> - ЧУМ. Тогда элемент называется наибольшим, если . Элемент называется наименьшим, если . Элемент называется максимальным, если для него нет большего, т.е. , если , то . Элемент называется минимальным, если для него нет меньшего, т.е. , если , то .

Наименьший элемент всегда минимален (наибольший – максимален). Обратное неверно.

Наибольший элемент часто называют единицей. Наименьший – нулем.

Диаграммы Хассе:

Рассмотрим ЧУМ <A,≤>. Говорят, что элемент y покрывает элемент x, если x≤y и x≠y не существует такого элемента z, что x<z<y. Если множество А конечно, то частично упорядоченное множество <A,≤> можно представить в виде схемы, в которой каждый элемент изображается точкой на плоскости, и если y покрывает х, то точки х и y соединяются отрезком, причем точку х располагают ниже y. Такие схемы называются диаграммами Хассе.

Частичный порядок ≤ на множестве А называется линейным порядком, если любые два элемента x и y из множества А сравнимы, т.е. x≤y или y≤x.

Линейный порядок ≤ на множестве А называется полным, если каждое непустое подмножество множества А имеет наименьший элемент. Пара <A,≤>, в которой отношение ≤ является полным порядком на множестве А, называется вполне упорядоченным множеством.