Эквивалентность и порядок

Отношением эквивалентности (или просто эквивалентностью) называют бинарное отношение на множестве, если оно рефлексивно, симметрично, транзитивно.

Отношение эквивалентности имеет важную особенность: экви-валентность R разбивает множество M, на котором оно задано, на непересекающиеся подмножества так, что элементы одного и того же подмножества находятся в отношении R, а между элементами из разных подмножеств отношение R отсутствует. В таком случае говорят, что отношение R задает разбиение на множестве M, или систему классов эквивалентности по отношению R. Мощность этой системы называется индексом разбиения. В то же время любое разбиение множества M на классы определяет некоторое отношение эквивалентности, а именно отношение “входить в один и тот же класс данного разбиения”.

Классом эквивалентности (смежным классом) элемента а по экви-валентности R называется множество

[ a ] _R = a / R ={ b |(a, b)Î R }.

Множество классов эквивалентности элементов множества M по экви-валентности R называется фактор-множеством M по R и обозначается через M / R.

Отношением нестрогого порядка (или частичным порядком) называют бинарное отношение на множестве, если оно рефлексивно, анти-симметрично, транзитивно, и отношением строгого порядка (строгим порядком), если оно антирефлексивно, антисимметрично, транзитивно. Оба эти отношения называются отношениями порядка. Например, отношения “быть не старше” на множестве людей, “быть не больше” на множестве натуральных чисел – нестрогий порядок; отношения “быть моложе”, “быть прямым потомком” на множестве людей – строгий порядок.

Элементы a, b Î M сравнимы по отношению порядка R на M, если выполняется а R b или b R a.

Бинарное отношение на множестве M называется предпорядком на M, если оно рефлексивно и транзитивно.

Частичный порядок £ на множестве M называется линейным, если любые два элемента из M сравнимы по £.

Линейный порядок £ на множестве M называется полным, если каждое непустое подмножество множества M имеет наименьший элемент а, т.е. а £ x для всех x Î M. Множество M в этом случае называется вполне упорядоченным.

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

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

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

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

а) (а ₁,..., а_n)£(b ₁,..., b_n), если а ₁£ b ₁,..., а_n £ b_n;

б) (а ₁,..., а_n)<(b ₁,..., b_n), если (а ₁,..., а_n)£(b ₁,..., b_n) и хотя бы в одной координате i выполняется < ;

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

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

5) отношение предшествования слов упорядоченного конечного алфавита A – лексикографическое упорядочение, определяемое следующим образом.

Пусть даны слова a₁= а ₁₁ а ₁₂… а _{1 m} и a₂= а ₂₁ а ₂₂… а _{2 n}, тогда:

a₁ a₂, если и только если:

а) a₁= и a₂= и , где b, g, d – некоторые слова, возможно пустые; и буквы, либо

б) a₂=a₁b, где b – непустое слово.

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

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

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

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

3) отношение равносильности на множестве формул (см. пример 1, п.1);

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

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

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

Мощность класса равна | M |.

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

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

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

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

2) £ и < на , введенные в примере 1, п.3;

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

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

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

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

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

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

Вопросы для самопроверки и упражнения:

1. Пусть M – конечное множество. Какие отношения эквивалентности дают наибольший и наименьший индекс разбиения?

2. Пусть R ₁ и R ₂ отношения на N ², определяемые следующим образом: (a, b) R ₁ (c, d) тогда и только тогда, когда а £ с и b £ d; (а, b) R ₂ (c, d) тогда и только тогда, когда а £ с и b ³ d. Являются ли R ₁ и R ₂ отношениями порядка?