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

Отношение порядка принято обозначать символом £. Запись Х£У означает, что пара (Х, у) принадлежит множеству АÌМ´М, являю­щемуся отношением порядка в М, причем Х предшествует У (или У следует за Х).

Отношение порядка обладает свойствами:

· Рефлексивности х £ Х;

· Транзитивности; Если Х £ У, а У £ Z , то Х £ Z;

· Антисимметричности; Если Х £ У, а У £ Х, то Х = У.

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

Если для любых двух элементов Х и У множества М имеет место отношение Х £ У (или У £ Х), то М – Совершенно (линейно) упорядоченно.

Например, множество натуральных или действительных чисел с естественным отношением порядка £ являются совершенно упорядо­ченными.

В общем случае может оказаться, что для некоторых пар (Х, у) ни одно из соотношений Х £ У и У £ Х не имеет места. Такие элементы называются Несравнимыми, а множество М называется Частично упорядоченным.

Примерами частичного порядка является отношение «быть дели­телем», отношение включения Ì и т. п. Так, отношение включения на множестве подмножеств МI некоторого универсума М рефлексивно (МI Ì МI), транзитивно (если МI Ì МJ, a МJ Ì МK, то МI Ì МK) и антисимметрично (из МI Ì МJ, и МJÌ МI следует МI = МJ), но среди всевозможных подмножеств имеются такие, что ни одно из соотно­шений из МI Ì МN, и МNÌ МI Не имеет места. Аналогично не все пары элементов из множества натуральных чисел находятся в отношении «быть делителем».

< Предыдущая		Следующая >