5.6. Структура упорядоченных множеств

Приведем несколько определений, относящихся к структуре множества М, упорядочен­ного некоторым отношением порядка А. Мажорантой (верхней гра­ницей) подмножества Q  М называют такой элемент т  М, что для всех qQ справедливо соотношение qAm. Минорантой (нижней границей) подмножества Q  М называют такой элемент п М, что для всех qQ справедливо соотношение nAq.

Если мажоранта т (миноранта п) принадлежит Q, то т называ­ется максимумом (п называется минимумом) множества Q и обо­значается max Q (min Q). Максимум, как и минимум, если он су­ществует, единственен; поэтому, когда говорят о минимуме или мак­симуме множества М, имеют в виду вполне определенный элемент.

Множество Q  М может иметь много мажорант и минорант. Если множество мажорант (минорант) имеет минимум (максимум), то этот элемент единственен. Его называют верхней (нижней) гранью или супремумом (инфинумом) множества Q и обозначают sup Q (inf Q).

5.7. Матрицы отношений порядка

Отношению порядка соответ­ствует матрица, у которой главная диагональ заполнена единицами (рефлексивность). Для каждой пары единичных элементов, один из которых расположен в i-м столбце и j-й строке, а второй – в j-м столбце и k-й строке, обязательно существует единичный элемент в i-м столбце и k-й строке (транзитивность). Кроме того, ни одни единичный элемент не имеет симметричного относительно главной диагонали (антисимметричность). Например, матрица отношения «быть делителем» на множестве (1,2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84} имеет вид:

	1	2	3	4	6	7	12	14	21	28	42	84
1	1
2	1	1
3	1		1
4	1	1		1
6	1	1	1		1
7	1					1
12	1	1	1	1	1		1
14	1	1				1		1
21	1		1			1			1
28	1	1		1		1		1		1
42	1	1	1		1	1		1	1		1
84	1	1	1	1	1	1	1	1	1	1	1	1

Матрица отношения строгого порядка отличается тем, что все элементы главной диагонали нулевые (антирефлексивность), а квази­порядка — допустимостью симметричных единичных элементов.