2015-02-24
420
Бинарное отношение на А называется предпорядком на А, если оно рефлексивно и транзитивно (например, отношение «х делитель у» на множестве целых чисел).
Частичным порядком на А называется бинарное отношение рефлексивное, транзитивное и антисимметричное. Частичный порядок часто обозначается символом “£”. Порядок £-1 называется двойственным к £ и обозначается символом “³”. Будем писать x<y, если x<y и x¹y. Частичный порядок £ на множестве А называется линейным, если два любые элемента из А сравнимы между собой по £, т.е. x£y или y£x для любых х,у ÎА. Множество А с заданным на нем частичным (линейным) порядком называется частично (линейно) упорядоченным.
Часто частично упорядоченное множество (ЧУМ) изображают в виде графа H=(V,£), из которого удалены все петли и транзитивно замыкающие дуги. Такой граф называется диаграммой Хассе. Диаграмма Хассе известна с конца XIX века. В течение многих лет ее применяли в генеалогии для задания родства.
Понятие непосредственного старшего легко задается в ЧУМ следующим определением: x покрывает у тогда и только тогда, когда y<x и не найдется такого элемента z, что y<z<x.
|
|
|
Таблица 3 Свойства отношений порядка
| Понятие | Свойство или определение | Пояснения |
| Рефлексивный ЧП в А | · R£A´A, · R рефлексивно в А, · R транзитивно в А, · R антисимметрично в А. | iAÍ R, R·R=R, xRy и yRx Û x=y. |
| Иррефлексивный ЧП в А | · R Í A2, · R иррефлексивный, транзитивный, асимметричный. | |
| R- ЧП в А, В Í А, B минимальный элемент в В: b = min B d – максимальный элемент в В: d = max B | · "x: xÎB Þ b<x, bÎB, · "x:xÎB Þ x<b, bÎB. | Элементы b и d сравнимы со всеми элементами из В. |
| R – ЧП в А, ВÍА, а,bÎА. а – нижняя грань В, b – верхняя грань В. | · "x: xÎB Þ a £ x, · "x: xÎB Þ x £ b. | В отличие от минимального и максимального элемента В а и b не обязательно принадлежат В. |
| R – ЧП в А, ВÍА; u, oÎA. u=inf B (точная нижняя граница В), o=sup B (точная верхняя граница В). | · u – максимальный элемент нижней грани, · о – минимальный элемент верхней грани. | Точная верхняя и нижняя границы не всегда существуют. |
| R – ЧП в А, ВÍА; В - цепь в А | "x,y: x,yÎBÞx£y или y£x. | В линейно упорядочено отношением В2 Ç £. |
Подмножество В множества А, частично упорядоченного отношением £, называется цепью в А, если оно линейно упорядочено отношением £ Ç В2.
Отношением частичного порядка является отношение включения (Í) на булеане конечного множества; примером линейного порядка является отношение £ на множестве чисел.
