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

Отношение эквивалентности является обобщением отношения равенства: эквивалентные системы считаются «равными». Обобщением обычного отношения  служит отношение порядка.

Рефлексивное, антисимметричное, транзитивное отношение R называется отношением нестрогого порядка и обозначается символом .

Антирефлексивное, антисимметричное, транзитивное отношение R называется отношением строгого порядка и обозначается символом <.

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

Пример1. Нестрогим порядком является обычное отношение  на множестве N. Действительно, это отношение рефлексивно (х  х), транзитивно (х  у, у  z  x = y) и антисимметрично (х  у, у  х  х = у).

Пример2. Отношение включения  на булеане P(U) образует нестрогий порядок.

Пример3. Отношение «х старше у» на некотором множестве людей является отношением строгого порядка.

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

Элементы a, bA сравнимы по отношению порядка R на М, если выполняется aRb или bRa. Во множестве М могут быть элементы, про которые нельзя сказать, что х  у или у  х. Такие элементы называются несравнимыми.

Пример4. Зададим отношение некоторого порядка рисунком:

Тогда элементы а и с – несравнимы.

М ножество А, на котором задано отношение порядка может быть:

а) полностью упорядоченным множеством (линейно упорядоченным или цепью), если любые два эле Рис.4.

мента a и b из А находятся между собой в отношении порядка. (Линейным является нестрогий порядок в примере 1).

б) в противном случае множество А является частично упорядоченным множеством. При этом говорят, что отношение R задаёт на множестве А частичный порядок.

В частично упорядоченном множестве можно выделить цепь.

Если между элементами a и b установлено отношение порядка, то они называются сравнимыми, в противном случае – несравнимыми.

Специальным типом частично упорядоченного множества является интервал

[x, y]={zX| x  z  y} (замкнутый) или (x, y)={zX| x < z < y} (открытый).

Антицепью (семейством Шернера) называется подмножество частично упорядоченного множества, в котором любые два элемента несравнимы.

Пример 1. К каким типам отношений относятся:

1. Отношение равносильности на множестве формул, описывающих элементарные функции (формулы равносильны, если они задают одну и туже функцию, например, (a + b)(a – b)=a² – b², sin²α + cos²α = 1);

2. Отношение, определяемое на множестве всех программ:{(a, b): a и b вычисляют одну и ту же функцию на определяемом множестве};

3. Отношения  и < на множестве векторов длины n с компонентами из N, определяемые следующим образом:

а) , если ;

б) , если и хотя бы в одной координате i выполняется .

4. Отношением предшествования букв < конечного алфавита А (например, отношение предшествования букв русского алфавита, отношение предшествования чисел 0, 1, 2, …, 9 и т. п.), заданного фиксированным списком:

, если предшествует в списке букв.

Отношения, заданные в п. 1 и 2, являются отношениями эквивалентности на соответствующих множествах. Отношения 3 и 4 – отношения порядка (в п. 3 – отношение нестрогого порядка, а в п. 4 – строгого порядка).

Пример 2. Какой порядок на множестве задают отношения:

1.  и , а также < и > для чисел множеств N и R;

2.  и < на Rⁿ _, введённые в примере а, б п. 3; (пример 1);

3.  и  на системе подмножеств β(М) множества М;

4. подчиненности на предприятии;

5. предшествования < букв конечного алфавита А, определённого в примере 1 п. 4.

6) Отношения нестрогого порядка  и , а также строгого порядка < и > полностью упорядочивают множества N и R.

7) Отношения  и < на множестве векторов длины n c компонентами из R определяют частичный порядок на Rⁿ:

и - не сравнимы.

8. Отношение  на системе β(М) задаёт строгий частичный порядок, а отношение  – нестрогий частичный порядок.

Например, {a, b}  {a, b, c}, но {a, b} и {b, c ,d} несравнимы по отношения .

9. Отношение подчинённости на предприятии задаёт строгий порядок. В нём несравнимыми являются, например, сотрудники разных звеньев одного уровня организационной структуры.

10. Отношение предшествования < букв в алфавите А задают полное упорядочение множества букв в алфавите А.