1.2.6. Отношения порядка

Рассмотрим отношения G, Lиз 1.2.4, отношениеQиз 1.2.2 и отношение включенияVна множестве всех подмножеств целых чисел (B(Z)– булеан множестваZ): B (Z).

Таблица 1.4

Свойства отношений

Отношение	Р	АР	С	АС	НС	Т
G	-	+	-	-	+	+
L	+	-	-	+	-	+
Q	+	-	-	+	-	+
V	+	-	-	+	-	+

Мы видим, что по свойствам эти отношения разделились на два типа.

Определение. ОтношениеRна множествеХ, обладающее свойствами рефлексивности, антисимметричности, транзитивности, называется отношениемпорядкана множествеХ (обозначается “”).

Определение. ОтношениеRна множествеХ, обладающее свойствами антирефлексивности, несимметричности, транзитивности, называется отношением строгого порядка.

Таким образом, отношения L, Q, Vявляются отношениями порядка на соответствующих множествах, а отношениеG– отношением строгого порядка.

1.2.7. Частично упорядоченные множества

Если на множестве Xвведено отношение порядка, то получен новый объект)– частично упорядоченное множество. Так, различные частично упорядоченные множества (N,) и (N,) можно получить, рассматривая на множествеNнатуральных чисел отношения сравнения “” (-xменьше или равноyи делимости “” (-xявляется делителемy). Слово “частично” используется потому, что не все элементы множества могут быть сравнимы между собой. Для частично упорядоченного множества (N,) несравнимы элементы Nи N, так как ни один из них не является делителем другого.

Если все элементы множества сравнимы между собой, мы имеем линейный порядок, например, (N,) – линейно упорядоченное множество.

1.2.8. Диаграммы Хассе

Для наглядного представления частично упорядоченного множества используют диаграмму Хассе – граф отношенияRбез петель и транзитивно замыкающих дуг.

Пусть . Рассмотрим на множествеXотношения порядка “” и “”. Получим два частично упорядоченных множества (X,) и (X,), различия которых наглядно отражают их диаграммы Хассе (рис.1.9).

Определение. Элементназываетсянаибольшимэлементом частично упорядоченного множества), если w. Элементназываетсямаксимальнымэлементом частично упорядоченного множества), если в множествеXнет элементаyтакого, чтоu y.

Элемент является наибольшим и одновременно максимальным для (X,) (рис. 1.9,а). В частично упорядоченном множестве (X,) есть два максимальныхи, но нет наибольшего (рис. 1.9,б).

Аналогично определяются понятия наименьшего и минимального элементов частично упорядоченного множества.

Теорема. Всякое частично упорядоченное множество имеет не более одного наибольшего элемента.

Доказательство. Пусть)– частично упорядоченное множество. Теорема утверждает, что если в множестве)имеется наибольший элемент, то он единственный. Предположим противное: пусть имеется два различных наибольших элементаи. Тогда по определению наибольшего элементаw и w, откуда в силу антисимметричности отношения порядка “” следует- противоречие, что и доказывает теорему.