Бинарное отношение R на множестве X называется антисимметричным, если из x R y и y R x следует: x = y. Бинарное отношение R на множестве X называется отношением порядка, если оно рефлексивно, антисимметрично и транзитивно. Легко видеть, что это равносильно выполнению следующих условий:
1) IdX Í R (рефлексивность),
2) R Ç R-1 (антисимметричность),
3) R ° R Í R (транзитивность).
Упорядоченная пара (X, R), состоящая из множества X и отношения порядка R на X, называется частично упорядоченным множеством.
Пример 1
Пусть X = {0, 1, 2, 3}, R = {(0, 0), (0, 1), (0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 2), (3, 3)}.
Поскольку R удовлетворяет условиям 1 – 3, то (X, R) – частично упорядоченное множество. Для элементов x = 2, y = 3, неверно ни x R y, ни y R x. Такие элементы называют несравнимыми. Обычно отношение порядка обозначают £. В приведенном примере 0 £ 1 и 2 £ 2, но неверно, что 2 £ 3.
Пример 2
Пусть < – бинарное отношение строгого неравенства на множестве w натуральных чисел, рассмотренное в разд. 1.2. Тогда объединение отношений = и < является отношением порядка £ на w и превращает w в частично упорядоченное множество.
Элементы x, y Î X частично упорядоченного множества (X, £) называются сравнимыми, если x £ y либо y £ x.
Частично упорядоченное множество (X, £) называется линейно упорядоченным или цепью, если любые два его элемента сравнимы. Множество из примера 2 будет линейно упорядоченным, а из примера 1 – нет.
Подмножество A Í X частично упорядоченного множества (X, £) называется ограниченным сверху, если существует такой элемент x Î X, что a £ x для всех a Î A. Элемент x Î X называется наибольшим в X, если y £ x для всех y Î X. Элемент x Î X называется максимальным, если нет отличных от x элементов y Î X, для которых x £ y. В примере 1 элементы 2 и 3 будут максимальными, но не наибольшими. Аналогично определяются ограничение снизу подмножества, наименьший и минимальный элементы. В примере 1 элемент 0 будет и наименьшим и минимальным. В примере 2 этими свойствами также обладает 0, но в (w, £) нет ни наибольшего, ни максимального элемента.
Пусть (X, £) – частично упорядоченное множество, A Í X – подмножество. Отношение на А, состоящее из пар (a, b) элементов a, b Î A, для которых a £ b, будет отношением порядка на А. Это отношение обозначают тем же символом: £. Таким образом, (A, £) – частично упорядоченное множество. Если оно является линейно упорядоченным, то будем говорить, что А – цепь в (X, £).