3.3. Отношение эквивалентности.

Определения.

1. Отношение R на множестве Х называется рефлексивным, если xRx  x Х.

2. Отношение R на множестве Х называется симметричным, если для x, у  Х из xRy следует yRx.

3. Отношение R на множестве Х называется транзитивным, если для x, у, z  Х из xRy и yRz следует xRz.

4. Отношение R на множестве Х называется отношением эквивалентности, если оно рефлексивно, симметрично и тран­зи­тивно.

Упражнения.

1. Доказать, что отношение R на множестве Х рефлексивно

 R  _X .

2. Доказать, что отношение R – симметрично  R^-1 – симметрично  R = R^-1.

3. Доказать, что отношение R – транзитивно  R² R (здесь R²= RR) .

4. Доказать, что пустое отношение  – симметрично и транзитивно.

5. Найти множества, для которых пустое отношение  – рефлексивно.

6. Доказать, что на множестве Х наибольшее отношение

R= XX рефлексивно, симметрично и транзитивно, и, следовательно, является отношением эквивалентности.

7. Доказать, что пересечение рефлексивных отношений – рефлексивно, пересечение симметричных отношений – симметрично, пересечение транзитивных отношений – транзитивно, пересечение отношений эквивалентности - отношение эквивалентности.

8. Доказать, что объединение рефлексивных отношений – рефлексивно, объединение симметричных отношений – симметрично. Привести пример транзитивных отношений, объединение которых не транзитивно.

9. Привести пример симметричных отношений, компози-

ция которых не симметрична. Привести пример транзитивных отношений, композиция которых не транзитивна.

Определение. Для отношения эквивалентности  на мно­же­стве Х определим класс элемента х Х как

cl_ x = { y Х| y x }. Когда ясно, какое отношение эквивалентности имеется ввиду, будем обозначать класс элемента х также cl x или .

Утверждения. Пусть  - отношение эквивалентности. Тогда

1)  х Х х cl_ x.

2) Если х cl_ y, то y cl_ x.

3) Если y cl_ x, то cl_ y  cl_ x.

4) Если y x, то cl_ y = cl_ x.

Доказательство 1) следует из определения рефлексивности, 2) – из определения симметричности, 3) – из определения транзитивности, 4) – из утверждений 2), 3).

Теорема. Если на множестве Х задано отношение эквивалентности , то множество Х разбивается в объединение непересекающихся классов эквивалентных элементов, то есть X = , где  x, y X либо cl_ х ∩ cl_ y = , либо cl_ х = cl_ y. Наоборот, любое разбиение множества Х в объединение непересекающихся подмножеств получается из некоторого отношения эквивалентности, которое определено однозначно, то есть если Х = U Х_i , где Х_i ∩ Х_j =  при i  j, то ! отношение эквивалентности  такое, что i Х_i = cl_ х_i , где х_i Х_i .

Доказательство.

. 1. Очевидно,  х Х х cl_ x  X = .

2. Если cl_ х ∩ cl_ y  , то есть cl_ х ∩ cl_ y  z, то из утверждения 4) cl_ х = cl_ z = cl_ y.

 . Пусть Х = U Х_i , где Х_i ∩ Х_j =  при i  j. Если существует отношения эквивалентности , которое порождает данное разбиение, то есть i Х_i = cl_ х_i ,то все элементы из каждого подмножества Х_i должны находиться в отношении , а элементы, не лежащие в одном подмножестве, не должны находиться в отношении  . То есть ху   i такое, что

х, у Х_i . Это означает единственность .

Докажем существование. Как мы только что увидели, если  , то ху   i такое, что х, у Х_i . Очевидно, так определенное отношение  рефлексивно, симметрично и транзитивно, то есть является отношением эквивалентности.  хХ cl_ х – это множество элементов, находящихся с х в отношении , то есть подмножество Х_i, содержащее элемент х. Это

означает существование .



Определение. Множество классов эквивалентных элементов по отношению  называется фактор-множеством и обозначается Х/. Другими словами, элементами множества

Х/ являются классы эквивалентных элементов множества Х. Часто отношение эквивалентности обозначается знаком  .

Упражнения.

1. Пусть ₁ и ₂ - отношения эквивалентности на Х. Найти классы эквивалентных элементов для отношения эквивалентности ₁ ∩ ₂ .

2. Найти классы эквивалентных элементов для наименьшего отношения эквивалентности _Х и для наибольшего отношения эквивалентности ХХ.

Лекция 5.

4. СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ