R называется бинарным отношением на множестве D, если R Í D ´ D. Утверждение (a, b) Î R принято записывать в виде a R b. Для произвольного отношения R используются следующие понятия:
· R рефлексивно @ "aÎD. a R a,
· R иррефлексивно @ "aÎD. Ø a R a,
· R симметрично @ a R b Þ b R a,
· R антисимметрично @ a R b & b R a Þ a = b,
· R транзитивно @ a R b & b R c Þ a R c.
Эквивалентностью называется рефлексивное, симметричное и транзитивное бинарное отношение R на D.
Обозначим через (D, ⊑) непустое множество D с отношением порядка ⊑. (D, ⊑) – частично упорядоченное множество (чум), если ⊑ рефлексивно, антисимметрично и транзитивно; при этом порядок ⊑ называется частичным. Частичный порядок ⊑ является линейным (или тотальным), если "a,bÎD. (a ⊑ b Ú b ⊑ a). Бинарное отношение ⊏ называется строгим частичным порядком, если ⊏ иррефлексивно, антисимметрично и транзитивно.
Пусть (D, ⊑) - частично упорядоченное множество. Для произвольного подмножества S Í D определим следующие понятия. Наименьшим (наибольшим) элементом S называется a Î S, такой что a ⊑ x (x ⊑ a) для всех x Î S. Для наименьшего и наибольшего элементов D используются обозначения: ⊥ (bottom) и ┬ (top). Верхней гранью S называется a Î D, такой что x ⊑ a для всех x Î S. Нижней гранью S называется a Î D, такой что a ⊑ x для всех x Î S. Наименьшая верхняя грань (least upper bound) подмножества S обозначается lub(S).
Частично упорядоченное множество (D, ⊑) называется нижней (верхней) полурешёткой, если для любого его подмножества (в том числе и пустого) существует наименьшая верхняя (наибольшая нижняя) грань. Частично упорядоченное множество называется полной решёткой, если оно является верхней и нижней полурешеткой.
Лемма 3.1. Нижняя (верхняя) полурешетка является полной решеткой.
Частично упорядоченное множество (D, ⊏) со строгим порядком ⊏ обладает свойством обрыва бесконечно убывающих цепей (well-founded partial order), если всякое непустое подмножество S имеет минимальный элемент, т. е.
"SÍD. (S ¹ Æ Þ $aÎS "sÎS. Ø s ⊏ a) . (3.1)
Из данного определения следует, что в подмножестве S не существует бесконечно убывающих цепей.
Множество (D, ⊑) с линейным порядком, обладающее свойством обрыва бесконечно убывающих цепей, является вполне упорядоченным: любое подмножество содержит нижнюю грань.
Более полное изложение материала по отношениям порядка см. в учебном пособии [1].