Пример 13

Определите индекс разбиения и мощности классов эквивалентности по отношению R, если R:

1) отношение равенства (тождества) на любом множестве;

2) универсальное (полное) отношение на любом множестве;

3) отношение равносильности на множестве формул;

4) отношение "иметь один и тот же остаток от деления на 5" на множестве натуральных чисел N?

Ø 1) Все классы эквивалентности по отношению равенства (тождества) Е = {(a, b): a = b} налюбом множестве М, a,bÎ M, состоят из одного элемента. Индекс разбиения М по отношению Е равен мощности множества М, т.е. | М|.

2) Индекс разбиения универсального (полного) отношения U, U= {(a, b): a U b для любых а,b Î М}, т.е. U = M ´ M для любого М, равен единице. Все элементы множества M принадлежат одному классу эквивалентности по отношению U. Мощность класса равна | М|.

3) Формулы, описывающие одну и ту же элементарную функцию, находятся в одном классе эквивалентности по отношению равносильности. Поэтому счетны само множество формул, множество классов эквивалентности (индекс разбиения) и каждый класс эквивалентности. (Счетными множествами называются множества, равномощные N- множеству натуральных чисел.)

4) Индекс разбиения множества N по заданному отношению R равен 5. Множества натуральных чисел, составляющие каждый класс эквивалентности, - счетны.

Пример 14

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

1) £ и ³, а также < и > для чисел множеств N и R;

2) £ и < на R, введенные в примере 11;

3) Ì и Í на системе подмножеств b(M) множества М;

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

Ø 1) Отношения нестрого порядка £ и ³, а также строго порядка < и > полностью упорядочивают множества M и R.

2) Отношения £ и < на множестве векторов длины п с компонентами из R определяют частичный порядок на Rⁿ: (-3,3/5,2) > (-3,1/2,2); (-3,1/2,2) и (-3,2,1/2) - не сравнимы.

3) Отношение Ì на системе b(M) задает строгий частичный порядок, а отношение Í; - нестрогий частичный порядок. Например, {а, b} Ì {а, b, с}, но {а, b} и {b, с, d} несравнимы по отношению Ì.

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