§ 6. Бинарное отношение порядка. Упорядоченные

МНОЖЕСТВА

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

1. (рефлексивность);

2. если и , то (антисимметричность);

3. если и , то (транзитивность).

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

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

Указанные бинарные отношения объединяют общим названием – бинарное отношение порядка.

Если в множестве М задано отношение порядка, то часто говорят, что элементы этого множества сравнимы.

Пример. Показать, что отношение нестрогого включения является отношением упорядоченности .

□ Любое множество является своим подмножеством, т.е. .

Значит, свойство рефлексивности выполняется.

Если и , то и, следовательно, отношение антисимметрично.

Если и ,то , при этом . Значит, отношение транзитивно.

Такими свойствами обладает отношение упорядоченности. Следовательно, заданное отношение включения является отношением упорядоченности . ■

Множество М с заданным в нем отношением порядка называется упорядоченным.

Если любые два элемента m_i и m_j упорядоченного множества находятся в отношении упорядоченности или , то это множество называется линейно упорядоченным, в противном случае – частично упорядоченным.

Примером линейно упорядоченного множества является множество натуральных чисел.

Пример частично упорядоченного множества показан на рис. 1.10

Рис. 1.10

(в качестве отношения рассмотрено отношение включения ). В этом примере пары элементов: {y} и {x}, {y} и {a}, {x} и {a}, {y,x} и {y,a}, {y,x}и {a,x}, {y,a} и {a,x}, {y} и {a,x}, {a} и {y,x} несравнимы. Остальные элементы попарно сравнимы.

Для элементов элемент называется верхней гранью, если и .

Для элементов элемент называется нижней гранью, если и .

В общем случае для некоторых элементов m_i и m_j верхняя или нижняя грани могут не существовать или быть не единственными.

Меньшая из всех верхних граней называется наименьшей верхней гранью.

Большая из всех нижних граней называется наибольшей нижней гранью.

Частично упорядоченное множество можно изобразить в виде диаграммы. На языке диаграмм два элемента находятся в отношении упорядоченности, т.е. , если существует путь из стрелок, ведущий из m_i в m_j ; верхняя грань элементов m_i и m_j – это элемент, в который есть путь из m_i и из m_j ; нижняя грань элементов m_i и m_j – это элемент, из которого есть путь в m_i и в m_j .

Примером частично упорядоченного множества, представленного в виде диаграммы, является рис. 1.10.

Отношение называется обратным к R , если тогда и только тогда, когда .

Принцип двойственности. Отношение, обратное отношению упорядоченности, также является отношением упорядоченности.

Двойственным к частично упорядоченному множеству М является частично упорядоченное множество , определенное на том же носителе с помощью обратного отношения. На рис. 1.11 показаны двойственные диаграммы двух частично упорядоченных множеств.

Подмножество упорядоченного множества М является упорядоченным, и если это упорядоченное множество является линейным, то подмножество является цепью в М .

Длина цепи l определяется как , где - мощность носителя.

Высотой d(m_i) элемента m_i упорядоченного множества М называется максимум длины цепей m₀ < m₁ < m₂ < … < m_i в М , для которых m_i – наибольший элемент, ( т₀ – минимальный элемент множества М ).

Рис. 1.11

Длиной d (М ) упорядоченного множества М называется максимум длин цепей в М или максимум высот d_i(m_i) его элементов:

.